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