What this calculator does
Discrete convolution slides one sequence across another, multiplying the overlapping terms and adding them at each offset. The result is longer than either input: convolving a sequence of length m with one of length n gives m + n − 1 terms.
The quickest way to see what it does is to read both sequences as polynomial coefficients. Convolving 1, 2, 3 with 4, 5, 6 is the same operation as multiplying (1 + 2x + 3x²) by (4 + 5x + 6x²), and the answer, 4, 13, 28, 27, 18, is exactly the coefficient list of that product. Signal processing, probability and polynomial arithmetic all lean on the same operation for this reason.
The formula
Every term of the first sequence is multiplied by every term of the second, and each product is added into the output position given by the sum of the two input positions. Counting positions from zero, the product of the term at position i and the term at position j lands at position i + j. That is why the result runs to m + n − 1 terms: the highest position anything can reach is (m − 1) + (n − 1).
| Term | Meaning |
|---|---|
| Convolution | The operation that produces cₙ by summing every product aₖ·b₍ₙ₋ₖ₎ whose indices add to n. |
| Position index | Where a term sits in its sequence, counted from zero, which also serves as the power of x in the polynomial reading. |
| Result length | m + n − 1, one less than the sum of the two input lengths. |
| Identity | The single-element sequence 1, which convolves with anything to return it unchanged. |
The inputs explained
| Field | What to enter |
|---|---|
| Sequence A (comma separated) | The first sequence, as numbers separated by commas. Read as polynomial coefficients, the first entry is the constant term. |
| Sequence B (comma separated) | The second sequence, in the same form. It does not need to be the same length as the first. |
When to use it
Multiplying two polynomials
Entering the coefficient lists of two polynomials returns the coefficient list of their product, which avoids the bookkeeping of expanding and collecting terms by hand and is easy to check against a manual expansion.
Applying a filter to a signal
A moving average, a smoothing kernel or any finite impulse response filter is applied by convolving the filter coefficients with the signal. Working through a short example by hand first makes what the filter is doing much clearer.
Combining two probability distributions
The distribution of the sum of two independent discrete random variables is the convolution of their individual distributions, so convolving the outcome probabilities of two dice gives the probabilities for their total.
Worked examples
Every figure in the tables below is produced by this page’s own calculator at build time, so the numbers and the tool always agree. Select any row to load that scenario.
What does convolving a sequence with different partners produce?
The sequence 1, 2, 3 convolved against five different second sequences.
| Sequence B | Result | Length of result |
|---|---|---|
| 1 | 1, 2, 3 | 3 |
| 0, 1 | 0, 1, 2, 3 | 4 |
| 1, 1 | 1, 3, 5, 3 | 4 |
| 1, -1 | 1, 1, 1, -3 | 4 |
| 4, 5, 6 | 4, 13, 28, 27, 18 | 5 |
Questions
Is convolution the same as multiplying the sequences together?
Not in the elementwise sense, where matching positions would be multiplied and nothing else. Convolution multiplies every term against every other and adds the products by position, which is exactly polynomial multiplication and gives a longer result.
Why is the result longer than either input?
Because the last term of one sequence can reach the last term of the other. With positions counted from zero, the furthest reachable position is (m − 1) + (n − 1), so the result has m + n − 1 entries in all.
Does the order of the two sequences matter?
No. Convolution is commutative, so swapping the inputs gives the same output. It is also associative, which is why a chain of filters can be collapsed into one by convolving the filters together first.
Is there a quick way to check a convolution result?
Yes. The sum of the output always equals the product of the two input sums. For 1, 2, 3 against 4, 5, 6 that is 6 × 15 = 90, and the result 4 + 13 + 28 + 27 + 18 also comes to 90. It will not catch every mistake, but it catches most.
For expanding a binomial power into its coefficients, see the binomial expansion calculator. For the elementwise product of two equal-length vectors instead, see the dot product calculator.