# The Brick Wall Rings

*Task 2 of 5 · [Filtering in the Frequency Domain](https://gpu.rocks/learn/frequency-filtering-8c225e10.md) · GPU.js Learn*

If multiplying by a spectrum is a filter, then just *choose* the spectrum.
Want a low-pass? Set every bin above a cutoff to zero and transform back. Nothing in signal
processing is simpler, and nothing punishes simplicity faster.

What comes back is not a smoothed square wave. It is a square wave with
**ringing**: an overshoot at every edge, plus ripples running the whole length
of the buffer. Widening the cutoff does not help: it squeezes the ripple closer to the edge,
but the height of that first overshoot sits at about **9% of the jump** however
many bins you keep — right up until you keep them all and there is no filter left. This is
the **Gibbs phenomenon**, and it is not a bug in your arithmetic: a rectangle in
frequency is a `sinc` in time, and a sinc rings forever.

One structural detail first, because it is the most common way this task goes wrong.
The signal is real, which makes its spectrum **conjugate-symmetric**: bin
`n − k` always holds the conjugate of bin `k`. Those upper bins are
not extra high frequencies — they are the mirror halves of the low ones. Bin 250 of 256 is
*six* bins from DC. Zero a bin without zeroing its mirror and the inverse transform
comes back complex, so fold the index before you compare it to the cutoff:

```js
const k = this.thread.x;
const dist = Math.min(k, this.constants.n - k);
```

The starter below forgets that fold, on purpose. Run it and look at the second log line:
a real signal has come back with an imaginary part bigger than 1.

## Figures

- **you cut the spectrum with a cliff; the cliff hands you back a ripple**

## Goal

**Goal:** finish `lowPass` so that every bin more than
`20` bins from DC is zeroed on *both* planes and every other bin passes
through untouched — then read the overshoot off the console.

## Requirements

- Keep `output: [256, 2]`; the incoming spectrum is read as `spec[0][k]` and `spec[1][k]`
- Measure a bin's distance from DC as `Math.min(k, this.constants.n - k)` — never the raw index
- Return `0` on both planes when that distance exceeds `this.constants.cut`
- Otherwise return the bin unchanged, real part on plane 0 and imaginary part on plane 1

## Hint 1 — the fold, and why

For a real signal the spectrum is a palindrome of conjugates: bin
`255` is the mirror of bin `1`, bin `236` the mirror of
bin `20`. Keeping a bin and dropping its mirror keeps half of a cosine and
throws the other half away, and what is left is a complex exponential. So:

```js
const k = this.thread.x;
const dist = Math.min(k, this.constants.n - k);
if (dist > this.constants.cut) return 0;
```

## Hint 2 — one return per plane

The zero is the same on both planes, so it can be returned before you ever
look at `this.thread.y`. What survives is a straight pass-through:

```js
if (this.thread.y === 0) return spec[0][k];
return spec[1][k];
```

## Hint 3 — reading the answer

The console prints the peak as a fraction of the wave's 2-unit jump. You are
looking for about `9.2`%. Gibbs' constant is 8.95%; the difference is only
that our samples do not land exactly on the peak of the ripple.

## Same idea elsewhere

Every real filter design is a negotiation with this fact. An ideal low-pass has an
infinitely long, non-causal impulse response, so hardware and DSP libraries ship windowed
approximations instead — `scipy.signal.firwin`, MATLAB's `fir1`, the
biquad cascades in Web Audio. It is also why a JPEG rings around sharp edges: quantising
away a block's high-frequency DCT coefficients is exactly the brick wall you just built.

## Starter code

```js
// A brick-wall low-pass, and the ringing it cannot avoid.
const gpu = new GPU({ mode });

// GIVEN — the forward transform. A real signal in, a complex spectrum
// out: with output [n, 2] the result is indexed spec[p][k], where plane 0
// holds the real part of bin k and plane 1 the imaginary part.
const dft = gpu.createKernel(function (sig) {
  const k = this.thread.x;
  let re = 0;
  let im = 0;
  for (let t = 0; t < this.constants.n; t++) {
    const angle = (-2 * Math.PI * k * t) / this.constants.n;
    re += sig[t] * Math.cos(angle);
    im += sig[t] * Math.sin(angle);
  }
  if (this.thread.y === 0) return re;
  return im;
}, { output: [256, 2], constants: { n: 256 } });

// GIVEN — the inverse. A complex spectrum in as spec[0][k] / spec[1][k], a
// complex signal out in the same two planes. The 1/n lives HERE and nowhere
// else: divide a second time "to be safe" and everything comes back n times
// too small.
const idft = gpu.createKernel(function (spec) {
  const t = this.thread.x;
  let re = 0;
  let im = 0;
  for (let k = 0; k < this.constants.n; k++) {
    const angle = (2 * Math.PI * k * t) / this.constants.n;
    const c = Math.cos(angle);
    const s = Math.sin(angle);
    re += spec[0][k] * c - spec[1][k] * s;
    im += spec[0][k] * s + spec[1][k] * c;
  }
  if (this.thread.y === 0) return re / this.constants.n;
  return im / this.constants.n;
}, { output: [256, 2], constants: { n: 256 } });

// YOUR JOB — zero everything above the cutoff.
const lowPass = gpu.createKernel(function (spec) {
  const k = this.thread.x;

  // TODO: this compares the RAW bin index. Bin 250 of 256 is the mirror of
  // bin 6, not a high frequency — fold the index first:
  //   const dist = Math.min(k, this.constants.n - k);
  if (k > this.constants.cut) return 0;

  if (this.thread.y === 0) return spec[0][k];
  return spec[1][k];
}, { output: [256, 2], constants: { n: 256, cut: 20 } });

const filtered = idft(lowPass(dft(wave)));

let peak = filtered[0][0];
let leftover = 0;
for (let i = 0; i < 256; i++) {
  peak = Math.max(peak, filtered[0][i]);
  leftover = Math.max(leftover, Math.abs(filtered[1][i]));
}
// samples 16..47 sit at least 16 away from any edge: whatever wobbles there
// is ringing that has travelled, not the edge itself
let ripple = 0;
for (let i = 16; i < 48; i++) ripple = Math.max(ripple, Math.abs(Math.abs(filtered[0][i]) - 1));

// the wave steps from -1 to +1, so the jump is 2 units wide
console.log('overshoot:', (((peak - 1) / 2) * 100).toFixed(2), '% of the jump');
console.log('ripple in the flat stretch:', ripple.toFixed(6));
console.log('largest imaginary part:', leftover.toFixed(6));
```

---

Interactive version: https://gpu.rocks/learn/frequency-filtering-8c225e10/2

[Previous task](https://gpu.rocks/learn/frequency-filtering-8c225e10/1.md) · [Next task](https://gpu.rocks/learn/frequency-filtering-8c225e10/3.md)