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.