Learning Objectives
- A change of index variable or an index mapping is used to uncouple the calculations of the discrete Fourier transform (DFT).
- This can result is a significant reduction in the required arithmetic and the resulting algorithm is called the fast Fourier transform (FFT).
A powerful approach to the development of efficient algorithms is to break a large problem into multiple small ones. One method for doing this with both the DFT and convolution uses a linear change of index variables to map the original one-dimensional problem into a multi-dimensional problem. This approach provides a unified derivation of the Cooley-Tukey FFT, the prime factor algorithm (PFA) FFT, and the Winograd Fourier transform algorithm (WFTA) FFT. It can also be applied directly to convolution to break it down into multiple short convolutions that can be executed faster than a direct implementation. It is often easy to translate an algorithm using index mapping into an efficient program.
Definition
The basic definition of the discrete Fourier transform (DFT) is
\[C(k)=\sum_{n=0}^{N-1}x(n)W_{N}^{nk} \nonumber \]
where nn" role="presentation" style="position:relative;" tabindex="0">n, k and N are integers, \[j=\sqrt{-1} \nonumber \]
the basis functions are the NN" role="presentation" style="position:relative;" tabindex="0">N roots of unity,
NN" role="presentation" style="position:relative;" tabindex="0">\[W_{N}=e^{\frac{-j2\pi }{N}} \nonumber \]
and k=0,1,2,...,N-1
If the \(N\)NN" role="presentation" style="position:relative;" tabindex="0"> values of the transform are calculated from the \(N\) values of the data, \(x(n)\), it is easily seen that \(N^2\) complex multiplications and approximately that same number of complex additions are required. One method for reducing this required arithmetic is to use an index mapping (a change of variables) to change the one-dimensional DFT into a two- or higher dimensional DFT. This is one of the ideas behind the very efficient Cooley-Tukey and Winograd algorithms. The purpose of index mapping is to change a large problem into several easier ones. This is sometimes called the “divide and conquer" approach but a more accurate description would be “organize and share" which explains the process of redundancy removal or reduction.
N2N2" role="presentation" style="position:relative;" tabindex="0">Contributor