Signal Convolution & Filtering

Convolution: The convolution (f*g)[n] = Σ f[k]·g[n−k] is the fundamental operation in linear filtering. Each output sample is a weighted sum of neighboring input samples, with weights given by the kernel. The Convolution Theorem states that convolution in the time domain equals pointwise multiplication in the frequency domain (via the Fourier transform), which is why FFTs make large kernel convolution efficient — O(n log n) rather than O(n²). Box kernels average all taps equally (crude low-pass); Gaussians minimize the time-bandwidth product (Heisenberg uncertainty principle for signals); Laplacian kernels detect second derivatives (edges); sharpening adds back the Laplacian.