5.2: The FFT from Factoring the DFT Operator
- Page ID
- 1987
The definition of the DFT in Multidimensional Index Mapping can written as a matrix-vector operation by \(C=WX \; \; \text{where}\; \; N=8\)
\[\begin{bmatrix} C(0)\\ C(1)\\ C(2)\\ C(3)\\ C(4)\\ C(5)\\ C(6)\\ C(7) \end{bmatrix}=\begin{bmatrix} 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} \end{bmatrix}\begin{bmatrix} x(0)\\ x(1)\\ x(2)\\ x(3)\\ x(4)\\ x(5)\\ x(6)\\ x(7) \end{bmatrix} \nonumber \]
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\).
Expanding on that gives
\[\begin{bmatrix} C(0)\\ C(4)\\ C(2)\\ C(6)\\ C(1)\\ C(5)\\ C(3)\\ C(7) \end{bmatrix}=\begin{bmatrix} 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 \end{bmatrix}\begin{bmatrix} 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} \end{bmatrix} \nonumber \]
\[\begin{bmatrix} 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} \end{bmatrix}\begin{bmatrix} x(0)\\ x(1)\\ x(2)\\ x(3)\\ x(4)\\ x(5)\\ x(6)\\ x(7) \end{bmatrix} \nonumber \]
where the \(F_i\) matrices are sparse. Note that each has \(16\; (\text{or}\; 2N)\) non-zero terms and \(F_2\) and \(F_3\) have \(8\; (\text{or}\; N)\) non-unity terms. If \(N=2^M\), 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
\[\begin{bmatrix} C(0)\\ C(4)\\ C(2)\\ C(6)\\ C(1)\\ C(5)\\ C(3)\\ C(7) \end{bmatrix}=\begin{bmatrix} 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 & 1 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & -1 \end{bmatrix} \nonumber \]
\[\begin{bmatrix} 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} \end{bmatrix}\begin{bmatrix} 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 \end{bmatrix} \nonumber \]
\[\begin{bmatrix} 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} \end{bmatrix}\begin{bmatrix} 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 \end{bmatrix}\begin{bmatrix} x(0)\\ x(1)\\ x(2)\\ x(3)\\ x(4)\\ x(5)\\ x(6)\\ x(7) \end{bmatrix} \nonumber \]
which is in the form