Skip to main content
Engineering LibreTexts

2.4: Efficiencies Resulting from Index Mapping with the DFT

  • Page ID
    1968
  • \( \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}}\)

    In this section the reductions in arithmetic in the DFT that result from the index mapping alone will be examined. In practical algorithms several methods are always combined, but it is helpful in understanding the effects of a particular method to study it alone.

    The most general form of an uncoupled two-dimensional DFT is given by

    \[X(k_{1},k_{2})=\sum_{n_{2}=0}^{N_{2}-1}\left \{ \sum_{n_{1}=0}^{N_{1}-1} x(n_{1},n_{2})f_{1}(n_{1},n_{2},k_{1})\right \}f_{2}(n_{2},k_{1},k_{2}) \nonumber \]

    where the inner sum calculates \(N_2\) length-\(N_1\) DFT's and, if for a type-two map, the effects of the TFs. If the number of arithmetic operations for a length-\(N\) DFT is denoted by \(F(N)\), the number of operations for this inner sum is

    F=N2F(N1)F=N2F(N1)" role="presentation" style="position:relative;" tabindex="0">


    This page titled 2.4: Efficiencies Resulting from Index Mapping with the DFT is shared under a CC BY license and was authored, remixed, and/or curated by C. Sidney Burrus.

    • Was this article helpful?