Stefan Krah | 1919b7e | 2012-03-21 18:25:23 +0100 | [diff] [blame] | 1 | |
| 2 | |
| 3 | (* Copyright (c) 2011 Stefan Krah. All rights reserved. *) |
| 4 | |
| 5 | |
| 6 | The Six Step Transform: |
| 7 | ======================= |
| 8 | |
| 9 | In libmpdec, the six-step transform is the Matrix Fourier Transform (See |
| 10 | matrix-transform.txt) in disguise. It is called six-step transform after |
| 11 | a variant that appears in [1]. The algorithm requires that the input |
| 12 | array can be viewed as an R*C matrix. |
| 13 | |
| 14 | |
| 15 | Algorithm six-step (forward transform): |
| 16 | --------------------------------------- |
| 17 | |
| 18 | 1a) Transpose the matrix. |
| 19 | |
| 20 | 1b) Apply a length R FNT to each row. |
| 21 | |
| 22 | 1c) Transpose the matrix. |
| 23 | |
| 24 | 2) Multiply each matrix element (addressed by j*C+m) by r**(j*m). |
| 25 | |
| 26 | 3) Apply a length C FNT to each row. |
| 27 | |
| 28 | 4) Transpose the matrix. |
| 29 | |
| 30 | Note that steps 1a) - 1c) are exactly equivalent to step 1) of the Matrix |
| 31 | Fourier Transform. For large R, it is faster to transpose twice and do |
| 32 | a transform on the rows than to perform a column transpose directly. |
| 33 | |
| 34 | |
| 35 | |
| 36 | Algorithm six-step (inverse transform): |
| 37 | --------------------------------------- |
| 38 | |
| 39 | 0) View the matrix as a C*R matrix. |
| 40 | |
| 41 | 1) Transpose the matrix, producing an R*C matrix. |
| 42 | |
| 43 | 2) Apply a length C FNT to each row. |
| 44 | |
| 45 | 3) Multiply each matrix element (addressed by i*C+n) by r**(i*n). |
| 46 | |
| 47 | 4a) Transpose the matrix. |
| 48 | |
| 49 | 4b) Apply a length R FNT to each row. |
| 50 | |
| 51 | 4c) Transpose the matrix. |
| 52 | |
| 53 | Again, steps 4a) - 4c) are equivalent to step 4) of the Matrix Fourier |
| 54 | Transform. |
| 55 | |
| 56 | |
| 57 | |
Stefan Krah | 752bfb7 | 2013-01-16 15:16:10 +0100 | [diff] [blame] | 58 | -- |
Stefan Krah | 1919b7e | 2012-03-21 18:25:23 +0100 | [diff] [blame] | 59 | |
| 60 | [1] David H. Bailey: FFTs in External or Hierarchical Memory |
| 61 | http://crd.lbl.gov/~dhbailey/dhbpapers/ |
| 62 | |
| 63 | |