Factoring the Signal Processing Operators
1.4
2008/05/22 15:46:57 GMT-5
2008/07/24 11:33:52.337 GMT-5
C.
Sidney
Burrus
csb@rice.edu
C.
Sidney
Burrus
csb@rice.edu
Daniel
Collins
Williamson
dwilliamson1285@gmail.com
A third approach to removing redundancy in an algorithm is to express
the algorithm as an operator and then factor that operator into sparse factors. This
approach is used by Tolimieri , , Egner ,
Selesnick, Elliott and others. It is presented in a more general form
in DFT and FFT: An Algebraic View The operators may be in the form of a matrix
or a tensor operator.
The FFT from Factoring the DFT Operator
The definition of the DFT in Multidimensional Index Mapping: Equation 1 can written as a matrix-vector
operation by C=WX which, for N=8 is
C
(
0
)
C
(
1
)
C
(
2
)
C
(
3
)
C
(
4
)
C
(
5
)
C
(
6
)
C
(
7
)
=
W
0
W
0
W
0
W
0
W
0
W
0
W
0
W
0
W
0
W
1
W
2
W
3
W
4
W
5
W
6
W
7
W
0
W
2
W
4
W
6
W
8
W
10
W
12
W
14
W
0
W
3
W
6
W
9
W
12
W
15
W
18
W
21
W
0
W
4
W
8
W
12
W
16
W
20
W
24
W
28
W
0
W
5
W
10
W
15
W
20
W
25
W
30
W
35
W
0
W
6
W
12
W
18
W
24
W
30
W
36
W
42
W
0
W
7
W
14
W
21
W
28
W
35
W
42
W
49
x
(
0
)
x
(
1
)
x
(
2
)
x
(
3
)
x
(
4
)
x
(
5
)
x
(
6
)
x
(
7
)
which clearly requires N2=64 complex multiplications and N(N-1) additions.
A factorization of the DFT operator, W, gives W=F1F2F3 and
C=F1F2F3X or, expanded,
C
(
0
)
C
(
4
)
C
(
2
)
C
(
6
)
C
(
1
)
C
(
5
)
C
(
3
)
C
(
7
)
=
1
1
0
0
0
0
0
0
1
-
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
-
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
-
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
-
1
1
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
W
0
0
-
W
2
0
0
0
0
0
0
W
0
0
-
W
2
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
W
0
0
-
W
0
0
0
0
0
0
0
W
2
0
-
W
2
1
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
1
W
0
0
0
0
-
W
0
0
0
0
0
W
1
0
0
0
-
W
1
0
0
0
0
W
2
0
0
0
-
W
2
0
0
0
0
W
3
0
0
0
-
W
3
x
(
0
)
x
(
1
)
x
(
2
)
x
(
3
)
x
(
4
)
x
(
5
)
x
(
6
)
x
(
7
)
where the Fi matrices are sparse. Note that each has 16 (or 2N) non-zero terms
and F2 and F3 have 8 (or N) non-unity terms. If N=2M, then the number
of factors is log(N)=M.
In another form with the twiddle factors separated so as to count the complex
multiplications we have
C
(
0
)
C
(
4
)
C
(
2
)
C
(
6
)
C
(
1
)
C
(
5
)
C
(
3
)
C
(
7
)
=
1
1
0
0
0
0
0
0
1
-
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
-
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
-
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
-
1
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
W
0
0
0
0
0
0
0
0
0
W
2
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
W
0
0
0
0
0
0
0
0
0
W
2
1
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
-
1
0
0
0
0
0
0
1
0
-
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
-
1
0
0
0
0
0
0
1
0
-
1
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
W
0
0
0
0
0
0
0
0
0
W
1
0
0
0
0
0
0
0
0
W
2
0
0
0
0
0
0
0
0
W
3
1
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
1
1
0
0
0
-
1
0
0
0
0
1
0
0
0
-
1
0
0
0
0
1
0
0
0
-
1
0
0
0
0
1
0
0
0
-
1
x
(
0
)
x
(
1
)
x
(
2
)
x
(
3
)
x
(
4
)
x
(
5
)
x
(
6
)
x
(
7
)
which is in the form C=A1M1A2M2A3X described by the index map.
A1, A2, and A3 each represents 8 additions, or, in general, N additions.
M1 and M2 each represent 4 (or N/2) multiplications.
This is a very interesting result showing that implementing the DFT using the factored
form requires considerably less arithmetic than the single factor definition.
Indeed, the form of the formula that Cooley and Tukey derived showing that the
amount of arithmetic required by the FFT is on the order of Nlog(N) can be
seen from the factored operator formulation.
Much of the theory of the FFT can be developed using operator factoring and it
has some advantages for implementation of parallel and vector computer
architectures. This book will not develop this approach.
The eigenspace approach is somewhat of the same type .
Algebraic Theory of Signal Processing Algorithms
A very general structure for all kinds of algorithms can be generalized from
the approach of operators and operator decomposition. This is developed as
“Algebraic Theory of Signal Processing" discussed in the module DFT and FFT: An Algebraic View by Püschel and others .
Beard, James K.
The FFT in the 21st Century: Eigenspace Processing
Kluwer
2003
Boston
Elliott, Douglas F.
Handbook of Digital Signal Processing
Academic Press
1987
San Diego, CA
Chapter 7 on FFT by Elliott
Egner, Sebastian and Püschel, Markus
Automatic Generation of Fast Discrete Signal Transforms
IEEE Transactions on Signal Processing
2001
49
9
1992–202
Tolimieri, Richard and An, Myoung and Lu, Chao
Algorithms for Discrete Fourier Transform and Convolution
Springer-Verlag
1989, 1997
New York
second
Tolimieri, Richard and An, Myoung and Lu, Chao
Mathematics of Multidimensional Fourier Transform Algorithms
Springer-Verlag
1993, 1997
New York
second