The Fourier Transform

1. The Core Intuition

Imagine twirling a signal around a circle at different speeds. At most speeds, positive and negative parts of the signal cancel and the centre of mass stays near the origin. But when you twirl at exactly the frequency of a component in the signal, the peaks always land on the same side — the centre of mass shifts away from the origin. The Fourier transform measures how far the centre of mass shifts at each frequency.

This beautiful geometric interpretation was popularised by Grant Sanderson (3Blue1Brown) and directly corresponds to the integral definition: we multiply the signal by a rotating complex exponential and integrate over time.

2. Fourier Series

For periodic functions, Joseph Fourier (1822) showed that any sufficiently well-behaved function f(t) with period T can be written as an infinite sum of sinusoids:

Each coefficient cₙ is a complex number whose magnitude is the amplitude of the nth harmonic and whose argument is its phase. This series converges to f(t) almost everywhere.

Example — square wave: A square wave oscillating between ±1 is the sum of odd harmonics: f(t) = (4/π)(sin t + sin(3t)/3 + sin(5t)/5 + …). Adding more terms makes the corners sharper.

3. The Fourier Transform

For non-periodic signals of finite energy, the series becomes an integral — the Fourier transform:

F(ξ) is the frequency-domain representation of f(t). The magnitude |F(ξ)| tells you how much of frequency ξ is present; the argument of F(ξ) gives the phase of that component.

Key Properties

• Linearity: FT(af + bg) = a·FT(f) + b·FT(g)
• Convolution theorem: multiplication in time = convolution in frequency (and vice versa). This makes filtering trivially fast.
• Parseval's theorem: total energy is preserved: ∫|f|² dt = ∫|F|² dξ.
• Uncertainty principle: a narrow spike in time has a broad frequency spectrum; a pure tone (narrow in frequency) lasts forever in time.

4. Discrete Fourier Transform (DFT)

Computers work with sampled data — N samples at rate f_s (Hz). The Discrete Fourier Transform takes N time-domain samples and returns N frequency-domain coefficients:

The frequency resolution is Δf = f_s / N Hz per bin. By the Nyquist theorem, the highest frequency representable is f_s / 2 — you must sample at twice the highest frequency of interest.

5. The Fast Fourier Transform (FFT)

The naive DFT requires O(N²) operations — for N = 1 000 000 that is 10¹² operations. Unusable. The Cooley–Tukey FFT algorithm (1965) exploits the recursive structure of the DFT to reduce this to O(N log N):

The key insight: if N is even, the DFT of size N can be split into two DFTs of size N/2 — one for even-indexed samples, one for odd. This "divide and conquer" is applied recursively until reaching size-1 transforms.

For N = 1 000 000, FFT needs ~20 million operations instead of 10¹². The FFT is one of the most important algorithms ever discovered. James Cooley and John Tukey published it in 1965, though Gauss had used an equivalent method in 1805.

6. Where It Appears

7. Implementing DFT in JavaScript

Here is a naive O(N²) DFT in JavaScript — correct but slow. Useful for understanding, not production.

// Naive DFT — O(N²). For N ≤ 1024 this is fast enough to demo.
function dft(signal) {
  const N = signal.length;
  const result = [];

  for (let k = 0; k < N; k++) {
    let re = 0, im = 0;
    for (let n = 0; n < N; n++) {
      const angle = (2 * Math.PI * k * n) / N;
      re += signal[n] * Math.cos(angle);
      im -= signal[n] * Math.sin(angle);
    }
    result.push({ re, im,
      freq: k,
      amp: Math.sqrt(re*re + im*im) / N,
      phase: Math.atan2(im, re)
    });
  }
  return result;
}

// Reconstruct signal from first `nTerms` DFT components
function idft(freq, nTerms, N) {
  const out = new Float64Array(N);
  for (let i = 0; i < N; i++) {
    for (let k = 0; k < nTerms; k++) {
      const angle = (2 * Math.PI * freq[k].freq * i) / N;
      out[i] += freq[k].amp * Math.cos(angle - freq[k].phase) * N;
    }
  }
  return out;
}

The Web Audio API's AnalyserNode uses a built-in FFT (power of two sizes up to 32 768) and returns magnitude data in real time.

8. Try the Simulation

The Fourier simulation lets you draw a waveform and watch its frequency spectrum in real time. You can add harmonics one by one to see how they build up a square, sawtooth, or triangle wave.