1 2 3(* Copyright (c) 2011 Stefan Krah. All rights reserved. *) 4 5 6The Six Step Transform: 7======================= 8 9In libmpdec, the six-step transform is the Matrix Fourier Transform (See 10matrix-transform.txt) in disguise. It is called six-step transform after 11a variant that appears in [1]. The algorithm requires that the input 12array can be viewed as an R*C matrix. 13 14 15Algorithm 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 30Note that steps 1a) - 1c) are exactly equivalent to step 1) of the Matrix 31Fourier Transform. For large R, it is faster to transpose twice and do 32a transform on the rows than to perform a column transpose directly. 33 34 35 36Algorithm 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 53Again, steps 4a) - 4c) are equivalent to step 4) of the Matrix Fourier 54Transform. 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 64