FFT in Practice | DSP-101

From Theory to Working Code

The Cooley-Tukey algorithm is elegant in theory, but deploying the FFT in a real system requires a handful of engineering decisions that the textbook derivation glosses over. How long should the input be? What if the signal doesn't fit in one block? How do you squeeze the last few percent of performance from the hardware? This lesson covers the practical answers — the choices that separate a working FFT implementation from an optimal one.

The starting point for almost every practical FFT is the same constraint: use a power-of-2 length. The radix-2 Cooley-Tukey algorithm divides by two at every stage, so it only works cleanly when N = 2^m. Attempting a 1000-point FFT with a radix-2 algorithm requires either padding to 1024 or switching to a mixed-radix algorithm — and in practice, padding is almost always the right choice.

Power-of-2 Sizes: The Standard Choices

Every major FFT library optimises heavily for power-of-2 sizes. The common choices in signal processing and audio work are:

N	log₂ N	Multiplies (N/2·log₂N)	Typical Use
256	8	1,024	Low-latency audio, embedded systems
512	9	2,304	Speech processing, OFDM subchannels
1024	10	5,120	General audio, spectrum analysis
2048	11	11,264	High-resolution spectrum, audio codecs
4096	12	24,576	LTE/5G OFDM, professional audio
8192	13	53,248	Scientific measurement, vibration analysis

Larger N gives finer frequency resolution (Δf = f_s / N) but increases latency and memory. The right choice depends on the application's resolution vs. latency trade-off — not just the signal length.

Zero-Padding: Size Up, Don't Truncate

When a signal block has M samples and M is not a power of 2, the standard approach is zero-padding: append zeros to the block until its length reaches the next power of 2. For example, a 700-sample block becomes 1024 samples by appending 324 zeros.

What Zero-Padding Does and Doesn't Do

Zero-padding interpolates the frequency spectrum — it adds more DFT bins between the existing ones, giving a smoother curve. It does not improve true frequency resolution. Two closely spaced sinusoids that are unresolvable in an M-point DFT remain unresolvable after zero-padding to 2M. Resolution is determined by how many actual signal samples you have, not the FFT size.

Zero-padding: more frequency bins, same resolution. More data: better resolution.

Despite not improving resolution, zero-padding is universally used because it enables efficient power-of-2 FFTs and makes spectral peaks easier to locate by providing a denser grid of bins.

The Real-Valued FFT Trick

When the input signal x[n] is real-valued (as it almost always is in practice — audio, sensor readings, communications baseband), the DFT output has a special symmetry: X[N−k] = X*[k] (conjugate symmetry). This means only the first N/2 + 1 bins carry unique information; the rest are redundant mirror images.

Conjugate Symmetry (Real Input)

X[N-k] = X^*[k], \quad k = 1, 2, \ldots, \tfrac{N}{2}-1

For real x[n], the DFT is conjugate-symmetric: X[N−k] = X*[k]. Only bins 0 through N/2 are unique.

A real-valued FFT exploits this by packing two real N/2-point signals into a single N-point complex FFT, then unpacking the result. The net effect: a real-valued N-point FFT costs roughly half the operations of a complex N-point FFT. All major libraries (FFTW, MATLAB's fft, NumPy's rfft, Apple Accelerate) offer dedicated real-FFT routines. Always prefer rfft / fftplan REAL when the input is real — it's a free 2× speedup.

Overlap-Add: FFT on Long Signals

The FFT operates on blocks of fixed length N. But real signals — audio streams, radio recordings, sensor logs — are potentially infinite. The naive approach of chopping the signal into non-overlapping N-point blocks and independently FFT-ing each one is correct for analysis, but breaks down when you want to filter the signal using frequency-domain multiplication.

Convolving an infinite signal x[n] with a finite impulse response h[n] (of length M) using the FFT requires the Overlap-Add (OLA) method:

Step 1

Segment

Divide x[n] into non-overlapping blocks of length L. Each block x_i[n] has L samples.

Step 2

Zero-Pad & FFT

Zero-pad each block to N = L + M − 1 (next power of 2). Compute the N-point FFT of each block and of h[n].

Step 3

Multiply

Multiply the block's spectrum by H[k] (FFT of the filter). This performs linear convolution in the frequency domain.

Step 4

IFFT & Overlap-Add

Take the N-point IFFT. Each output block has N = L + M − 1 samples. Overlap the last M − 1 samples with the start of the next block and add.

The result is identical to direct convolution, but the computational cost is O(N log N) per block rather than O(N·M) — a massive win when M is large (e.g., a 4096-tap room impulse response).

Overlap-Save: The Alternative

The Overlap-Save (OLS) method achieves the same result differently: input blocks overlap by M−1 samples, and the first M−1 samples of each IFFT output (which contain circular convolution artifacts) are discarded. Both OLA and OLS produce identical output when implemented correctly — OLS is slightly preferred in hardware implementations because it avoids the addition step.

FFT Libraries and Hardware Accelerators

Writing a correct, fast FFT from scratch is a research-grade task. In practice, you should always use a well-tested library. The ecosystem is mature:

FFTW

Fastest Fourier Transform in the West

Open-source C library. Auto-tunes for any hardware at runtime using "plans". Supports mixed-radix, real/complex, multi-dimensional. The gold standard for CPUs.

Intel oneMKL / IPP

Intel Math Kernel Library

Highly optimized for Intel CPUs using AVX-512 SIMD. Dramatically faster than FFTW on Intel hardware for specific sizes. Commercial, but free for most uses.

cuFFT / rocFFT

GPU FFT Libraries

NVIDIA cuFFT and AMD rocFFT run hundreds of FFTs in parallel on GPUs. Essential for SDR, deep learning feature extraction, and large batch scientific computing.

ARM Ne10 / Accelerate

Mobile & Embedded

ARM's Ne10 uses NEON SIMD for Cortex-A. Apple's Accelerate framework uses vDSP for iPhone/Mac. Both achieve near-peak performance on mobile hardware.

Dedicated FFT hardware (DSP processors, FPGAs, ASICs) hard-wire butterfly stages for single-cycle throughput — the TI C6000 family, for example, can execute a 1024-point complex FFT in under 1 microsecond. Modern 5G base stations run hundreds of thousands of FFTs per second using ASIC accelerators.

Practical Checklist for FFT Use

Before calling your FFT, verify: (1) input length is a power of 2 — zero-pad if not; (2) use rfft if input is real — half the work; (3) apply a window function if spectral leakage is a concern; (4) normalise the output if you need physical amplitudes (divide by N for IDFT reconstruction); (5) use a library, not home-grown code, for any production system.

rfft + zero-pad + window + library = correct, fast, and efficient.

Lesson 6.4 covers Real-Time Spectrum Analysis — the Short-Time Fourier Transform (STFT), frame/hop sizing, and building a live spectrum analyzer that processes microphone input in the browser.

Key Takeaways

Always use a power-of-2 FFT size — zero-pad to the next power of 2 when the signal block is shorter.
Zero-padding interpolates the frequency spectrum (denser bin grid) but does not improve true frequency resolution; resolution depends on actual signal length.
Real-valued FFTs exploit conjugate symmetry (X[N−k] = X*[k]) to halve computation — use rfft whenever the input is real.
Overlap-Add (OLA) and Overlap-Save (OLS) enable efficient frequency-domain filtering of arbitrarily long signals using fixed-size FFT blocks.
The crossover where FFT-based convolution outperforms direct convolution is at filter length M ≈ 30–50 taps; for longer filters the FFT wins by large margins.
Use established libraries (FFTW, MKL, cuFFT, Accelerate) — they auto-tune for your hardware and are orders of magnitude faster than hand-written code.
Hardware accelerators (DSP cores, FPGAs, ASICs) achieve single-microsecond FFT throughput for real-time applications in communications and audio.