2.4: Efficiencies Resulting from Index Mapping with the DFT

Last updated
Save as PDF

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}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$\newcommand{\avec}{\mathbf a}$ $\newcommand{\bvec}{\mathbf b}$ $\newcommand{\cvec}{\mathbf c}$ $\newcommand{\dvec}{\mathbf d}$ $\newcommand{\dtil}{\widetilde{\mathbf d}}$ $\newcommand{\evec}{\mathbf e}$ $\newcommand{\fvec}{\mathbf f}$ $\newcommand{\nvec}{\mathbf n}$ $\newcommand{\pvec}{\mathbf p}$ $\newcommand{\qvec}{\mathbf q}$ $\newcommand{\svec}{\mathbf s}$ $\newcommand{\tvec}{\mathbf t}$ $\newcommand{\uvec}{\mathbf u}$ $\newcommand{\vvec}{\mathbf v}$ $\newcommand{\wvec}{\mathbf w}$ $\newcommand{\xvec}{\mathbf x}$ $\newcommand{\yvec}{\mathbf y}$ $\newcommand{\zvec}{\mathbf z}$ $\newcommand{\rvec}{\mathbf r}$ $\newcommand{\mvec}{\mathbf m}$ $\newcommand{\zerovec}{\mathbf 0}$ $\newcommand{\onevec}{\mathbf 1}$ $\newcommand{\real}{\mathbb R}$ $\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$ $\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$ $\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$ $\newcommand{\laspan}[1]{\text{Span}\{#1\}}$ $\newcommand{\bcal}{\cal B}$ $\newcommand{\ccal}{\cal C}$ $\newcommand{\scal}{\cal S}$ $\newcommand{\wcal}{\cal W}$ $\newcommand{\ecal}{\cal E}$ $\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$ $\newcommand{\gray}[1]{\color{gray}{#1}}$ $\newcommand{\lgray}[1]{\color{lightgray}{#1}}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\row}{\text{Row}}$ $\newcommand{\col}{\text{Col}}$ $\renewcommand{\row}{\text{Row}}$ $\newcommand{\nul}{\text{Nul}}$ $\newcommand{\var}{\text{Var}}$ $\newcommand{\corr}{\text{corr}}$ $\newcommand{\len}[1]{\left|#1\right|}$ $\newcommand{\bbar}{\overline{\bvec}}$ $\newcommand{\bhat}{\widehat{\bvec}}$ $\newcommand{\bperp}{\bvec^\perp}$ $\newcommand{\xhat}{\widehat{\xvec}}$ $\newcommand{\vhat}{\widehat{\vvec}}$ $\newcommand{\uhat}{\widehat{\uvec}}$ $\newcommand{\what}{\widehat{\wvec}}$ $\newcommand{\Sighat}{\widehat{\Sigma}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\newcommand{\amp}{&}$ $\definecolor{fillinmathshade}{gray}{0.9}$

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 = N 2 F (N 1) " role="presentation" style="position:relative;" tabindex="0">$

The outer sum which gives $N_1$ length-$N_2$ DFT's requires $N_1F(N_2)$ operations. The total number of arithmetic operations is then

\[F=N_{2}F(N_{1})+N_{1}F(N_{2}) \nonumber \]

The first question to be considered is for a fixed length $N$, what is the optimal relation of $N_1$ and $N_2$ in the sense of minimizing the required amount of arithmetic. To answer this question, $N_1$and $N_2$are temporarily assumed to be real variables rather than integers. If the short length- $N_i$ DFT's in the equation and any TF multiplications are assumed to require $N_i^2$ operations, i.e

\[F(N_{i})=N_{i}^{2} \nonumber \]

Thus Efficiencies Resulting from Index Mapping with the DFT becomes

\[F=N_{2}N_{1}^{2}+N_{1}N_{2}^{2}=N(N_{1}+N_{2})=N(N_{1}+NN_{1}^{-1}) \nonumber \]

To find the minimum of $F$ over $N_1$, the derivative of $F$ with respect to $N_1$ is set to zero (temporarily assuming the variables to be continuous) and the result requires $N_{1}=N_{2}$

\[\frac{\mathrm{d} F}{\mathrm{d} N_{1}}=0\; \; \; \; \Rightarrow N_{1}=N_{2} \nonumber \]

This result is also easily seen from the symmetry of $N_1$, and in $N_2$, in $N=N_1N_2$. If a more general model of the arithmetic complexity of the short DFT's is used, the same result is obtained, but a closer examination must be made to assure that $N_{1}=N_{2}$ is a global minimum.

there are now $M$ length-$R$ DFT's and, since the factors are all equal, the index map must be type two. This means there must be twiddle factors.

In order to simplify the analysis, only the number of multiplications will be considered. If the number of multiplications for a length-$R$ DFT is $F(R)$, then the formula for operation counts in the equation generalizes to

\[F=N\sum_{i=1}^{M}\frac{F(N_{i})}{N_{i}}=NM\frac{F(R)}{R} \nonumber \]

for $N_i=R$

\[F=N\ln R(N)\frac{F(R)}{R}=(N\ln N)\frac{F(R)}{R\ln R} \nonumber \]

This is a very important formula which was derived by Cooley and Tukey in their famous paper on the FFT. It states that for a given $R$ which is called the radix, the number of multiplications (and additions) is proportional to $N\ln N$. It also shows the relation to the value of the radix, $R$.

In order to get some idea of the “best" radix, the number of multiplications to compute a length-$R$ DFT is assumed to be

\[F(R)=R^{x} \nonumber \]

If this is used with the equation, the optimal $R$ can be found.

\[\frac{\mathrm{d} F}{\mathrm{d} R}=0\; \; \; \; \Rightarrow R=e^{\frac{1}{(x-1)}} \nonumber \]

For $x=2$ this gives $R=e$, with the closest integer being three.

While this is an interesting result from the analysis of the effects of index mapping alone, in practice, index mapping is almost always used in conjunction with special algorithms for the short length-$N_i$ DFT's in the equation. For example, if $R=2\; \text{or}\; 4$, there are no multiplications required for the short DFT's. Only the TFs require multiplications. Winograd (see Winograd's Short DFT Algorithms ) has derived some algorithms for short DFT's that require O(N) multiplications. This means that $F (N i) = K N i " role="presentation" style="position:relative;" tabindex="0">$

Search

Text Color

Text Size

Margin Size

Font Type