0.5 Factoring the signal processing operators

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. Thisapproach is used by Tolimieri [link] , [link] , Egner [link] , Selesnick, Elliott [link] 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

which clearly requires $N^2=64$ complex multiplications and $N(N-1)$ additions. A factorization of the DFT operator, $W$ , gives $W=F_1{F}_2{F}_3$ and $C=F_1{F}_2{F}_{3}X$ or, expanded,

where the $F_i$ matrices are sparse. Note that each has 16 (or $2N$ ) non-zero terms and $F_2$ and $F_3$ have 8 (or $N$ ) non-unity terms. If $N=2^M$ , then the number of factors is $log\left(N\right)=M$ . In another form with the twiddle factors separated so as to count the complexmultiplications we have

which is in the form $C=A_1{M}_1{A}_2{M}_2{A}_{3}X$ described by the index map. $A_1$ , $A_2$ , and $A_3$ each represents 8 additions, or, in general, $N$ additions. $M_1$ and $M_2$ 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\left(N\right)$ 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 [link] .

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 [link] .