convolution

Convolution is a mathematical operation that combines two functions to produce a third function that expresses how the shape of one is modified by the other. In signal processing and related fields, convolution describes how a system with an impulse response h responds to an input signal x, yielding the output y = x * h.

Continuous convolution is defined by (f * g)(t) = ∫_{-∞}^{∞} f(τ) g(t − τ) dτ, assuming the integral exists. Discrete convolution for a sequence {f[n]} and {g[n]} is (f * g)[n] = ∑_{k=-∞}^{∞} f[k] g[n − k], with similar finite-length forms used in practice. Note that cross-correlation is similar but does not flip the second function. Convolution is commutative and associative, and convolving with a delta function δ yields the original function: f * δ = f. In time-invariant systems, the output is the convolution of the input with the system's impulse response.

The operation links to the frequency domain via the convolution theorem: the Fourier transform of a convolution is the pointwise product of the transforms, F{f * g} = F{f} · F{g}. This equivalence underpins many analysis and design techniques.

Computationally, convolution can be performed directly or via the fast Fourier transform (FFT) to reduce complexity. For finite-length sequences, zero-padding is used to obtain linear convolution rather than circular convolution. Applications include signal and image processing (smoothing, blurring, edge detection), probability (sum of independent variables), differential equations via Green's functions, and machine learning (convolutional neural networks).