Field Guide · algorithm

Also known as: DFT

The discrete Fourier transform (DFT) is the finite, sampled form of the Fourier transform: it takes a block of N evenly spaced samples and returns N complex numbers, each describing the amplitude and phase of one frequency component present in that block.1 Where the continuous transform integrates over all time and yields a continuous spectrum, the DFT sums over a finite record and produces a discrete spectrum — one value per bin — which is exactly what a computer can hold and what a software-defined radio needs to see its band.

N time samples DFT N frequency bins frequency →
The DFT maps a finite record of N samples into N discrete frequency bins — the spectrum a software radio plots as a waterfall.

How it works

Given complex samples x[0] … x[N-1], the DFT computes each output bin as a sum:

X[k] = Σ x[n] · e^(-j2πkn/N) for n = 0 … N-1.

Each output X[k] is the correlation of the input against a complex sinusoid (“twiddle factor”) that completes exactly k whole cycles across the block. If the signal contains energy at that frequency, the products line up and the sum is large; if not, they cancel. The result X[k] is complex — its magnitude gives the component’s amplitude and its angle gives the phase.

  • Bin spacing. For a block of N samples taken at sample rate fs, bin k sits at frequency k · fs / N. The resolution — the gap between adjacent bins — is therefore fs / N hertz. More samples (a longer record) means finer resolution but a longer observation time; this is the fundamental time–frequency trade.
  • Bin range and aliasing. The N bins span 0 to fs, with the upper half representing negative frequencies for real input. Anything above the Nyquist limit folds back down, so aliasing sets what the transform can honestly show.
  • Windowing. A raw block has hard edges, and the DFT assumes the block repeats forever. The discontinuity smears energy across bins (spectral leakage), so a window function is normally applied first.

Relation to the FFT

The direct sum above costs O(N^2) operations — one full inner product per bin. The fast Fourier transform is not a different transform; it is a family of algorithms that compute the same DFT in O(N log N) by recursively reusing shared twiddle-factor products. For the block sizes used in a real waterfall (1024, 4096, 65536 points), the FFT is thousands of times faster, which is why practical SDR software never runs the naive sum — it always calls an FFT. When only a handful of specific bins are needed rather than the whole spectrum, the Goertzel algorithm evaluates individual DFT terms even more cheaply than a full FFT.

Relevance to SDR

The DFT is the workhorse of spectral display and detection. Every SDR waterfall, panadapter, and spectrum plot is a stream of DFTs (via FFT) of the incoming I/Q data, one block after another, stacked over time. Energy detection — deciding whether a channel is busy — compares the magnitude of the relevant bins against a threshold. Averaged DFTs form the periodograms behind Welch’s method for power-spectral-density estimation, and DFT-based fast convolution underlies efficient filtering and channelization.

GopherTrunk uses FFT-based spectral processing to visualise wideband captures and to help locate control channels within a monitored band; the transform it computes there is, by definition, the DFT. The decode chain proper leans more on time-domain filtering and symbol recovery, but the DFT remains the lens through which the operator and the scanner first see the spectrum.

Sources

  1. Discrete Fourier transform — Wikipedia, on the definition, bin structure, and relationship to the continuous transform and the FFT. ↩

See also