Discrete Fourier Transform

3 min read#fourier

The Fourier transform of sampled data — and the Nyquist limit and aliasing that sampling forces upon us.

Contents

Discrete Fourier Transform

Computers cannot integrate a signal over all of continuous time; they hold a finite list of samples. The discrete Fourier transform (DFT) is the version of the Fourier Transform built for that reality. Given N samples x_0,\dots,x_{N-1} it returns N frequency coefficients:

X_k = \sum_{n=0}^{N-1} x_n\,e^{-2\pi i kn/N},\qquad k = 0,\dots,N-1.

Computed naively this costs N^2 operations; the celebrated fast Fourier transform (FFT) reorganizes the same arithmetic into N\log N, and that single speedup is what put Fourier analysis inside every phone, radio, and oscilloscope.

The price of sampling: Nyquist and aliasing

Sampling is not free. If you measure a signal only every \Delta t seconds, you can faithfully represent frequencies only up to the Nyquist limit f_{\text{Nyq}} = \tfrac{1}{2\Delta t} — half the sampling rate. Anything faster cannot be told apart from something slower: a high frequency, sampled too coarsely, masquerades as a low one. This impostor is called an alias.

Below, the faint curve is a genuine high-frequency sine. The dots are samples taken too sparsely, and the bold line connects them — a slow, lazy wave that was never really there. Your eye, like the DFT, is fooled.

Faint: a true high-frequency sine. Dots: coarse samples. Bold: the low-frequency 'alias' they imply — a frequency that does not exist in the signal.

Living with the limit

The cure for aliasing is to remove offending frequencies before sampling with an anti-aliasing filter, or to sample fast enough that everything real sits below Nyquist. The same trap explains why wagon wheels spin backward on film and why a poorly chosen audio sample rate adds phantom tones. Once the DFT has the samples, its output is read as a Spectrum — but only the part below Nyquist can be trusted.

See also

Related topics

  • Fourier TransformThe generalization of the Fourier series to non-periodic signals — an integral that resolves any signal into a continuous band of frequencies.
  • Frequency DomainThe second of the two equivalent views of a signal — describing it by which frequencies it contains rather than by how it varies in time.
  • SpectrumThe magnitude of a signal's frequency content — the map of where its energy lives, read as a landscape of peaks.
  • Fourier AnalysisAny signal is a sum of pure sinusoids — and reading it as such turns the tangled language of time into the clean language of frequency.
  • Uncertainty PrincipleA signal cannot be sharply localized in both time and frequency at once — the tighter one view, the broader the other.
  • ConvolutionThe sliding-overlap operation that blends two signals — and which, magically, becomes simple multiplication in the frequency domain.

Referenced by