# Compare a Signal With Itself

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

"What note is this?" sounds like a question about frequency. Mostly it isn't. Ask
a different one: **how much does this signal look like itself, shifted?**
Slide a copy along by *lag* samples, multiply it against the original point by
point, and total the products. Land the shift on a whole period and peaks meet peaks —
a big positive score. Land it half a period out and peaks meet troughs — a big negative
one. The periodicity falls straight out as a row of peaks.

That is **autocorrelation**, and it is not a new idea if you have done
Template Matching: it is that module's cross-correlation with the template replaced by
the signal itself. It also parallelises without an argument — **one thread per
lag**, every thread reading the same array and writing only its own cell. No
atomics, no scatter, nothing to coordinate.

Below is `signal`: 512 samples of a plucked string recorded at
8192 Hz — 62.5 milliseconds, a fundamental plus three harmonics, decaying. Its
period is in there. Go and find it.

## Figures

- **slide it half a period and it argues with itself; slide it a whole one and it agrees**

## Goal

**Goal:** score `signal` against a shifted copy of itself at
every lag from 0 to 255, then find the lag of the biggest peak and log the
period.

## Requirements

- `output: [256]` — one thread per lag, and `this.thread.x` *is* the lag
- Loop over all `this.constants.n` samples, adding `signal[i] * signal[i + lag]` only while `i + lag` is still inside the signal
- Scan the returned array from lag `8` upward for the largest value — not from 0
- Log it: `console.log('period:', bestLag, 'samples')`

## Hint 1 — which lag is mine?

With `output: [256]` there are 256 threads, and thread
`this.thread.x` owns exactly one lag. Read it into a
`const lag` on the first line and the rest of the kernel reads like the
formula.

## Hint 2 — the loop, and its guard

A kernel loop needs a bound known at compile time, so loop over the
*whole* signal and skip the samples whose partner has fallen off the end:

```js
for (let i = 0; i < this.constants.n; i++) {
  if (i + lag < this.constants.n) {
    sum += signal[i] * signal[i + lag];
  }
}
```

Long lags therefore add up fewer terms than short ones. Remember that — task 3 sends
the bill.

## Hint 3 — finding the peak in JavaScript

256 numbers is nothing; finish in plain JS.

```js
let bestLag = 8;
for (let lag = 8; lag < 256; lag++) {
  if (r[lag] > r[bestLag]) bestLag = lag;
}
```

Start at 8, not 0. Lag 0 is the signal against an unshifted copy of itself:
it wins every time and means nothing.

## Same idea elsewhere

Correlation-by-lag is a stock primitive everywhere — NPP and cuFFT on CUDA,
vDSP's `conv`/`corr` on Apple silicon, a WGSL compute shader indexed
by `global_invocation_id` in WebGPU. The guarded inner loop is the same edge
handling every stencil kernel needs, and the read pattern (all threads sweeping the same
array in step) is the one caches and texture units are built to serve.

## Starter code

```js
// One thread per lag. Each one slides a copy of the signal over itself.
const gpu = new GPU({ mode });

const correlate = gpu.createKernel(function (signal) {
  const lag = this.thread.x;
  let sum = 0;
  // TODO: walk the whole signal, and whenever i + lag is still inside it,
  // add signal[i] * signal[i + lag] to sum.
  return sum;
}, {
  output: [256],
  constants: { n: 512 },
});

const r = correlate(signal);
console.log('r[0], the signal against itself:', r[0]);

// TODO: scan lags 8…255 for the biggest value, then
// console.log('period:', bestLag, 'samples');
```

---

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

[Next task](https://gpu.rocks/learn/autocorrelation-b159433f/2.md)