17db96d56Sopenharmony_ci 27db96d56Sopenharmony_ci 37db96d56Sopenharmony_ci(* Copyright (c) 2011-2020 Stefan Krah. All rights reserved. *) 47db96d56Sopenharmony_ci 57db96d56Sopenharmony_ci 67db96d56Sopenharmony_ciThe Six Step Transform: 77db96d56Sopenharmony_ci======================= 87db96d56Sopenharmony_ci 97db96d56Sopenharmony_ciIn libmpdec, the six-step transform is the Matrix Fourier Transform (See 107db96d56Sopenharmony_cimatrix-transform.txt) in disguise. It is called six-step transform after 117db96d56Sopenharmony_cia variant that appears in [1]. The algorithm requires that the input 127db96d56Sopenharmony_ciarray can be viewed as an R*C matrix. 137db96d56Sopenharmony_ci 147db96d56Sopenharmony_ci 157db96d56Sopenharmony_ciAlgorithm six-step (forward transform): 167db96d56Sopenharmony_ci--------------------------------------- 177db96d56Sopenharmony_ci 187db96d56Sopenharmony_ci 1a) Transpose the matrix. 197db96d56Sopenharmony_ci 207db96d56Sopenharmony_ci 1b) Apply a length R FNT to each row. 217db96d56Sopenharmony_ci 227db96d56Sopenharmony_ci 1c) Transpose the matrix. 237db96d56Sopenharmony_ci 247db96d56Sopenharmony_ci 2) Multiply each matrix element (addressed by j*C+m) by r**(j*m). 257db96d56Sopenharmony_ci 267db96d56Sopenharmony_ci 3) Apply a length C FNT to each row. 277db96d56Sopenharmony_ci 287db96d56Sopenharmony_ci 4) Transpose the matrix. 297db96d56Sopenharmony_ci 307db96d56Sopenharmony_ciNote that steps 1a) - 1c) are exactly equivalent to step 1) of the Matrix 317db96d56Sopenharmony_ciFourier Transform. For large R, it is faster to transpose twice and do 327db96d56Sopenharmony_cia transform on the rows than to perform a column transpose directly. 337db96d56Sopenharmony_ci 347db96d56Sopenharmony_ci 357db96d56Sopenharmony_ci 367db96d56Sopenharmony_ciAlgorithm six-step (inverse transform): 377db96d56Sopenharmony_ci--------------------------------------- 387db96d56Sopenharmony_ci 397db96d56Sopenharmony_ci 0) View the matrix as a C*R matrix. 407db96d56Sopenharmony_ci 417db96d56Sopenharmony_ci 1) Transpose the matrix, producing an R*C matrix. 427db96d56Sopenharmony_ci 437db96d56Sopenharmony_ci 2) Apply a length C FNT to each row. 447db96d56Sopenharmony_ci 457db96d56Sopenharmony_ci 3) Multiply each matrix element (addressed by i*C+n) by r**(i*n). 467db96d56Sopenharmony_ci 477db96d56Sopenharmony_ci 4a) Transpose the matrix. 487db96d56Sopenharmony_ci 497db96d56Sopenharmony_ci 4b) Apply a length R FNT to each row. 507db96d56Sopenharmony_ci 517db96d56Sopenharmony_ci 4c) Transpose the matrix. 527db96d56Sopenharmony_ci 537db96d56Sopenharmony_ciAgain, steps 4a) - 4c) are equivalent to step 4) of the Matrix Fourier 547db96d56Sopenharmony_ciTransform. 557db96d56Sopenharmony_ci 567db96d56Sopenharmony_ci 577db96d56Sopenharmony_ci 587db96d56Sopenharmony_ci-- 597db96d56Sopenharmony_ci 607db96d56Sopenharmony_ci [1] David H. Bailey: FFTs in External or Hierarchical Memory 617db96d56Sopenharmony_ci http://crd.lbl.gov/~dhbailey/dhbpapers/ 627db96d56Sopenharmony_ci 637db96d56Sopenharmony_ci 64