Task 5 of 5
Task 1 had an accident built into it: the signal occupied 20 of 64 samples and the filter 5, so the 24-sample answer had room to spare. Take the room away and the theorem bites.
Multiplying two length-n spectra does not produce the convolution you want.
It produces the circular convolution — the one that treats both buffers as
loops, so whatever runs off the end comes back on at the beginning:
circular[i] = linear[i] + linear[i + n]Here sig is 32 samples and filt carries 9 taps, so the honest
answer is 32 + 9 − 1 = 40 samples long. Multiply their 32-bin spectra and the
last 8 samples fold back onto the first 8, corrupting them by as much as
0.37 against a signal whose largest value is 0.66. The signature is
unmistakable once you have seen it: the tail of the answer appears at its head.
The fix is to give the answer somewhere to live. Zero-pad both buffers to at least
n + m − 1 before transforming — 40 here, and since every real FFT wants a
power of two, 64. The overhang then lands on padding instead of on your
data. The starter transforms at 32 and prints the damage; fix PAD and the
guard inside pad, and the error should collapse to float32 rounding — a few
millionths on a GPU, a few hundred-thousandths on a software renderer.
This is also where the cost story gets honest. Padding to a power of two means transforming 64 points to convolve 32 with 9 — and 9 taps is short enough that the sliding window wins outright, on any hardware. Frequency-domain convolution starts paying somewhere around a few dozen taps, and exactly where depends on the machine. The Benchmark button will price this pipeline for you on both backends; Measuring Speed Honestly owns the rest of the methodology, including why a single timing is a rumour.
PAD long enough to hold the whole answer,
and finish pad so it copies the first 32 samples and zeroes the rest.PAD to at least 32 + 9 − 1 = 40; round up to 64, the next power of twopad, return src[this.thread.x] only while this.thread.x is below this.constants.src, and 0 beyond itNaN on the CPU backend and garbage on WebGLConvolving n samples with m taps produces
n + m − 1 samples: the filter's last tap is still hanging over the
signal's last sample m − 1 steps after the signal has ended. With 32 and
9 that is 40. Any transform length of 40 or more works; 64 is what you would use in
practice, because that is what an FFT wants.
Two lines, and the if matters — a ternary would still describe an
out-of-range read to the GLSL compiler:
if (this.thread.x < this.constants.src) {
return src[this.thread.x];
}
return 0;filt already arrives in a 32-sample buffer with 9 taps and 23 zeros, so
the same kernel pads it correctly with no special case.
Before you fix it, compare the first eight samples the starter prints against
the last eight of direct. They are the same numbers. That is not a
coincidence and it is not rounding — it is the tail of the convolution, delivered to
the front of the buffer.
scipy.signal.fftconvolve all pad internally and hand back the
n + m − 1 answer; numpy.fft does not, which is why the "why is my
filtered audio clicking at the block boundaries" question outlives every generation of
programmers. Streaming filters solve the same problem with overlap-add or overlap-save:
pad each block, convolve, and add the overhang into the next block instead of throwing it
at the start of this one.
This page is an interactive exercise — the editor, the GPU runner and your saved progress need JavaScript. The text above is the full brief.