Section 7.1: 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

Prerequisites. This section builds directly on the sampling and discrete-time notation of Chapter 3: a sensor stream is $x[n] = x(nT_s)$ sampled at rate $f_s = 1/T_s$, and the Nyquist limit $f_s/2$ caps the frequencies we can resolve. It also uses complex exponentials $e^{j\theta} = \cos\theta + j\sin\theta$ and the geometric-series sum, both reviewed in Appendix A. No prior Fourier machinery is assumed; the sampling theorem that justifies treating the DFT as a spectrum estimate is developed in Chapter 2 and Chapter 3. The moving-average and convolution ideas from Chapter 6 reappear here as windows.

Why the spectrum is the second language of sensing

Almost every physical signal a machine perceives is, at some level, a sum of oscillations: the 60 Hz hum of a motor, the 1 to 2 Hz sway of a walking gait, the resonant ring of a cracked bearing, the carrier of a radar return. The Discrete Fourier Transform (DFT) is the tool that turns a block of samples into "how much energy sits at each frequency," and the Fast Fourier Transform (FFT) is the algorithm that makes it cheap enough to run inside a wristband or a microcontroller. This section underpins the whole chapter, and much of the feature engineering in Chapter 8. It also carries the warning that trips up more practitioners than any other single mistake in spectral analysis: the peaks you see are not always where the energy really is. That distortion is called spectral leakage, and understanding it is the difference between reading a spectrum and being fooled by one.

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:

$$X[k] = \sum_{n=0}^{N-1} x[n]\, e^{-j 2\pi k n / N}, \qquad k = 0, 1, \dots, N-1.$$

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

$$f_k = \frac{k}{N}\, f_s \ \text{Hz}, \qquad \text{so the bin spacing is} \quad \Delta f = \frac{f_s}{N} = \frac{1}{N T_s}.$$

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.

Resolution comes from duration, sensitivity from rate

Two knobs govern every DFT and they do different jobs. The record length $N T_s$ sets how finely you can separate neighboring frequencies ($\Delta f = 1/(NT_s)$); the sample rate $f_s$ sets how high in frequency you can see before aliasing (Nyquist $=f_s/2$). Confusing them is the classic beginner error: someone unable to resolve two close tones cranks the sample rate and wonders why the peaks still merge, when they needed a longer window, not a faster ADC. Keep this split in mind through the chapter: the short-time transform of Section 7.2 is precisely the art of trading window duration against time localization.

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 best known) 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)$: roughly a four-thousand-fold speedup at $N = 65536$. It 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, though modern libraries handle arbitrary $N$ and simply 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. A single true tone then smears its power across many bins, with slowly decaying side skirts. That smearing is spectral leakage. A related effect, scalloping loss, is what happens when a tone falls exactly between two bins: no bin's response peaks at that frequency, so every bin under-reports it, by as much as 36 percent (3.9 dB) for a rectangular window. The cause is the window's own frequency response, a smooth lobe the DFT only samples at $N$ discrete points, so an off-grid tone is scored partway down the lobe's slope rather than at its crest; it matters most for calibrated amplitude readings and little when you only need to know which frequency dominates, since the true peak is still the tallest bin nearby. Leakage is not noise and not a bug: it is the toll every finite window charges for pretending a snippet of signal repeats forever, and that toll can bury a weak signal under a strong neighbor's skirts.

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")

A 200.5 Hz tone deliberately placed between DFT bins. The rectangular (unwindowed) transform scatters a large fraction of the tone's energy into distant bins; the Hann-windowed transform pulls most of it back near the peak. Run it and the "leaked" percentage for the rectangular case dwarfs the Hann case, which is the whole argument for windowing in one number.

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; 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; Hann widens the main lobe to about two bins but pushes side lobes to 31 dB with a steep rolloff; Blackman-Harris 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.

Misconception: zero-padding buys you resolution

Padding a block of real samples with zeros before the FFT produces more output bins, and it is tempting to read that as a sharper spectrum. It is not: zero-padding only interpolates the same underlying transform more finely, adding no new samples and therefore no new information, so it cannot separate two tones the true observation window could not already separate. What it does buy is a smoother-looking peak and a better estimate of where an isolated tone truly sits between bins. Resolving two close frequencies still requires a longer observation, not more zeros. Exercise 7.1(d) asks you to make this argument yourself.

Right tool: windows and scaling you should not hand-roll

Choosing, generating, and correctly normalizing a window is fiddly, and getting the amplitude scaling wrong silently biases every downstream feature. SciPy packages the whole catalog and the corrections:

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

Three lines replace roughly 30 lines of window math, coherent-gain and noise-power normalization, and one-sided scaling. get_window exposes Hann, Hamming, Blackman-Harris, flat-top, and the parametric Kaiser; the 2/w.sum() factor restores true peak amplitude on a one-sided spectrum.

The library owns the exact taper coefficients, the coherent-gain factor (amplitude-accurate) versus the noise-equivalent-bandwidth factor (power-accurate), and the special flat-top window for reading peak height correctly rather than frequency. Write your own only on a microcontroller with no SciPy, where a precomputed Hann table in flash is the pragmatic choice.

Learning the window instead of choosing it

An active research line asks whether the window shapes in this section need to be hand-picked at all. Differentiable spectral front-ends, SincNet-style learnable filterbanks and GPU-native STFT layers such as nnAudio, parameterize the taper and tune it jointly with the downstream network by gradient descent, trading the classic resolution-versus-leakage tradeoff for whatever the task actually rewards. The open question is when a learned front-end genuinely beats a well-chosen Kaiser or Blackman-Harris window and when it merely overfits the training distribution; these neural front-ends return in Chapter 13.

The phantom bearing tone on a factory gearbox

A predictive-maintenance team, of the kind we return to in Chapter 35, ran a raw FFT on 0.5-second accelerometer blocks from a gearbox and flagged a growing peak near 118 Hz as an emerging bearing fault. Maintenance opened a healthy gearbox and found nothing. The "fault" was the skirt of the dominant gear-mesh line at 120 Hz, leaking sideways because the 0.5-second rectangular window gave only 2 Hz resolution and the strong tone fell slightly off-grid. Lengthening the window to 2 seconds sharpened resolution to 0.5 Hz, and adding a Hann taper dropped the mesh line's side lobes below the real fault features; the phantom 118 Hz peak vanished, and a genuine, much weaker sideband at 122.7 Hz, the actual signature of the developing defect, emerged from under the leakage. The lesson generalizes: before trusting a peak near a strong neighbor, ask whether it is real or the skirt of a leaked one, and whether your window is long and smooth enough to tell.

Exercise 7.1

You sample a vibration signal at $f_s = 2000$ Hz and must distinguish a suspected fault tone at 122.7 Hz from a strong structural line at 120.0 Hz. (a) What is the minimum window length $N$ (and duration in seconds) so that $\Delta f$ can separate them? (b) With that $N$, which power-of-two FFT length would you actually use, and what $\Delta f$ does it give? (c) The 120 Hz line is 40 dB stronger than the fault. Explain why a rectangular window might still hide the fault even at adequate resolution, and name a window whose side-lobe level would reveal it. (d) A colleague proposes zero-padding a 0.25-second block up to your target $N$ instead of collecting more data. Explain in one sentence why that does not recover the resolution you need.

Self-check

1. Two tones 0.4 Hz apart merge into one peak. Do you increase the sample rate or the window length, and why does the other knob not help?

2. In what precise sense does the DFT "assume" your finite block repeats forever, and how does that assumption produce spectral leakage?

3. State the fundamental tradeoff a window makes, and give one situation favoring a rectangular window and one favoring a Blackman-Harris window.

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.