Chapter 6: The DFT & FFT Algorithms

6.1 The Discrete Fourier Transform

Given a finite-length discrete-time signal $x[n]$ of length $N$, the Discrete Fourier Transform (DFT) maps it to a set of $N$ frequency-domain coefficients. Unlike the DTFT, which produces a continuous frequency spectrum, the DFT samples the frequency axis at $N$ equally spaced points.

The Twiddle Factor

The complex exponential kernel appears so frequently that it is given a special symbol, the twiddle factor:

$$W_N = e^{-j2\pi/N}$$

In this notation the DFT becomes $X[k] = \sum_{n=0}^{N-1} x[n]\, W_N^{kn}$. The twiddle factor satisfies important symmetry properties:

• Periodicity: $W_N^{k+N} = W_N^k$
• Symmetry: $W_N^{k+N/2} = -W_N^k$
• Recursion: $W_N^{2} = W_{N/2}$

Computational Complexity

Direct evaluation of the DFT requires $N$ multiplications and $N-1$ additions for each of the $N$ output bins, yielding an overall complexity of$\mathcal{O}(N^2)$. For a signal with $N = 10^6$ samples, this means$10^{12}$ complex multiplications — utterly impractical without the FFT.

6.2 The Cooley-Tukey FFT

The Fast Fourier Transform (FFT) is not a different transform — it is an efficient algorithm for computing the DFT. The most widely used variant is the Cooley-Tukey radix-2 decimation-in-time (DIT) algorithm, published by Cooley and Tukey in 1965 (though Gauss knew a version of it in 1805).

Divide and Conquer

Assume $N$ is a power of 2. Split $x[n]$ into even-indexed and odd-indexed subsequences:

$$X[k] = \underbrace{\sum_{m=0}^{N/2-1} x[2m]\, W_{N/2}^{mk}}_{E[k]} \;+\; W_N^k \underbrace{\sum_{m=0}^{N/2-1} x[2m+1]\, W_{N/2}^{mk}}_{O[k]}$$

Here $E[k]$ is the $N/2$-point DFT of the even samples and$O[k]$ is the $N/2$-point DFT of the odd samples. Using the symmetry $W_N^{k+N/2} = -W_N^k$, we obtain:

Complexity Analysis

The recursion splits the $N$-point DFT into two $N/2$-point DFTs plus $N/2$ butterfly operations. With $\log_2 N$ stages of splitting:

$$T(N) = 2\,T(N/2) + \mathcal{O}(N) \;\;\Longrightarrow\;\; T(N) = \mathcal{O}(N \log N)$$

For $N = 10^6$, this is roughly $2 \times 10^7$ operations instead of$10^{12}$ — a speedup of $50{,}000\times$.

Bit-Reversal Permutation

The DIT algorithm requires the input to be rearranged in bit-reversed order. For $N = 8$, the index mapping is:

6.3 DFT Properties

Many properties of the DTFT carry over to the DFT, but with the critical distinction that all operations are circular (modulo $N$) rather than linear.

6.4 Spectral Leakage & Windowing

Why Does Leakage Happen?

Computing the DFT of a finite-length signal is equivalent to multiplying an infinite signal by a rectangular window, then taking the DFT. In the frequency domain, this multiplication becomes convolution with the Dirichlet kernel (the DFT of the rectangular window):

$$W_{\text{rect}}(\omega) = e^{-j\omega(N-1)/2} \cdot \frac{\sin(N\omega/2)}{\sin(\omega/2)}$$

The main lobe has width $4\pi/N$, and the sidelobes decay slowly at only$\sim 1/k$. When a signal's frequency does not land exactly on a DFT bin, energy "leaks" into all bins through these sidelobes.

Window Functions

Applying a tapered window before the DFT trades a wider main lobe (reduced frequency resolution) for much lower sidelobes (less leakage). The five most common windows:

Resolution vs. Leakage Trade-off

There is a fundamental trade-off: a narrower main lobe gives better frequency resolution but higher sidelobes (more leakage), and vice versa. The rectangular window has the narrowest main lobe ($4\pi/N$) but the worst sidelobes ($-13$ dB). The Nuttall window has sidelobes at $-93$ dB but a main lobe 4x wider.

6.5 Zero-Padding

Zero-padding means appending zeros to a signal before computing the DFT. If $x[n]$ has $N$ samples and we compute an $M$-point DFT with $M > N$:

$$X_M[k] = \sum_{n=0}^{N-1} x[n]\, e^{-j2\pi kn/M}, \quad k = 0, \ldots, M-1$$

This evaluates the DTFT $X(e^{j\omega})$ at $M$ equally spaced frequencies instead of $N$. The result is a finer sampling of the same underlying continuous spectrum — the spectrum looks smoother, but no new information is added.

6.6 Welch Periodogram

The raw periodogram $\hat{S}(\omega) = \frac{1}{N}|X(\omega)|^2$ is the simplest power spectral density (PSD) estimator, but it is inconsistent: its variance does not decrease as $N \to \infty$. Welch's method (1967) fixes this by averaging periodograms of overlapping windowed segments.

Variance Reduction

For $K$ independent segments, the variance of the Welch estimator is reduced by a factor of approximately $1/K$. With 50% overlap and a Hann window, the effective number of independent segments is about $K_{\text{eff}} \approx 0.89\,K$ due to partial correlation between overlapping segments.

6.7 Practical Tips

Choosing N

The DFT length $N$ determines the frequency resolution:

$$\Delta f = \frac{f_s}{N}$$

To resolve two tones separated by $\Delta f_{\min}$ Hz, you need at least $N \geq f_s / \Delta f_{\min}$ samples. With a window applied, the required $N$ increases by the window's main-lobe-width factor (e.g., 2x for Hann).

Padding to Power of 2

The radix-2 FFT requires $N = 2^m$. If your data length is not a power of 2, zero-pad to the next power of 2. Most FFT libraries also support mixed-radix transforms for composite sizes, but powers of 2 remain the fastest:

$$N_{\text{fft}} = 2^{\lceil \log_2 N \rceil}$$

Common Pitfalls

• Forgetting the periodic assumption: The DFT treats the input as periodic with period $N$. Discontinuities at the boundaries cause leakage — always apply a window.
• Confusing DFT bins with physical frequency: Bin $k$ corresponds to frequency $f_k = k \cdot f_s / N$ Hz. The upper half of the DFT ($k > N/2$) represents negative frequencies.
• Not normalizing the FFT output: For amplitude spectra, divide $|X[k]|$ by $N$ (or $N/2$ for one-sided spectra). For PSD, use $|X[k]|^2 / (f_s \cdot N)$.
• Assuming zero-padding improves resolution: It does not. Only more data or parametric methods can do that.

Frequency Resolution Summary

Bringing it all together, the achievable frequency resolution depends on three factors:

1. Data length: $\Delta f = f_s / N$ — the fundamental limit.
2. Window function: Widens the main lobe by a factor of 1.5x (Hann) to 4x (Nuttall), effectively degrading resolution.
3. SNR: In practice, noise limits resolution more than the theoretical $\Delta f$ — use Welch averaging to improve PSD estimates.