Fast Fourier Transform
Learn how the discrete Fourier transform can be simplified for practical implementation.
We'll cover the following
We have learned that the DFT computes the spectrum of a length signal at equally spaced frequencies. The exact expression is given as:
When implemented in real systems, that is a lot of operations to perform for any digital signal processor, which we’ll explore in the next section.
Complexity of the DFT
If is real, we have two complex multiplications for each frequency—one with the real and the other with the imaginary part of the analysis sinusoid. In total, these are multiplications for each . Then, adding complex numbers requires additions.
Since this process is repeated for frequencies, the computational complexity of the DFT is on the order of .
As an example, assume that the processor speed is 1 GHz, and it performs one operation in 1 ns. Then, for a DFT size of (which is not an extraordinary number in the context of DFTs), we can calculate the time it takes for computations.
For this reason, the DFT was not a major tool in signal analysis until the discovery of the fast Fourier transform (FFT).
Reducing the complexity
The FFT is not an approximation to the DFT. Instead, it is the DFT with a reduced number of operations. To understand why the FFT performs so well, we need to see the sinusoidal factors appearing with the signal
To understand why FFT performs so well, we need to see the sinusoidal factors appearing with the signal in the DFT definition. As an example, consider any of the outputs in the upper half of the DFT after breaking the signal into even and odd samples.
Similar simplifications reduce the number of multiplications through subsequent stages and result in a much faster algorithm. The computational complexity of the FFT turns out to be on the order of .
Taking the same example as the case of the DFT, consider . For the processor with a speed of 1 GHz that performs one operation in 1 ns, we have . The computational time required is:
Compare this the timespan of 31 years that it takes the DFT, and it is easy to see why the FFT, commonly known as “the algorithm of the 20th century,” is the most ubiquitous algorithm in use today.
Get hands-on with 1200+ tech skills courses.