blob: 759147ff1cc232d13d97ae37ae84def06603175c (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
(* Copyright (c) 2011 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/
|
