The Fourier Transform — Decomposing Everything Into Waves

1. Fourier Series — Periodic Signals

Joseph Fourier's 1822 insight was that any periodic function f(t) with period T can be written as a sum of harmonically related sinusoids:

Using Euler's formula e^{iθ} = cos θ + i sin θ, the series takes a compact complex exponential form:

A square wave, a sawtooth, or a triangular wave — each has a distinct Fourier series. Near sharp discontinuities, the partial sum overshoots by ~9%; this is the Gibbs phenomenon, which never fully disappears no matter how many terms are included.

2. The Continuous Fourier Transform

Extending to non-periodic signals — taking T → ∞ — yields the continuous Fourier transform F(ω):

|F(f)|² is the power spectral density: how much power the signal carries per unit frequency. The total energy is preserved by Parseval's theorem:

3. Key Properties

The Fourier transform has elegant algebraic properties that make it the cornerstone of signal processing:

• Linearity: F{af + bg} = aF{f} + bF{g}
• Time shift: a delay of t₀ multiplies the spectrum by e^{-iωt₀} — changing phase without affecting magnitude.
• Frequency shift (modulation): multiplying f(t) by e^{iω₀t} shifts the spectrum by ω₀ — the basis of AM radio modulation.
• Convolution theorem: time-domain convolution equals multiplication in the frequency domain: F{f * g} = F{f} · F{g}. This turns slow O(N²) convolutions into fast O(N log N) FFT multiplications.
• Differentiation: F{f′(t)} = iω · F{f}(ω) — derivatives become polynomial multiplications, turning differential equations into algebraic ones.
• Symmetry (Hermitian): for real signals, F(−f) = F*(f), so the negative-frequency half is redundant.
• Uncertainty principle: Δt · Δω ≥ 1/2 — a signal cannot be simultaneously localized in both time and frequency. (This is the same Heisenberg uncertainty principle, which has a mathematical rather than quantum origin.)

4. The Discrete Fourier Transform (DFT)

Real-world signals are sampled at discrete time steps. Given N samples x[0]…x[N-1] spaced Δt apart, the DFT produces N complex frequency bins X[0]…X[N-1]:

The DFT wraps around: bins k and k±N represent the same frequency. Bins 0 to N/2 cover 0 Hz to the Nyquist limit; bins N/2+1 to N-1 represent negative frequencies.

5. The Fast Fourier Transform (FFT)

The naive DFT requires O(N²) operations — too slow for N = 10⁶ or larger. The Cooley-Tukey FFT (1965) exploits the recursive structure of the DFT to compute it in O(N log₂ N).

The key insight: split the N-point DFT into two N/2-point DFTs applied to even-indexed and odd-indexed samples:

// Radix-2 Cooley-Tukey FFT — O(N log N)
function fft(re, im) {
  const N = re.length;
  // Bit-reversal permutation
  for (let i = 1, j = 0; i < N; i++) {
    let bit = N >> 1;
    for (; j & bit; bit >>= 1) j ^= bit;
    j ^= bit;
    if (i < j) { [re[i], re[j]] = [re[j], re[i]]; [im[i], im[j]] = [im[j], im[i]]; }
  }
  // Butterfly stages
  for (let len = 2; len <= N; len <<= 1) {
    const ang = -2 * Math.PI / len;
    const wRe = Math.cos(ang), wIm = Math.sin(ang);
    for (let i = 0; i < N; i += len) {
      let curRe = 1, curIm = 0;
      for (let k = 0; k < len / 2; k++) {
        const u = re[i+k], v = im[i+k];
        const tRe = curRe*re[i+k+len/2] - curIm*im[i+k+len/2];
        const tIm = curRe*im[i+k+len/2] + curIm*re[i+k+len/2];
        re[i+k] = u + tRe; im[i+k] = v + tIm;
        re[i+k+len/2] = u - tRe; im[i+k+len/2] = v - tIm;
        const nr = curRe*wRe - curIm*wIm; curIm = curRe*wIm + curIm*wRe; curRe = nr;
      }
    }
  }
}

6. 2-D Fourier Transforms

Images are 2-D signals. The 2-D DFT applies 1-D DFTs first along rows, then along columns (separability):

The 2-D FFT is used in:

• JPEG encoding: 8×8 block DCT (cosine-only variant) for image compression
• MRI reconstruction: the scanner natively measures k-space (2-D Fourier space); an inverse 2-D FFT reconstructs the image
• Telescope imaging: interferometric arrays measure Fourier components of the sky; CLEAN and VLBI imaging are inverse-problem applications

7. Applications Across Science

Audio (MP3 / AAC)

Psychoacoustic models quantise frequency bins according to the masking threshold — sounds near a loud tone are inaudible to human ears and can be severely compressed. The convolution theorem allows fast FIR filtering for equalization and reverb.

Telecommunications (OFDM)

Orthogonal Frequency-Division Multiplexing divides bandwidth into many subcarriers — each modulated separately. The IFFT converts frequency-domain data to a time-domain waveform at the transmitter; the receiver applies the FFT to recover the data. Used in WiFi (802.11), LTE, 5G, and digital TV (DVB-T).

Crystallography

X-ray diffraction from a crystal measures the magnitude (but not phase) of its 3-D Fourier transform. The "phase problem" — determining the missing phase information — occupied crystallographers for decades. Modern ab initio methods solve structures with ~10,000 atoms.

Partial Differential Equations

The heat equation ∂u/∂t = α ∇²u transforms to dU/dt = −α ω² U — a simple first-order ODE in frequency space with solution U(ω,t) = U(ω,0) e^{−αω²t}. Higher-frequency components decay faster — physical heat smoothing captured in one line of math.

Quantum Mechanics

Position and momentum wavefunctions are Fourier transform pairs. The uncertainty principle Δx·Δp ≥ ℏ/2 is an instance of the time-frequency uncertainty principle — a purely mathematical property of the Fourier transform.