The Fourier Transform

How mathematics hears which notes are hidden in a chord.

An instrument plays three notes at once, but you hear a single chord. Physically, all three notes create pressure waves that sum together and hit your eardrum as one. Your brain is somehow able to recognize the three distinct frequencies hidden in that single wave. The mechanism behind how the brain does this is an extremely complicated topic, but getting machines to decompose the signal is quite straightforward, and this post explains how it is done. The core mathematical operation doing signal decomposition is called the Fourier Transform.

Sound is a sum of sinusoids

A pure tone (a tuning fork or a whistle) is a sinusoid. A sinusoid is a smooth, repetitive oscillation at a single frequency. If you stack multiple pure tones on top of each other, you get a chord. The sounds you hear in your ear on a daily basis are typically a sum of hundreds of pure tones. When looking at the waveforms of chords, it looks like pure noise (see Figure 1), but it isn’t noise. The pure tones are just hiding in the sum of frequencies of the chord signal.

Below you can hear three different pure tones and the chord they produce when combined. Then below the media players, you can see the wave forms of the signals individually and then the signal that is produced when combining the three pure tones.

fs = 8000
t = np.linspace(0, 1.5, int(fs * 1.5), endpoint=False)
note_freqs = [300, 700, 1200]  # Hz ratio 3:7:12, matching the figure below
note_amps = [1.0, 0.7, 0.4]
chord = sum(a * np.cos(2 * np.pi * f * t) for f, a in zip(note_freqs, note_amps))

Note 1 (low)

Note 2 (mid)

Note 3 (high)

The chord

Figure 1: Three pure tones (top three panels) add up to one complicated waveform (bottom). The individual notes are nowhere to be seen in the mixture.

How to detect a hidden frequency

The core intuition behind finding the frequencies in a chord is that if the frequency f is present in the signal, then the signal and a pure tone at f should “agree” on average. “Agreeing” in this context means that when the test pure tone is positive, the signal tends to be positive, and when the test tone is negative, the signal also tends to be negative.

The mathematical way to measure this agreement is the dot product. In practice, you multiply the signal and the test sinusoid at each discrete time point and then sum all the multiplications together (aka you take the dot product). If the products are consistently positive (or consistently negative) the sum is large and this means that the test frequency can be found from the original signal. If the test frequency doesn’t match with the original signal, the products alternate in sign and cancel out and the sum collapses to zero. This is the entire intuition of the fourier transform. The fourier transform just tests every single frequency and then returns a list of frequencies present.

The formula

For a discrete signal x[0], x[1], \ldots, x[N-1], the k-th Fourier coefficient is:

X[k] = \sum_{n=0}^{N-1} x[n]\, e^{-2\pi \mathrm{i} k n / N} \tag{1}

where e^{-2\pi \mathrm{i} k n / N} is a complex sinusoid at frequency k. This comes from Euler’s formula: e^{\mathrm{i}\theta} = \cos \theta + \mathrm{i}\sin \theta. Multiplying x[n] by e^{-2\pi \mathrm{i} k n / N} and summing is the exact definition of computing the dot product of the signal and the test sinusoid at frequency k.

The result X[k] is a complex number. Its magnitude |X[k]| tells you how much of frequency k is present. But why is the result a complex number? The reason for this is that with e^{-2\pi \mathrm{i} kn/N} = \cos(2\pi kn/N) - \mathrm{i}\sin(2\pi kn/N), the real part measures correlation with the cosine and the imaginary part with the sine. Together they capture both the amplitude and phase of each frequency in a single number. Repeating for all k = 0, 1, \ldots, N-1 gives the full spectrum of which frequencies are in the signal and how strong each one is.

Geometric intuition: winding a signal around a circle

There is a nice geometric way to understand what Equation 1 is doing. The idea is that you take the signal and wind it around a circle. At sample n, place the value x[n] on the complex plane, rotated by k full turns spread over N samples. Then each point becomes a point in 2D space. The sum X[k] is the centre of mass of all these points.

When k matches a hidden frequency, the wound samples bunch up on one side of the origin (large |X[k]|). When k does not match a hidden frequency, the samples scatter evenly around the circle (small |X[k]|). From the figure below, you can see the chord signal that is wound around a circle. Changing the frequency k shows on which frequencies |X[k]| becomes non-zero. The figure below uses a synthetic 256-sample signal with notes at bin indices k = 3, 7, 12 which is the same ratio as the chord, but scaled to a different absolute pitch to simplify the visual.

viewof wind_f = {
  const wrap = html`<div style="font-family:inherit;font-size:13px;">
    <div style="display:flex;justify-content:space-between;align-items:center;margin-bottom:4px;">
      <span style="color:#d1d5db;">Test frequency k</span>
      <input type="number" min="0" max="20" step="0.05" value="3"
        style="width:68px;background:#1f2937;color:#f9fafb;border:1px solid #4b5563;
               border-radius:4px;padding:2px 6px;font-size:13px;text-align:right;">
    </div>
    <input type="range" min="0" max="20" step="0.05" value="3"
      style="width:100%;accent-color:#7eb8f7;cursor:pointer;">
  </div>`;

  const slider = wrap.querySelector("input[type=range]");
  const number = wrap.querySelector("input[type=number]");

  const emit = () => {
    wrap.value = +slider.value;
    wrap.dispatchEvent(new Event("input", {bubbles: true}));
  };

  slider.oninput = () => { number.value = slider.value; emit(); };
  number.oninput = () => {
    const v = Math.max(0, Math.min(20, +number.value));
    slider.value = v;
    emit();
  };

  wrap.value = 3;
  return wrap;
}

Figure 2: Three-panel interactive: signal x[n] (top), signal wound around a circle at frequency k (middle), full spectrum |X[k]| (bottom). Drag the slider to k = 3, 7, or 12 and watch the winding bunch up while the orange dot in the spectrum jumps to a peak.

signalX = {
  const N = winding_N;
  return Array.from({length: N}, (_, n) =>
    winding_freqs.reduce((s, f, i) => s + winding_amps[i] * Math.cos(2 * Math.PI * f * n / N), 0)
  );
}

specK = {
  const N = winding_N;
  return Array.from({length: 21}, (_, k) => {
    let re = 0, im = 0;
    for (let n = 0; n < N; n++) {
      re += signalX[n] * Math.cos(-2 * Math.PI * k * n / N);
      im += signalX[n] * Math.sin(-2 * Math.PI * k * n / N);
    }
    return { k, mag: Math.sqrt(re * re + im * im) / N };
  });
}

layout = ({
  W: 520, flatH: 148, gapY: 14, circD: 300, gapY2: 18, specH: 150,
  totalH: 148 + 14 + 300 + 18 + 150
})

drawSignalPanel = (svg, { x, components, compColors, compAlpha, wind_f, isMatch, N }) => {
  const { W, flatH } = layout;
  const xMax = d3.max(x, v => Math.abs(v));
  const xPad = N * 0.10;
  const fm   = { l: 14, r: 14, t: 20, b: 8 };
  const xSc  = d3.scaleLinear([0, N - 1 + xPad], [fm.l, W - fm.r]);
  const ySc  = d3.scaleLinear([-xMax * 1.2, xMax * 1.2], [flatH - fm.b, fm.t]);
  const y0   = ySc(0);

  svg.append("text")
    .attr("x", W / 2).attr("y", 13).attr("text-anchor", "middle")
    .style("fill", "#9ca3af").style("font-size", "11px")
    .text("the chord signal");

  if (wind_f >= 1) {
    const step = N / wind_f;
    const markerColor = isMatch ? "#6ddc8b" : "#6b7280";
    for (let j = 0; j * step <= N - 1 + xPad; j++) {
      const mn = Math.round(j * step);
      if (mn >= 0)
        svg.append("line")
          .attr("x1", xSc(mn)).attr("x2", xSc(mn))
          .attr("y1", fm.t).attr("y2", flatH - fm.b)
          .attr("stroke", markerColor).attr("stroke-width", 1.2)
          .attr("stroke-dasharray", "3,3").attr("opacity", 0.75);
    }
  }

  svg.append("line")
    .attr("x1", fm.l).attr("x2", W - fm.r).attr("y1", y0).attr("y2", y0)
    .attr("stroke", "#374151").attr("stroke-width", 1);

  const compLine = d3.line().x((_, n) => xSc(n)).y(v => ySc(v)).curve(d3.curveLinear);
  components.forEach((c, i) =>
    svg.append("path").datum(c).attr("d", compLine)
      .attr("fill", "none").attr("stroke", compColors[i])
      .attr("stroke-width", 1.5).attr("opacity", compAlpha[i])
  );

  x.forEach((v, n) => {
    const cx = xSc(n), cy = ySc(v);
    svg.append("line")
      .attr("x1", cx).attr("y1", y0).attr("x2", cx).attr("y2", cy)
      .attr("stroke", "#6b7280").attr("stroke-width", 0.8)
      .attr("opacity", 0.12 + 0.38 * Math.abs(v) / xMax);
  });
}

drawWindingPanel = (svg, { wound, cm_x, cm_y, wind_f }) => {
  const { W, flatH, gapY, circD } = layout;
  const circY0 = flatH + gapY;
  const margin = 18;
  const R      = (circD - 2 * margin) / 2;
  const cx0    = W / 2;
  const cy0    = circY0 + circD / 2;
  const scale  = R / 2.2;

  svg.append("text")
    .attr("x", cx0).attr("y", circY0 + 13).attr("text-anchor", "middle")
    .style("fill", "#9ca3af").style("font-size", "11px")
    .text("wound around a circle");

  svg.append("circle")
    .attr("cx", cx0).attr("cy", cy0).attr("r", scale)
    .attr("fill", "none").attr("stroke", "#374151").attr("stroke-width", 1);
  svg.append("line").attr("x1", cx0 - R).attr("x2", cx0 + R)
    .attr("y1", cy0).attr("y2", cy0).attr("stroke", "#374151").attr("stroke-width", 1);
  svg.append("line").attr("x1", cx0).attr("x2", cx0)
    .attr("y1", cy0 - R).attr("y2", cy0 + R).attr("stroke", "#374151").attr("stroke-width", 1);

  const isInt   = Math.abs(wind_f - Math.round(wind_f)) < 0.01;
  const woundPts = isInt ? [...wound, wound[0]] : wound;
  const wLine = d3.line()
    .x(d => cx0 + d.px * scale).y(d => cy0 - d.py * scale).curve(d3.curveLinear);
  svg.append("path").datum(woundPts).attr("d", wLine)
    .attr("fill", "none").attr("stroke", "#7eb8f7")
    .attr("stroke-width", 1.4).attr("opacity", 0.75);

  svg.append("line")
    .attr("x1", cx0).attr("y1", cy0)
    .attr("x2", cx0 + cm_x * scale).attr("y2", cy0 - cm_y * scale)
    .attr("stroke", "#f0956a").attr("stroke-width", 2.5).attr("opacity", 0.95);
  svg.append("circle")
    .attr("cx", cx0 + cm_x * scale).attr("cy", cy0 - cm_y * scale)
    .attr("r", 6).attr("fill", "#f0956a");
}

drawSpectrumPanel = (svg, { specK, wind_f, mag, comp_freqs, compColors }) => {
  const { W, flatH, gapY, circD, gapY2, specH } = layout;
  const specY0     = flatH + gapY + circD + gapY2;
  const specFm     = { l: 36, r: 14, t: 18, b: 32 };
  const specMaxMag = d3.max(specK, d => d.mag);
  const kSc        = d3.scaleLinear([0, 20], [specFm.l, W - specFm.r]);
  const magSc      = d3.scaleLinear([0, specMaxMag * 1.3],
                       [specY0 + specH - specFm.b, specY0 + specFm.t]);
  const barW     = (kSc(1) - kSc(0)) * 0.65;
  const specBase = specY0 + specH - specFm.b;

  svg.append("text")
    .attr("transform", `translate(9, ${specY0 + specH / 2}) rotate(-90)`)
    .attr("text-anchor", "middle")
    .style("fill", "#9ca3af").style("font-size", "10px")
    .text("|X[k]|");

  [0, specMaxMag].forEach(v => {
    const ty = magSc(v);
    if (v > 0)
      svg.append("line")
        .attr("x1", specFm.l).attr("x2", W - specFm.r).attr("y1", ty).attr("y2", ty)
        .attr("stroke", "#374151").attr("stroke-width", 0.5)
        .attr("stroke-dasharray", "2,3").attr("opacity", 0.6);
    svg.append("line")
      .attr("x1", specFm.l - 4).attr("x2", specFm.l).attr("y1", ty).attr("y2", ty)
      .attr("stroke", "#6b7280").attr("stroke-width", 1);
    svg.append("text")
      .attr("x", specFm.l - 6).attr("y", ty + 4).attr("text-anchor", "end")
      .style("fill", "#6b7280").style("font-size", "9px")
      .text(v.toFixed(2));
  });

  svg.append("line")
    .attr("x1", specFm.l).attr("x2", W - specFm.r).attr("y1", specBase).attr("y2", specBase)
    .attr("stroke", "#374151").attr("stroke-width", 1);

  specK.forEach(({ k, mag: m }) => {
    const noteIdx = comp_freqs.indexOf(k);
    svg.append("rect")
      .attr("x", kSc(k) - barW / 2).attr("y", magSc(m))
      .attr("width", barW).attr("height", specBase - magSc(m))
      .attr("fill", noteIdx >= 0 ? compColors[noteIdx] : "#4b5563").attr("opacity", 0.85);
  });

  const tickKs = new Set([0, 5, 10, 15, 20, ...comp_freqs]);
  tickKs.forEach(k => {
    const noteIdx = comp_freqs.indexOf(k);
    svg.append("text")
      .attr("x", kSc(k)).attr("y", specBase + 14).attr("text-anchor", "middle")
      .style("fill", noteIdx >= 0 ? compColors[noteIdx] : "#6b7280")
      .style("font-size", "10px").text(k);
  });

  svg.append("text")
    .attr("x", W / 2).attr("y", specBase + 28).attr("text-anchor", "middle")
    .style("fill", "#6b7280").style("font-size", "10px")
    .text("frequency bin k");

  const cur_x = kSc(wind_f);
  const cur_y = magSc(mag);
  svg.append("line")
    .attr("x1", cur_x).attr("x2", cur_x)
    .attr("y1", specY0 + specFm.t).attr("y2", specBase)
    .attr("stroke", "#f0956a").attr("stroke-width", 1.5)
    .attr("stroke-dasharray", "4,3").attr("opacity", 0.8);
  svg.append("circle")
    .attr("cx", cur_x).attr("cy", cur_y).attr("r", 5).attr("fill", "#f0956a")
    .attr("stroke", "#111827").attr("stroke-width", 1.5);
}

{
  const N          = winding_N;
  const comp_freqs = winding_freqs;
  const comp_amps  = winding_amps;
  const compColors = ["#7eb8f7", "#6ddc8b", "#f0956a"];

  const wound  = signalX.map((v, n) => ({
    px: v * Math.cos(-2 * Math.PI * wind_f * n / N),
    py: v * Math.sin(-2 * Math.PI * wind_f * n / N),
  }));
  const cm_x   = wound.reduce((s, p) => s + p.px, 0) / N;
  const cm_y   = wound.reduce((s, p) => s + p.py, 0) / N;
  const mag      = Math.sqrt(cm_x**2 + cm_y**2);
  const isMatch  = comp_freqs.some(f => Math.abs(f - wind_f) < 0.15);
  const mag_display = Math.abs(wind_f - Math.round(wind_f)) < 0.01 ? mag : 0;

  const components = comp_freqs.map((f, i) =>
    Array.from({length: N}, (_, n) => comp_amps[i] * Math.cos(2 * Math.PI * f * n / N))
  );
  const compAlpha = comp_freqs.map(f => {
    const dist = Math.abs(f - wind_f);
    return dist < 2 ? 0.15 + 0.85 * (1 - dist / 2) : 0.15;
  });

  const svg = d3.create("svg")
    .attr("width", layout.W).attr("height", layout.totalH)
    .style("background", "#111827").style("border-radius", "8px");

  drawSignalPanel(svg, { x: signalX, components, compColors, compAlpha, wind_f, isMatch, N });
  drawWindingPanel(svg, { wound, cm_x, cm_y, wind_f });
  drawSpectrumPanel(svg, { specK, wind_f, mag: mag_display, comp_freqs, compColors });

  return svg.node();
}

An instrument plays three notes at once, but you hear a single chord. Your brain solves that problem instantly, without effort. Now you know how a computer does it too.