| 1 |
|
| 2 |
|
| 3 |
(* Copyright (c) 2011-2020 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 |
|
| 58 |
-- |
| 59 |
|
| 60 |
[1] David H. Bailey: FFTs in External or Hierarchical Memory |
| 61 |
http://crd.lbl.gov/~dhbailey/dhbpapers/ |
| 62 |
|
| 63 |
|