Fast Fourier Transform

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

$$X[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]$ 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 $2N$ multiplications for each $k$. Then, adding $N$ complex numbers requires $2(N-1)$ additions.

Since this process is repeated for $N$ frequencies, the computational complexity of the DFT is on the order of $N^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=10^9$ (which is not an extraordinary number in the context of DFTs), we can calculate the time it takes for $N^2=10^{18}$ computations.

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

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

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

$$\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.