Definition
Continuous convolution of functions f and g: (f ∗ g)(t) = ∫ f(τ) g(t − τ) dτ, with the integral taken over all real τ.
Discrete convolution of sequences f and g: (f ∗ g)[n] = Σₖ f[k] g[n − k]. For finite sequences of lengths L and M the result has length L + M − 1.
Multiplying two polynomials is the same as convolving their coefficient lists, so a FOIL or polynomial expansion is a small convolution.
Sources: NIST Digital Library of Mathematical Functions: DLMF §1.14 Integral Transforms (convolutions)
Properties
- Commutative: f ∗ g = g ∗ f
- Associative: (f ∗ g) ∗ h = f ∗ (g ∗ h)
- Distributive: f ∗ (g + h) = f ∗ g + f ∗ h
- Identity: f ∗ δ = f, where δ is the Dirac delta (or the unit impulse [1] for sequences)
- Shift: delaying either input by a delays the output by a
- Convolution theorem: the Fourier (or Laplace) transform of f ∗ g is the product of the transforms, up to a constant factor that depends on the transform convention
- Probability: the density of the sum of two independent random variables is the convolution of their densities
Sources: NIST Digital Library of Mathematical Functions: DLMF §1.14 Integral Transforms (convolutions)
Worked example
Convolve f = [1, 2, 3] with g = [1, 1]. Each output term adds the products of overlapping entries: the result is [1, 3, 5, 3].
The same numbers are the coefficients of (1 + 2x + 3x²)(1 + x) = 1 + 3x + 5x² + 3x³.
| n | Terms f[k]·g[n − k] | (f ∗ g)[n] |
|---|---|---|
| 0 | 1·1 | 1 |
| 1 | 1·1 + 2·1 | 3 |
| 2 | 2·1 + 3·1 | 5 |
| 3 | 3·1 | 3 |