Decomposing Signals with the Discrete Fourier Transform

A prism doesn’t analyze light—it separates it. White light enters as a mixture, exits as a spectrum. The Discrete Fourier Transform does the same for sampled signals: it takes time-domain data (a waveform) and decomposes it into frequency-domain components (which frequencies are present, at what amplitudes).

The mathematics rest on Euler’s formula: $e^{i\theta} = \cos\theta + i\sin\theta$. Each frequency bin $k$ is computed by correlating the input signal against a complex sinusoid at that frequency. Here’s the direct approach in TypeScript:

function dft(samples: number[]): [number, number][] {
  const N = samples.length;
  return Array.from({ length: N }, (_, k) => {
    let real = 0, imag = 0;
    for (let n = 0; n < N; n++) {
      const angle = (-2 * Math.PI * k * n) / N;
      real += samples[n] * Math.cos(angle);
      imag += samples[n] * Math.sin(angle);
    }
    return [real / N, imag / N];
  });
}

const signal = [1, 0, -1, 0];  // 440 Hz sine at 1760 Hz sample rate
const spectrum = dft(signal);
console.log(spectrum.map(([r, i]) => Math.hypot(r, i)));
// [0, 0.5, 0, 0.5]  — energy at bins 1 and 3 (quarter-period wave)

OCaml handles the complex arithmetic explicitly, building each bin through a fold:

let dft samples =
  let n = Array.length samples in
  Array.init n (fun k ->
    Array.fold_left (fun (re, im) (i, x) ->
      let angle = -2. *. Float.pi *. float k *. float i /. float n in
      (re +. x *. cos angle, im +. x *. sin angle)
    ) (0., 0.) (Array.mapi (fun i x -> (i, x)) samples)
  ) |> Array.map (fun (r, i) -> (r /. float n, i /. float n))

This is the $O(N^2)$ formulation—every output bin requires summing over all input samples. Cooley and Tukey’s FFT (1965) exploited symmetries to cut this to $O(N \log N)$, which made real-time spectral analysis feasible on 1970s minicomputers. The algorithm itself is older (Gauss, 1805), but digital signal processors turned it into infrastructure: vocoders, sonar, MP3 encoding, radio astronomy.

The output isn’t the signal reconstructed—it’s the signal decomposed, each bin a frequency component you can inspect, filter, or modify independently. Time-domain and frequency-domain are two views of the same data. The prism doesn’t change the light; it shows you what was always there.