DFT/FFT and spectral leakage

"I found a strong peak at 49.7 Hz and confidently reported a new vibration mode. It was the 50 Hz mains, smeared sideways because my window did not end where it began."

A Leaky AI Agent

The DFT: projecting a block of samples onto pure tones

What the DFT does is take \(N\) real or complex samples \(x[0], \dots, x[N-1]\) and return \(N\) complex numbers \(X[k]\), each measuring how strongly a pure tone of a particular frequency is present in the block:

Why this works is that the complex exponentials \(e^{-j2\pi kn/N}\) form an orthogonal basis: multiplying the signal by tone \(k\) and summing acts as a correlation, large when \(x\) contains that tone and near zero when it does not. The magnitude \(|X[k]|\) is the amplitude at bin \(k\) and the angle \(\arg X[k]\) is its phase. How bins map to real frequencies is the one formula you must never forget: bin \(k\) corresponds to

The frequency resolution \(\Delta f\) is set entirely by the observation time \(N T_s\), not by the sample rate. To tell 49.5 Hz apart from 50.0 Hz you need \(\Delta f \le 0.5\) Hz, hence at least two seconds of data, no matter how fast you sample. Sampling faster raises the Nyquist ceiling; it does not sharpen closely spaced peaks. For real-valued sensor signals the spectrum is conjugate-symmetric, so only the first \(N/2 + 1\) bins, from DC up to Nyquist, carry unique information.

The FFT: from \(N^2\) to \(N\log N\)

Computed straight from the definition, the DFT costs \(O(N^2)\) complex multiplies: for a 1-second window at 48 kHz that is over two billion operations, hopeless on an embedded target. The FFT is a family of algorithms (the radix-2 Cooley-Tukey version is the famous one) that exploits the symmetry and periodicity of the exponentials to factor the computation recursively, splitting even and odd samples, and driving the cost down to \(O(N\log N)\). For \(N = 65536\) that is roughly a four-thousand-fold speedup. The FFT computes exactly the same numbers as the DFT; it is an accelerator, not an approximation. One practical residue survives: classic radix-2 implementations want \(N\) to be a power of two, which is why sensor pipelines so often chop or pad blocks to 256, 1024, or 4096 samples. Modern libraries handle arbitrary \(N\) but run fastest on smooth, highly composite lengths.

Spectral leakage: the price of a finite window

Here is the trap. The DFT does not analyze your infinite signal; it analyzes the \(N\) samples you handed it, and it implicitly assumes that block repeats forever, wrapping end to start. When a sinusoid completes a whole number of cycles inside the window, that wrap is seamless and its energy lands cleanly in a single bin. When the frequency falls between bins, so the last sample does not continue smoothly into a copy of the first, the periodic extension has a jump, and a jump contains energy at every frequency. The result is that a single true tone smears its power across many bins, with slowly decaying side skirts. That smearing is spectral leakage. A related effect, scalloping loss, means a tone sitting exactly between two bins reads up to about 36 percent (3.9 dB) low in amplitude, because no bin sits on its peak. Leakage is not noise and it is not a bug in the FFT; it is the unavoidable consequence of looking through a finite rectangular window, and it can bury a weak signal under the skirts of a strong neighbor.

The cure is windowing: before transforming, multiply the block by a smooth taper \(w[n]\) that eases both ends to zero, so the periodic extension no longer jumps. Applying a window before the FFT is the standard workflow:

import numpy as np

fs, N = 1000, 1024                     # 1 kHz sample rate, ~1.024 s window
t = np.arange(N) / fs
# A tone at 200.0 Hz lands ON a bin; 200.5 Hz lands BETWEEN bins.
x = np.sin(2 * np.pi * 200.5 * t)      # deliberately off-grid

# Rectangular (no window) vs a Hann taper.
X_rect = np.fft.rfft(x)
X_hann = np.fft.rfft(x * np.hann(N) if hasattr(np, "hann") else x * np.hanning(N))
freqs  = np.fft.rfftfreq(N, 1 / fs)

def peak_report(X, label):
    mag = np.abs(X)
    k = mag.argmax()
    # Fraction of energy OUTSIDE the 3 bins around the peak = leakage.
    total = (mag**2).sum()
    near  = (mag[max(0, k-1):k+2]**2).sum()
    print(f"{label:11s} peak {freqs[k]:6.1f} Hz  leaked {100*(1-near/total):4.1f}%")

peak_report(X_rect, "rectangular")
peak_report(X_hann, "hann")

The code above makes leakage measurable rather than merely visible: the off-grid tone bleeds a large share of its energy across the spectrum under a rectangular window, and the Hann taper confines it. That confinement is not free, and the tradeoff is the real content of windowing. A window trades a wider main lobe (worse resolution, since energy spreads over more bins) for lower side lobes (less leakage into distant bins). A rectangular window has the narrowest main lobe but side lobes only 13 dB down; the Hann window widens the main lobe to about two bins but pushes side lobes to 31 dB and rolls them off steeply; a Blackman-Harris window buys 90-plus dB of side-lobe suppression at the cost of a lobe four bins wide. There is no universally best window, only the right point on this resolution-versus-dynamic-range curve for your problem.

from scipy.signal import get_window
w = get_window(("kaiser", 8.6), N)     # tunable beta trades lobe width vs leakage
X = np.fft.rfft(x * w)
X *= 2 / w.sum()                        # coherent-gain scaling -> true amplitude

What's Next

In Section 7.2, we confront the DFT's biggest limitation: it gives one spectrum for an entire block and cannot say when a frequency appeared. By sliding a short window along the signal and transforming each position, the Short-Time Fourier Transform turns a single spectrum into a spectrogram, a time-frequency picture, and the window-length choice we just met becomes the central knob trading time resolution against frequency resolution.