Convolution in simple words
Convolution combines two lists of numbers into a new list. Picture writing the second list backwards on a strip of paper and sliding it along the first list, one step at a time.
At each step, multiply the numbers that line up and add those products. That sum is one number in the answer. Keep sliding until the strips no longer overlap.
Example: convolve 1, 2, 3 with 1, 1. First 1 × 1 = 1. Then 1 × 1 + 2 × 1 = 3. Then 2 × 1 + 3 × 1 = 5. Last 3 × 1 = 3. The answer is 1, 3, 5, 3.
The answer is always one shorter than the two lengths added together: 3 + 2 − 1 = 4 numbers. Convolution is used to blur pictures, smooth data and add up dice rolls.
The convolution formula
The discrete convolution of x[n] and h[n] is y[n] = Σ x[k] · h[n − k], summed over every k where both samples exist. Samples outside the entered values count as zero.
If x has Nx samples and h has Nh samples, the result has Nx + Nh − 1 samples. When x starts at index nx₀ and h at nh₀, the first output index is nx₀ + nh₀.
Circular convolution with period N wraps the index instead: y[n] = Σ x[k] · h[(n − k) mod N] for n = 0 … N − 1. It is what multiplying two N-point discrete Fourier transforms computes, and it matches linear convolution only when N ≥ Nx + Nh − 1.
Worked example
Take x = [1, 2, 3] and h = [0, 1, 0.5]. The output has 3 + 3 − 1 = 5 samples.
y[0] = 1×0 = 0; y[1] = 1×1 + 2×0 = 1; y[2] = 1×0.5 + 2×1 + 3×0 = 2.5; y[3] = 2×0.5 + 3×1 = 4; y[4] = 3×0.5 = 1.5. So x ∗ h = [0, 1, 2.5, 4, 1.5].
A quick check: the outputs sum to 9, which equals (1 + 2 + 3) × (0 + 1 + 0.5) = 6 × 1.5.
| n | Terms | y[n] |
|---|---|---|
| 0 | 1×1 + 2×1 + 3×0 | 3 |
| 1 | 1×0 + 2×1 + 3×1 | 5 |
| 2 | 1×1 + 2×0 + 3×1 | 4 |
Where convolution shows up
Convolution describes how a linear, time-invariant system responds to an input: h is the impulse response and y is the output. It also multiplies polynomials, since the coefficients of the product are the convolution of the coefficient lists, and it smooths data with moving averages.
Values are handled in floating point and shown to 10 significant digits. Each sequence can have up to 200 values.