# The Note That Isn't There

*Task 4 of 5 · [Autocorrelation & Pitch](https://gpu.rocks/learn/autocorrelation-b159433f.md) · GPU.js Learn*

Play a note through a telephone, or a small speaker, or a church organ's mixture
stop, and something strange happens: the fundamental is gone — the hardware simply cannot
move that slowly — and you hear it anyway. Your auditory system is not reading the
loudest peak off a spectrum. It is finding the period the partials *share*.

`signal` below is built from harmonics 2, 3 and 4 of 128 Hz — that is
256, 384 and 512 Hz — and there is no energy at 128 Hz at all. Not
attenuated: absent, by construction. Take its spectrum and the loudest bin is
256 Hz, an octave above the note. Take its autocorrelation and the first peak is at
lag 64, which is 128 Hz, because 256, 384 and 512 all come back into step every 64
samples whether or not anything is oscillating at that rate.

So you need a spectrum to accuse. Write one — a direct transform, one thread per bin,
which is the O(n²) way and perfectly fine at 512 samples. *The DFT, Honestly* has
a great deal more to say about what a transform is *for* and what it costs; here it
is only the witness for the prosecution.

**Two planes, one complex array.** gpu.js has no complex
number, so this track carries one as two planes of floats: a kernel declares
`output: [n, 2]` and the result reads `result[0][i]` for the real part
and `result[1][i]` for the imaginary part. Going the other way, a complex
*argument* is a nested `[2][n]` array read as `data[0][i]` and
`data[1][i]`. It is the same trick Optical Flow uses to return two flow components
from one kernel — `output: [w, h]` is indexed `[y][x]`, so
`[n, 2]` is indexed `[plane][i]`.

## Goal

**Goal:** write the two-plane DFT kernel, find the loudest bin and its
frequency, and log it beside the answer the (already written) autocorrelation gives.

## Requirements

- `output: [512, 2]` — one thread per (plane, bin); `this.thread.x` is the bin, `this.thread.y` is the plane
- Each thread sums over all `this.constants.n` samples with angle `−2π · bin · i / n`: plane 0 accumulates `signal[i] · cos(angle)`, plane 1 `signal[i] · sin(angle)`
- In JavaScript, take `Math.hypot(re, im)` per bin and find the loudest one below bin 256; its frequency is `bin * sampleRate / 512`
- Log both verdicts: `console.log('loudest partial:', hz, 'Hz')` and `console.log('autocorrelation:', hz, 'Hz')`

## Hint 1 — one thread, one number

Each thread owns a single output cell, so it computes a single sum — its own
plane's, for its own bin:

```js
const bin = this.thread.x;
let re = 0;
let im = 0;
for (let i = 0; i < this.constants.n; i++) {
  const angle = (-2 * Math.PI * bin * i) / this.constants.n;
  re += signal[i] * Math.cos(angle);
  im += signal[i] * Math.sin(angle);
}
if (this.thread.y === 0) return re;
return im;
```

Both sums get computed by both threads and one of them is thrown away. That is
wasteful and it is also the shape gpu.js gives you — and at 512 bins the whole
transform is one launch, so you will not notice. The next task runs the same idea over
a buffer 32 times longer, which is where the O(n²) stops being a remark and
becomes the thing you are waiting for.

## Hint 2 — reading two planes back

The result is two rows, not two columns:

```js
const spec = spectrum(signal);
const mag = Math.hypot(spec[0][bin], spec[1][bin]);
```

Plane first, bin second — `output: [n, 2]` is indexed `[y][x]`
like any other 2D output.

## Hint 3 — bins go the other way

Watch the two conversions in this task, because they are reciprocals of each
other and mixing them up is the classic slip. A *lag* is a period, so
`hz = sampleRate / lag`. A *bin* is already a frequency count, so
`hz = bin * sampleRate / n`. With 8192 Hz over 512 samples each bin
is 16 Hz wide, and the answer you are looking for is bin 16.

## Same idea elsewhere

Two outputs per thread packed into planes is how every platform returns
multi-component results without a struct: an RG32F texture in WebGPU, a
`float2` buffer in CUDA (which is exactly what cuFFT's
`cufftComplex` is), `half2` pairs in Metal. The layout question —
interleaved `[re, im, re, im…]` or planar `[re…][im…]` — is the same
one everywhere, and planar is what coalesces.

## Starter code

```js
// One kernel to write. The autocorrelation is yours from task 3.
const gpu = new GPU({ mode });

// Two planes: result[0][bin] is the real part, result[1][bin] the imaginary.
const spectrum = gpu.createKernel(function (signal) {
  const bin = this.thread.x;
  // TODO: sum signal[i] * cos(angle) and signal[i] * sin(angle) over the
  // whole signal, with angle = -2 * PI * bin * i / n, then return the sum
  // belonging to THIS thread's plane (this.thread.y).
  return 0;
}, {
  output: [512, 2],
  constants: { n: 512 },
});

const correlate = gpu.createKernel(function (signal) {
  const lag = this.thread.x;
  let dot = 0;
  let head = 0;
  let tail = 0;
  for (let i = 0; i < this.constants.n; i++) {
    if (i + lag < this.constants.n) {
      const a = signal[i];
      const b = signal[i + lag];
      dot += a * b;
      head += a * a;
      tail += b * b;
    }
  }
  return dot / Math.sqrt(head * tail);
}, {
  output: [256],
  constants: { n: 512 },
});

const spec = spectrum(signal);
const rho = correlate(signal);

// The autocorrelation's verdict — the first peak over the threshold, as before.
let period = -1;
for (let lag = 8; lag < 255; lag++) {
  if (rho[lag] >= 0.8 && rho[lag] > rho[lag - 1] && rho[lag] >= rho[lag + 1]) {
    period = lag;
    break;
  }
}

// TODO: find the loudest bin below 256 from spec[0][bin] and spec[1][bin],
// convert it to hertz, and log:
//   console.log('loudest partial:', hz, 'Hz');
//   console.log('autocorrelation:', sampleRate / period, 'Hz');
```

---

Interactive version: https://gpu.rocks/learn/autocorrelation-b159433f/4

[Previous task](https://gpu.rocks/learn/autocorrelation-b159433f/3.md) · [Next task](https://gpu.rocks/learn/autocorrelation-b159433f/5.md)