The Fast Fourier Transform
The Fast Fourier Transform is the algorithm that makes spectrum analysis possible in real time. Every SDR spectrum display, every waterfall in WSJT-X, every FFT scope on a digital oscilloscope, and every OFDM digital radio system relies on the FFT to convert a block of time-domain samples into a frequency-domain spectrum in milliseconds. The FFT does not do anything different from the Discrete Fourier Transform (DFT); it computes the same result but thousands of times faster by exploiting symmetry. Understanding the FFT explains both what you see on a spectrum display and why digital mode signals look the way they do.
Effect of windowing on FFT spectral leakage. Left: rectangular window (abrupt cut-off) produces wide sidelobes. Middle: Hann window smoothly tapers the block edges. Right: the windowed FFT shows narrow spectral lines with greatly reduced sidelobes.
View LargerThe Discrete Fourier Transform
The Discrete Fourier Transform decomposes a block of N time-domain samples into N frequency-domain components (bins). Each frequency bin answers the question: "how much of this particular frequency is present in the block of samples?" The mathematical operation is:
X[k] = ∑n=0N-1 x[n] × e−j2πkn/N
Where x[n] is the n-th time-domain sample, X[k] is the k-th frequency bin (a complex number), N is the number of samples, and k ranges from 0 to N-1. Each X[k] requires N complex multiplications and N-1 complex additions, so computing all N bins costs O(N²) operations.
The complex output X[k] encodes both the amplitude and phase of the frequency component k × (fs/N). To display a spectrum, the magnitude |X[k]| is plotted for each bin. The phase information is preserved but rarely displayed in a spectrum viewer (it is essential, however, for phase-modulated digital modes like BPSK and OFDM).
The Fast Fourier Transform Algorithm
The DFT requires O(N²) operations. For N = 1024, that is about one million complex multiply-adds. The Cooley-Tukey FFT algorithm, published in 1965, computes exactly the same DFT result but requires only O(N log₂ N) operations by recursively splitting the DFT into smaller DFTs and reusing intermediate results.
Direct DFT: N² = 1,048,576 complex operations
Cooley-Tukey FFT: N × log₂(N) = 1024 × 10 = 10,240 complex operations
Speedup factor: 1,048,576 / 10,240 ≈ 102×
For N = 65536 (16 K point FFT used in some OFDM systems), the speedup is over 4000×.
The FFT requires N to be a power of 2 (or, in more advanced implementations, a highly composite number). Real-time spectrum displays use FFT sizes from 256 to 16,384 points depending on the required frequency resolution and update rate. A larger FFT gives finer frequency resolution but takes longer to compute and requires more samples (lower time resolution).
Frequency Resolution and Time Resolution
FFT frequency resolution is determined by the sample rate and the number of points:
Δf = fs / N
Where fs is the sample rate and N is the FFT size. The time duration of the block is T = N / fs = 1 / Δf.
Δf = 48000 / 4096 = 11.7 Hz per bin
Block duration = 4096 / 48000 = 85.3 ms per FFT
This means each column of the waterfall display represents 85.3 ms of time, and adjacent frequency bins are 11.7 Hz apart.
There is a fundamental tradeoff between frequency resolution and time resolution: to get finer frequency bins, you need more samples (longer observation time), and vice versa. This is the time-frequency uncertainty principle — the same tradeoff that appears as the Heisenberg uncertainty principle in quantum mechanics and as the bandwidth-time product in analog filter theory. You cannot have both perfect frequency resolution and perfect time resolution simultaneously.
| FFT size (N) | Freq resolution at 48 kHz | Block duration | Update rate |
|---|---|---|---|
| 256 | 187.5 Hz/bin | 5.3 ms | 188 Hz |
| 1024 | 46.9 Hz/bin | 21.3 ms | 47 Hz |
| 4096 | 11.7 Hz/bin | 85.3 ms | 11.7 Hz |
| 16384 | 2.9 Hz/bin | 341 ms | 2.9 Hz |
Spectral Leakage and Windowing
The FFT assumes that the N-sample block is one period of a periodic signal. If the signal frequency does not fall exactly on a bin frequency, the block edges are discontinuous — the signal appears to start and stop abruptly. This discontinuity creates spectral leakage: energy from the signal spreads into neighboring frequency bins, raising the noise floor around the signal and potentially obscuring nearby weaker signals.
Applying a window function before the FFT solves this problem. The window multiplies each sample by a value that smoothly tapers to zero at both ends of the block, eliminating the discontinuity. The tradeoff is slightly wider frequency bins (reduced frequency resolution). The same window functions used for FIR filter design — Hann, Hamming, Blackman, Kaiser — are applied here.
Window choice for ham radio spectrum analysis:
- Rectangular (no window): best frequency resolution, high sidelobes (−13 dB). Use for CW signals when frequency accuracy matters more than sidelobe rejection.
- Hann: −32 dB sidelobes, good compromise. The default in most SDR spectrum displays.
- Blackman-Harris: −74 dB sidelobes, wider main lobe. Use when detecting weak signals near a strong signal (common on HF bands).
- Flat-top: very wide main lobe but extremely accurate amplitude measurements. Used for signal power measurements, not for visual spectrum displays.
The Waterfall Display
A waterfall display is a time-frequency visualization built from a sequence of FFT outputs. Each row of the waterfall image is one FFT spectrum (magnitude vs frequency), displayed as a row of colored pixels where color represents signal strength. New rows are added at the top (or bottom, depending on the software) and the display scrolls downward as time progresses. The result is a two-dimensional map of signal activity: horizontal axis is frequency, vertical axis is time.
The waterfall makes it trivial to identify signal types, see band activity, and find weak signals that would be invisible in a peak-hold spectrum display. Digital modes like FT8, WSPR, and JS8Call show distinctive patterns on the waterfall: FT8 signals appear as clusters of narrow tones, WSPR signals appear as slow-moving narrow lines, and CW signals appear as sharp vertical spikes that trace a dotted/dashed pattern over time.
FFT in OFDM and Digital Modes
Orthogonal Frequency Division Multiplexing (OFDM) uses the FFT not just to analyze signals but to generate them. An OFDM transmitter takes a block of data symbols, assigns each one to a different frequency bin, places the values into an inverse FFT (IFFT), and the IFFT output is transmitted as the OFDM waveform. The receiver takes the received waveform, runs a forward FFT, and reads the data symbols from the frequency bins.
OFDM is used in WiFi (802.11a/g/n), LTE, DVB-T digital television, and the ham radio digital modes Winlink Robust Packet Radio (RMS Express), FreeDV, and JS8Call. The key property of OFDM is that each sub-carrier is orthogonal to all others — their sinusoids are integer multiples of the symbol duration, so they do not interfere despite overlapping in frequency. A 1024-point IFFT simultaneously generates 512 independent sub-carriers, each carrying one data symbol, in a single operation.
FT8 and the FFT. WSJT-X decodes FT8 by taking a 15-second block of audio samples, computing a series of FFTs to build a time-frequency grid, and searching the grid for FT8 signal patterns (8-tone frequency-shift keying with known symbol timing). The FFT's O(N log N) efficiency is what makes it possible to decode dozens of simultaneous FT8 signals in the 15-second window on a Raspberry Pi.
Frequently Asked Questions
Why does the FFT spectrum show a mirror image on the negative frequency side?
The FFT of a real-valued signal (single ADC channel) produces a conjugate-symmetric output: the bins above fs/2 are mirror images of the bins below it. The upper half carries no new information and is typically discarded for display. SDR systems use complex IQ samples (two ADC channels) rather than real samples, which gives a full two-sided spectrum where positive and negative frequencies are independent — this is why an SDR waterfall shows the full bandwidth centered on the LO, while a spectrum analyzer using a real ADC shows only the positive-frequency side.
How does WSJT-X's coherent averaging improve weak-signal detection?
WSJT-X decodes FT8 by accumulating FFT magnitude over the full 15-second transmission interval and performing a joint decode over all time-frequency bins simultaneously. Random noise is incoherent — it adds as power (square root of N improvement), while the coherent signal adds linearly (N improvement). By processing 128 FFT frames coherently rather than decoding each frame independently, WSJT-X achieves a sensitivity advantage of approximately 10×log₁₀(128) ≈ 21 dB compared to single-frame analysis. This is the core reason FT8 and WSPR can recover signals that are 20–30 dB below the audible noise floor.
Test Your Knowledge
Answer the questions below to check your understanding. Every answer can be found in the lesson above.