The Fast Fourier Transform
The Fast Fourier Transform is the algorithm that makes spectrum analysis possible in real time. Every audio spectrum analyzer, every waterfall display, every FFT scope on a digital oscilloscope, and every OFDM wireless 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.
Choosing a window for spectrum analysis:
- Rectangular (no window): best frequency resolution, high sidelobes (−13 dB). Use for transient signals that fit entirely inside the block, or when frequency resolution matters more than sidelobe rejection.
- Hann: −32 dB sidelobes, good compromise. The default in many spectrum displays.
- Blackman-Harris: −74 dB sidelobes, wider main lobe. Use when detecting weak signals or small harmonics near a strong signal.
- 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 easy to identify signal types, see activity over time, and find weak or intermittent signals that would be invisible in a single spectrum. Audio analysis tools and many oscilloscopes and spectrum analyzers offer waterfall displays: a steady carrier appears as a vertical line, a frequency-hopping signal such as Bluetooth as scattered dashes, a sweeping chirp as a diagonal line, and an intermittent interference source as a pattern that comes and goes.
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 Wi-Fi (802.11a/g/n/ac/ax), 4G LTE and 5G, DVB-T digital television, DAB digital radio and power-line networking. The key property of OFDM is that each subcarrier is orthogonal to all others — their sinusoids are integer multiples of the symbol duration — so the receiver can separate them perfectly with one FFT, even though their spectra overlap.
The FFT in instruments. A digital oscilloscope's FFT function, a sound-card spectrum analyzer and a low-cost USB analyzer all use the same algorithm: capture N samples, apply a window, compute an N-point FFT and display the magnitude of each bin. Understanding bin width (sample rate / N) and windowing explains why the display behaves as it does when you change the timebase or the FFT length.
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. Digital receivers 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 IQ waterfall shows the full bandwidth centered on the LO, while a spectrum analyzer using a real ADC shows only the positive-frequency side.
How can an FFT show a signal that is below the noise on an oscilloscope?
Each FFT bin collects only the noise within its own narrow bandwidth, while a pure tone puts all of its energy into one bin. Doubling the FFT length halves the bin width and halves the noise power per bin, lowering the noise floor by 3 dB, while the tone's bin stays the same. Averaging many FFTs reduces the random fluctuation of the noise further. That is how a sound-card analyzer can show harmonics 100 dB below the fundamental, and why the noise floor drops on an FFT display when you increase the record length.
Test Your Knowledge
Answer the questions below to check your understanding of this lesson. Every answer can be found in the lesson above.