Every signal — a piece of music, an MRI scan, a radio wave — can be expressed as a sum of simple sine waves at different frequencies. Fourier analysis makes this decomposition precise, and the Fast Fourier Transform makes it computationally tractable, enabling everything from MP3 compression to 5G communications.
A signal is simply a quantity that varies with time (or space). An audio waveform records air pressure over time; an electrocardiogram traces electrical potential across the heart; a photograph stores light intensity across a two-dimensional grid. These signals look complicated in their natural representation — the time domain — but often have a much simpler structure when viewed through a different lens.
Joseph Fourier's key insight, articulated in his 1822 treatise on heat conduction, was that any periodic function can be written as an infinite sum of sines and cosines whose frequencies are integer multiples (harmonics) of a fundamental frequency. This superposition principle is not just a mathematical curiosity: it reflects the fact that sinusoidal oscillations are the natural modes of vibration for strings, membranes, electrical circuits and quantum mechanical systems.
The crucial distinction between the two representations is what each reveals: the time domain shows when things happen — where peaks and troughs occur, how quickly the signal changes. The frequency domain shows what frequencies are present — which sinusoidal components make up the signal, each with its own amplitude and phase. A pure musical note is a single spike in the frequency domain; a chord is several spikes; noise is energy spread across all frequencies.
Periodic signals — repeating indefinitely — have a discrete set of frequencies called a Fourier series: a fundamental plus harmonics. Aperiodic (one-off) signals have a continuous spectrum: the Fourier transform, where energy is spread across a continuum of frequencies. In practice, signals are always finite in duration, so we work with windowed segments and the Discrete Fourier Transform.
The continuous Fourier transform converts a time-domain signal x(t) to its frequency-domain representation X(f). The transform and its inverse are defined by the integral pair:
The complex exponential e^{-i2πft} is the key: by Euler's formula it equals
cos(2πft) − i·sin(2πft), so the integral projects x(t) onto a sinusoidal basis function
at frequency f. The result X(f) is a complex number for each frequency: its magnitude
|X(f)| gives the amplitude spectrum (how much of each frequency is present)
and its argument arg(X(f)) gives the phase spectrum (the timing offset of
that frequency component relative to zero).
In practice, signals are sampled at discrete intervals. The Discrete Fourier Transform (DFT) takes N equally-spaced samples and returns N complex frequency coefficients:
Here k indexes discrete frequencies: k=0 is the DC component (average value), k=1 is the fundamental frequency (one full cycle over N samples), and k=N/2 is the highest representable frequency (the Nyquist frequency). The Nyquist-Shannon sampling theorem states that to faithfully capture a signal containing frequencies up to fmax, one must sample at a rate of at least 2·fmax samples per second. Sampling below this rate causes aliasing — high-frequency content folds back and masquerades as lower frequencies, irreversibly corrupting the signal. Audio CDs sample at 44,100 Hz, sufficient to capture frequencies up to 22,050 Hz — comfortably beyond the human hearing limit of roughly 20,000 Hz.
Computing the DFT directly from the definition requires O(N²) complex multiplications: for each of the N output frequencies, we sum over all N input samples. For a one-second audio clip sampled at 44,100 Hz, that means N = 44,100, and N² ≈ 1.9 billion operations. For a 4K video frame (N ≈ 8 million pixels), direct computation is entirely impractical.
The Cooley-Tukey FFT algorithm, published in 1965 (though related ideas go back to Gauss), reduces the cost to O(N log N) through a brilliant divide-and-conquer approach. The key observation is that the DFT of size N can be expressed in terms of two DFTs of size N/2 — one over the even-indexed input samples and one over the odd-indexed samples — combined by a simple butterfly operation:
The complex factor e^{-i2πk/N} is called the twiddle factor. By applying this splitting recursively — halving the problem at each stage — we reduce the total work to N/2 · log₂(N) butterfly operations. Each stage requires exactly N/2 multiplications and N additions; with log₂(N) stages, the total is O(N log N). The twiddle factors are precomputed once and stored, so each butterfly is just two additions and one multiplication.
The radix-2 FFT requires N to be a power of 2 (512, 1024, 2048, ...). Practical implementations like FFTW use mixed-radix factorizations to handle arbitrary N efficiently, automatically choosing the best algorithm for the given size at runtime.
The Fourier transform and FFT underpin an extraordinary range of technologies. Almost every system that processes signals — natural or artificial — relies on frequency-domain analysis at some stage of its pipeline.
Graphic equalizers split audio into frequency bands and allow independent gain control of each — a direct application of Fourier decomposition. Pitch detection algorithms identify the fundamental frequency of a voice or instrument by locating the dominant peak in the spectrum. Perceptual audio codecs like MP3 and AAC exploit a psychoacoustic model: they use the FFT to identify frequency components that are masked by louder nearby components or fall below the hearing threshold, then discard or heavily quantize those components. This is why an MP3 at 128 kbps sounds nearly identical to an uncompressed WAV at 1,411 kbps.
JPEG compression operates on 8×8 pixel blocks of an image. Each block is transformed using the Discrete Cosine Transform (DCT) — a real-valued variant of the DFT that is particularly efficient for natural images because it avoids the boundary artefacts of the DFT. The resulting 64 frequency coefficients represent the block as a superposition of spatial frequency patterns: the top-left coefficient is the average brightness (DC), while coefficients toward the bottom-right represent increasingly fine detail. High-frequency coefficients are then quantized heavily (or set to zero), since the human visual system is less sensitive to fine spatial detail than to low-frequency structure. The result is dramatic file-size reduction with acceptable visual quality.
Magnetic Resonance Imaging scanners do not collect images directly. Instead, radiofrequency pulses and gradient magnetic fields cause hydrogen nuclei to emit signals at frequencies encoding their spatial positions. The scanner records data in k-space — the frequency domain of the anatomical image. An inverse FFT applied to the collected k-space data reconstructs the spatial image of the body's tissue. Without the FFT, MRI reconstruction would take hours rather than seconds.
Orthogonal Frequency-Division Multiplexing (OFDM) is the modulation scheme used in 4G LTE, 5G NR, Wi-Fi, and digital television. Rather than transmitting on a single carrier frequency, OFDM splits the available bandwidth into hundreds or thousands of narrow, orthogonal sub-carriers. Data bits are encoded onto each sub-carrier independently. At the transmitter, an Inverse FFT combines all sub-carriers into a time-domain waveform for transmission; at the receiver, an FFT separates them back. OFDM is highly robust against multipath fading and interference, which is why it dominates modern broadband wireless standards.
Fourier analysis reveals periodicity hidden in noisy data. Astronomers use spectral analysis to detect exoplanet transits as periodic dips in stellar brightness, and to measure stellar rotation from light-curve periodicities. Seismologists decompose earthquake records into normal modes to study Earth's interior. Neuroscientists identify brain rhythms (alpha, beta, gamma waves) in EEG recordings. The convolution theorem — which states that convolution in the time domain equals pointwise multiplication in the frequency domain — enables fast polynomial multiplication, efficient digital filtering, and the O(N log N) computation of cross-correlations used in signal matching and radar processing.
Browse interactive wave, oscillation and signal-processing simulations — see Fourier decomposition and frequency analysis brought to life in real time.
A Fourier series represents a periodic function as an infinite sum of sinusoids: f(t) = a₀/2 + Σ[aₙcos(nωt) + bₙsin(nωt)]. The coefficients aₙ and bₙ are computed from integrals of f multiplied by cos/sin basis functions. Fourier series converge to f(t) at all continuous points (and to the average at discontinuities — Gibbs phenomenon). They're the foundation for analyzing periodic signals and solving PDEs with periodic boundary conditions.
The Continuous Fourier Transform (CFT) applies to continuous functions defined over all time: F(ω) = ∫f(t)e^(-iωt)dt. The Discrete Fourier Transform (DFT) applies to finite sequences of N samples: X[k] = Σx[n]e^(-2πikn/N). The DFT is what computers compute. The CFT is the theoretical ideal; the DFT approximates it when signals are band-limited and properly sampled. The FFT computes the DFT in O(N log N) instead of O(N²).
The convolution theorem states that convolution in one domain equals pointwise multiplication in the other domain. In the time domain: (f * g)(t) = ∫f(τ)g(t-τ)dτ. In the frequency domain: ℱ{f*g}(ω) = F(ω)·G(ω). This means filtering can be done by: FFT the signal → multiply by the filter's frequency response → inverse FFT. This is dramatically faster than direct convolution for long signals.
The Fourier uncertainty principle states that a function and its Fourier transform cannot both be sharply concentrated: σ_t · σ_ω ≥ 1/2, where σ_t and σ_ω are the time and frequency spreads. A short time-domain pulse has a wide frequency spectrum; a pure sinusoid (narrow frequency) lasts forever in time. This is the mathematical basis for Heisenberg's uncertainty principle in quantum mechanics (σ_x · σ_p ≥ ℏ/2).
The Short-Time Fourier Transform (STFT) analyzes how the frequency content of a signal changes over time. A sliding window function is multiplied with the signal, and FFT is computed for each window position. The result — a spectrogram — shows time on one axis and frequency on the other. Window length controls the time-frequency resolution trade-off: short windows give better time resolution but worse frequency resolution.
While Fourier analysis uses infinite sinusoids as basis functions (good frequency resolution, no time localization), wavelet analysis uses short, oscillatory basis functions (wavelets) localized in both time and frequency. Wavelets provide multi-resolution analysis — coarse approximation plus detail at each scale. Applications include image compression (JPEG 2000 uses wavelets), denoising, ECG analysis, and seismic signal processing where features occur at multiple scales.
The Gibbs phenomenon is an overshoot in Fourier series approximation near a jump discontinuity. No matter how many harmonics are summed, the partial sum overshoots the true value by about 9% of the jump height at the discontinuity. It doesn't disappear as more terms are added — it only moves closer to the discontinuity. Gibbs phenomenon affects digital audio, image processing, and numerical PDE solutions near sharp features.
Musical instruments produce sounds that are superpositions of harmonic overtones — integer multiples of the fundamental frequency. Fourier analysis decomposes any musical sound into its component frequencies, identifying the fundamental pitch and harmonic content. Timbre (the difference in sound between a violin and piano playing the same note) is determined by which harmonics are present and their relative amplitudes. Music synthesizers generate sounds by adding harmonics (additive synthesis) or filtering white noise (subtractive synthesis).
The DCT transforms a signal into a sum of cosine functions at different frequencies. Unlike the DFT, it only uses real-valued cosines (no complex exponentials) and has favorable energy compaction: most signal energy concentrates in a few low-frequency coefficients. JPEG uses 8×8 block DCT for image compression — it transforms each block to frequency domain, quantizes (discards) high-frequency coefficients that the eye barely notices, then entropy-encodes the remaining coefficients.
The Fourier transform of a Gaussian is another Gaussian: ℱ{e^(-at²)}(ω) = √(π/a) · e^(-ω²/4a). Gaussians are self-similar under the Fourier transform — a Gaussian in time produces a Gaussian in frequency. Narrower Gaussians in time produce wider Gaussians in frequency, demonstrating the uncertainty principle. This property makes Gaussians ideal for windowing (minimizing time-frequency uncertainty) and is central to quantum mechanics (coherent states are Gaussian wavepackets).