DFT & FFT

The discrete Fourier transform computes the spectrum of sampled data, and the FFT computes it fast. Learn the DFT definition, frequency bins and resolution, the radix-2 FFT and its N log N cost, windowing and spectral leakage, zero padding, amplitude scaling, real-signal FFTs, and applications — with a Python spectrum analyser.

The Cooley–Tukey FFT (1965) is one of the most important algorithms ever: it powers OFDM modems (Wi-Fi, 4G/5G), audio codecs, spectrum analysers, radar processing and image compression.

An analogy

The FFT is like sorting a pile of coins by type using a clever divide-and-conquer strategy instead of checking each coin against every type.

The DFT

N samples produce N frequency bins spaced f_s/N apart. For real signals, bins above N/2 mirror those below; rfft returns the N/2 + 1 unique bins. Longer records give finer resolution.

FFT algorithm

Radix-2 FFT splits the DFT into even and odd halves recursively, reducing N² operations to (N/2) log₂ N. For N = 1024: ≈ 1 million vs 5120 complex multiplies — a 200× speed-up.

Leakage and windows

If a tone does not fit an integer number of cycles in the record, its energy spreads into neighbouring bins. Windows (Hann, Hamming, Blackman, flat-top) trade main-lobe width for lower side-lobes.

Applications

OFDM transmitters use IFFT and receivers FFT; fast convolution via FFT (overlap-add); spectrograms; radar range–Doppler maps (2D FFT); vibration and power-quality analysis. Fixed-point FFTs need scaling per stage.

Formulas

Worked example: Resolution

Given: f_s = 48 kHz, N = 1024

Find: Bin spacing and record length.

Answer: 46.9 Hz bins from a 21.3 ms record

Worked example: Speed-up

Given: N = 1024

Find: DFT vs FFT operations.

Answer: ≈ 205× fewer multiplies

Spectrum analyser with numpy FFT

import numpy as np

fs = 8000                                  # sample rate (Hz)
N = 1024                                   # FFT length
t = np.arange(N) / fs
x = 1.0 * np.sin(2 * np.pi * 1000 * t) + 0.5 * np.sin(2 * np.pi * 2500 * t)
x += 0.05 * np.random.default_rng(1).normal(size=N)   # a little noise

w = np.hanning(N)                          # window to reduce leakage
X = np.fft.rfft(x * w)
f = np.fft.rfftfreq(N, 1 / fs)
mag = 2 * np.abs(X) / np.sum(w)            # amplitude-corrected spectrum

# local maxima above 0.1 are the tones
peaks = [k for k in range(1, len(mag) - 1)
         if mag[k] > 0.1 and mag[k] >= mag[k - 1] and mag[k] >= mag[k + 1]]
for k in peaks:
    print(f"{f[k]:7.1f} Hz  amplitude {mag[k]:.2f}")
print(f"bin spacing = {fs / N:.3f} Hz")
#  1000.0 Hz  amplitude 1.00
#  2500.0 Hz  amplitude 0.50
# bin spacing = 7.812 Hz

A window tapers the block edges to limit leakage; dividing by the window sum restores true amplitudes. Both tones fall exactly on bins (1000 and 2500 are multiples of 7.8125 Hz), so the amplitudes read 1.00 and 0.50.

Common mistakes

Applications

Key takeaways

Going further