Processing Operators1
A third approach to removing redundancy in an algorithm is to ex-
press the algorithm as an operator and then factor that operator into
sparse factors. This approach is used by Tolimieri [382], [384], Eg-
ner [118], Selesnick, Elliott [121] and others. It is presented in a
more general form in DFT and FFT: An Algebraic View (Chap-
ter 8) The operators may be in the form of a matrix or a tensor
operator.
6.1 The FFT from Factoring the DFT Oper-
ator
The definition of the DFT in Multidimensional Index Mapping:
Equation 1 (3.1) can written as a matrix-vector operation by C =
W X which, for N = 8 is
1This content is available online at <http://cnx.org/content/m16330/1.8/>.
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
51
CHAPTER 6. FACTORING THE SIGNAL
52
PROCESSING OPERATORS
C (0)
W 0 W 0
W 0
W 0
W 0
W 0
W 0
W 0
x (0)
C (1)
W 0 W 1
W 2
W 3
W 4
W 5
W 6
W 7 x (1)
C (2)
W 0
W 2
W 4
W 6
W 8
W 10 W 12 W 14 x (2)
C (3)
W 0
W 3
W 6
W 9
W 12 W 15 W 18 W 21 x (3)
=
(6.1)
C (4)
W 0
W 4
W 8
W 12 W 16 W 20 W 24 W 28 x (4)
C (5)
W 0
W 5 W 10 W 15 W 20 W 25 W 30 W 35 x (5)
C (6)
W 0
W 6 W 12 W 18 W 24 W 30 W 36 W 42 x (6)
C (7)
W 0 W 7 W 14 W 21 W 28 W 35 W 42 W 49
x (7)
which clearly requires N2 = 64 complex multiplications and
N (N − 1) additions. A factorization of the DFT operator, W , gives
W = F1 F2 F3 and C = F1 F2 F3 X or, expanded,
C (0)
1
1 0
0 0
0 0
0
1
0
1
0
0
0
0
0
C (4)
1 −1 0
0 0
0 0
0 0
1
0
1
0
0
0
0
C (2)
0
0 1
1 0
0 0
0 W 0
0
−W 2
0
0
0
0
0
C (6)
0
0 1 −1 0
0 0
0 0
W 0
0
−W 2
0
0
0
0
=
(6.2)
C (1)
0
0 0
0 1
1 0
0 0
0
0
0
1
0
1
0
C (5)
0
0 0
0 1 −1 0
0 0
0
0
0
0
1
0
1
C (3)
0
0 0
0 0
0 1
1 0
0
0
0
W 0
0
−W 0
0
C (7)
0
0 0
0 0
0 1 −1
0
0
0
0
0
W 2
0
−W 2
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
53
1
0
0
0
1
0
0
0
x (0)
0
1
0
0
0
1
0
0
x (1)
0
0
1
0
0
0
1
0
x (2)
0
0
0
1
0
0
0
1
x (3)
(6.3)
W 0
0
0
0
−W 0
0
0
0
x (4)
0
W 1
0
0
0
−W 1
0
0
x (5)
0
0
W 2
0
0
0
−W 2
0
x (6)
0
0
0
W 3
0
0
0
−W 3
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)
1
1
0
0
0
0
0
0
C (4)
1
−1 0
0
0
0
0
0
C (2)
0
0
1
1
0
0
0
0
C (6)
0
0
1 −1 0
0
0
0
=
(6.4)
C (1)
0
0
0
0
1
1
0
0
C (5)
0
0
0
0
1 −1 0
0
C (3)
0
0
0
0
0
0
1
1
C (7)
0
0
0
0
0
0
1 −1
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
CHAPTER 6. FACTORING THE SIGNAL
54
PROCESSING OPERATORS
1 0
0
0
0 0
0
0
1 0
1
0
0 0
0
0
0 1
0
0
0 0
0
0 0 1
0
1
0 0
0
0
0
0 W 0
0
0 0
0
0 1 0 −1
0
0 0
0
0
0
0
0
W 2 0 0
0
0 0 1
0
−1 0 0
0
0
(6.5)
0
0
0
0
1 0
0
0 0 0
0
0
1 0
1
0
0
0
0
0
0 1
0
0 0 0
0
0
0 1
0
1
0
0
0
0
0 0 W 0
0 0 0
0
0
1 0 −1
0
0 0
0
0
0 0
0
W 2
0 0
0
0
0 1
0
−1
1 0 0 0
0
0
0
0
1 0 0 0
1
0
0
0
x (0)
0 1 0 0
0
0
0
0 0 1 0 0
0
1
0
0 x (1)
0
0 1 0
0
0
0
0 0 0 1 0
0
0
1
0 x (2)
0
0 0 1
0
0
0
0 0 0 0 1
0
0
0
1 x (3)
(6.6)
0
0 0 0 W 0
0
0
0 1 0 0 0 −1
0
0
0 x (4)
0
0 0 0
0
W 1
0
0 0 1 0 0
0
−1
0
0 x (5)
0
0 0 0
0
0
W 2
0 0 0 1 0
0
0
−1
0 x (6)
0 0 0 0
0
0
0
W 3
0 0 0 1
0
0
0
−1
x (7)
which is in the form C = A1 M1 A2 M2 A3 X described by the in-
dex map. A1, A2, and A3 each represents 8 additions, or, in general,
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
55
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 arith-
metic 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. The eigenspace approach is
somewhat of the same type [18].
6.2 Algebraic Theory of Signal Processing
Algorithms
A very general structure for all kinds of algorithms can be gener-
alized from the approach of operators and operator decomposition.
This is developed as “Algebraic Theory of Signal Processing" dis-
cussed in the module DFT and FFT: An Algebraic View (Chap-
ter 8) by P üschel and others [118].
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
CHAPTER 6. FACTORING THE SIGNAL
56
PROCESSING OPERATORS
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>