Also known as: fast Fourier transform, FFT
The fast Fourier transform (FFT) is an efficient algorithm for computing the discrete Fourier transform (DFT), reducing the arithmetic from O(N²) to O(N log N) so the same result can be produced fast enough to run many times a second in real time.1 It computes exactly the same spectrum as a direct DFT — it is a shortcut, not an approximation — and that speedup is what makes live spectrum displays, waterfalls, and OFDM radios practical at all.
How it works
The FFT exploits the redundancy in the DFT sum. The most common variant, the Cooley–Tukey radix-2 algorithm, recursively splits an N-point transform into two N/2-point transforms — one over the even-indexed samples, one over the odd — and then recombines them with a butterfly that multiplies one half by a twiddle factor (a complex root of unity) and adds and subtracts. Applying this split log₂N times leaves only 2-point butterflies, so the total cost is N/2 · log₂N butterflies rather than N² complex multiplies. Radix-2 wants a power-of-two length; mixed-radix and Bluestein variants handle other sizes.
The band is divided into a number of bins equal to the FFT size; the frequency resolution is roughly sample rate ÷ FFT size. More bins give finer resolution but cover a longer time window, so the update rate drops and CPU cost rises — the familiar time-versus-frequency resolution trade-off.
In practice
Feeding raw samples straight into an FFT causes spectral leakage: because the block is a finite chunk cut from a longer signal, its edges act like a discontinuity and smear energy across neighbouring bins. The fix is to multiply the block by a tapered window function (Hann, Hamming, Blackman-Harris…) before the transform, trading a slightly wider main lobe for far lower sidelobes. To turn short, noisy transforms into a stable power-spectral-density estimate, Welch’s method averages the windowed FFTs of many overlapping segments.
The FFT also accelerates filtering: convolving a signal with a long filter is far cheaper as a multiply in the frequency domain, and streaming that idea across successive blocks is exactly the overlap-add and overlap-save method.
Relevance to SDR
The FFT drives the spectrum and waterfall displays used to find signals and spot a steady control channel, and GopherTrunk relies on it for band surveys and inside polyphase channelizers. It is also the heart of OFDM: systems such as Wi-Fi, LTE, 5G NR, DVB-T, and DAB transmit data on thousands of orthogonal subcarriers, and the receiver recovers them all with a single FFT per symbol — the algorithm that makes wideband digital broadcasting economical.
Sources
-
Fast Fourier transform — Wikipedia, for the algorithm and its efficiency over the direct DFT. See also Cooley–Tukey FFT algorithm for the radix-2 decomposition. ↩