Skip to main content
Engineering LibreTexts

5.2: The FFT from Factoring the DFT Operator

  • Page ID
    1987
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    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

    C=A1M1A2M2A3XC=A1M1A2M2A3X" role="presentation" style="position:relative;" tabindex="0">


    This page titled 5.2: The FFT from Factoring the DFT Operator is shared under a CC BY license and was authored, remixed, and/or curated by C. Sidney Burrus.

    • Was this article helpful?