Fast Fourier Transform

Learn how the discrete Fourier transform can be simplified for practical implementation.

We have learned that the DFT computes the spectrum of a length NN signal at NN equally spaced frequencies. The exact expression is given as:

X[k]=n=0N1x[n]ej2πkNnX[k] = \sum_{n=0}^{N-1}x[n]e^{-j2\pi\frac{k}{N}n}

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 x[n]x[n] 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 2N2N multiplications for each kk. Then, adding NN complex numbers requires 2(N1)2(N-1) additions.

Since this process is repeated for NN frequencies, the computational complexity of the DFT is on the order of N2N^2.

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 N=109N=10^9 (which is not an extraordinary number in the context of DFTs), we can calculate the time it takes for N2=1018N^2=10^{18} computations.

1018109×3600×24×36531 years!\frac{10^{18}}{10^9\times 3600\times 24\times 365} \approx 31 ~\text{years!}

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 x[n]x[n] in the DFT definition. As an example, consider any of the outputs X[k+N/2]X[k+N/2] in the upper half of the DFT after breaking the signal into even and odd samples.

ej2πk+N/2N=ej2πkNej2πN/2N=ej2πkNejπ=ej2πkN\begin{align*} e^{-j2\pi\frac{k+N/2}{N}}&=e^{-j2\pi\frac{k}{N}}e^{-j2\pi\frac{N/2}{N}}\\ &=e^{-j2\pi\frac{k}{N}}e^{-j\pi}\\&=-e^{-j2\pi\frac{k}{N}} \end{align*}

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 Nlog2NN\log_2 N.

Taking the same example as the case of the DFT, consider N=109N=10^9. For the processor with a speed of 1 GHz that performs one operation in 1 ns, we have Nlog2N=30109N\log_2 N=30\cdot 10^9. The computational time required is:

3010910930 seconds\frac{30\cdot 10^9}{10^9} \approx 30 ~\text{seconds}

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.