| |
| |
| (* Copyright (c) 2011-2020 Stefan Krah. All rights reserved. *) |
| |
| |
| The Six Step Transform: |
| ======================= |
| |
| In libmpdec, the six-step transform is the Matrix Fourier Transform (See |
| matrix-transform.txt) in disguise. It is called six-step transform after |
| a variant that appears in [1]. The algorithm requires that the input |
| array can be viewed as an R*C matrix. |
| |
| |
| Algorithm six-step (forward transform): |
| --------------------------------------- |
| |
| 1a) Transpose the matrix. |
| |
| 1b) Apply a length R FNT to each row. |
| |
| 1c) Transpose the matrix. |
| |
| 2) Multiply each matrix element (addressed by j*C+m) by r**(j*m). |
| |
| 3) Apply a length C FNT to each row. |
| |
| 4) Transpose the matrix. |
| |
| Note that steps 1a) - 1c) are exactly equivalent to step 1) of the Matrix |
| Fourier Transform. For large R, it is faster to transpose twice and do |
| a transform on the rows than to perform a column transpose directly. |
| |
| |
| |
| Algorithm six-step (inverse transform): |
| --------------------------------------- |
| |
| 0) View the matrix as a C*R matrix. |
| |
| 1) Transpose the matrix, producing an R*C matrix. |
| |
| 2) Apply a length C FNT to each row. |
| |
| 3) Multiply each matrix element (addressed by i*C+n) by r**(i*n). |
| |
| 4a) Transpose the matrix. |
| |
| 4b) Apply a length R FNT to each row. |
| |
| 4c) Transpose the matrix. |
| |
| Again, steps 4a) - 4c) are equivalent to step 4) of the Matrix Fourier |
| Transform. |
| |
| |
| |
| -- |
| |
| [1] David H. Bailey: FFTs in External or Hierarchical Memory |
| http://crd.lbl.gov/~dhbailey/dhbpapers/ |
| |
| |