Convolution Calculator

(a * b)[k] = Σᵢ a[i] × b[k − i] length = m + n − 1

a, b

The two sequences, typed as numbers separated by semicolons. Their order does not matter — convolution is commutative, so swapping the two boxes returns an identical result. They do not have to be the same length, and either may hold decimals or negative values. Each box accepts up to two hundred entries.

k

The index of the entry being produced, running from 0 to the length of the result minus one. It is not printed beside each value, because a comma-separated row already has an order: the first number is k = 0, the second is k = 1. The reference table below spells the indices out for the default pair, one row each, which is where to look if the positions are what you are checking.

a[i] × b[k − i]

One product in the sum. For each k the index i runs over every position where both sequences have an entry, so the number of products added together rises from one at the ends to the length of the shorter sequence in the middle. The pattern of overlap is the whole idea: one sequence slides past the other and the products are collected column by column.

Σᵢ

The sum over those products, which is one entry of the result. Each entry is rounded to six decimal places, and the total reported beside the sequence is the sum of those rounded entries rather than of the unrounded ones — so adding up the numbers printed on the panel gives exactly the printed total.

m + n − 1

The length of the result, reported as its own reading. Two sequences of three give five entries; a single number convolved with a three-term sequence gives three. The extra entries beyond the longer of the two are what make this the full convolution rather than the kind that keeps only the part where the sequences completely overlap.

Use this page when two sequences have to be combined into a distribution: the number of ways two dice can add up to each total, the effect of a moving average window on a series, the coefficients of a product of two polynomials. When the question is about one sequence on its own — its terms, its sum, its pattern — the sequence calculator covers it, and when the window of a moving average is what you are choosing, the average calculator is the page that names it.

1. One, two, three against four, five, six

   1. k = 0: only the first entries overlap, so 1 × 4 = 4
   2. k = 1: 1 × 5 + 2 × 4 = 5 + 8 = 13
   3. k = 2: 1 × 6 + 2 × 5 + 3 × 4 = 6 + 10 + 12 = 28
   4. k = 3: 2 × 6 + 3 × 5 = 12 + 15 = 27
   5. k = 4: only the last entries overlap, 3 × 6 = 18
   6. The result is 4, 13, 28, 27, 18 and its total is 90, which is also 6 × 15

   The last line is the check that makes this page easy to trust: the sum of a convolution is always the product of the two sequence sums, here 1 + 2 + 3 = 6 against 4 + 5 + 6 = 15. It falls out of the algebra, because every product in the result is a product of one entry from each sequence and every such pair appears exactly once.

2. Two dice and the shape of their totals

   1. A die has one way to show each of its six faces, so each sequence is six ones
   2. Convolving them counts the pairs that add to each total: k = 0 gives 1 × 1 = 1 way to roll a sum of 2
   3. k = 1 gives 1 + 1 = 2 ways to roll a sum of 3, and the count keeps rising
   4. The peak is 6, at the middle entry, which is the sum of 7
   5. The result is 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1, and its total is 36

   This is the standard illustration of the central limit theorem in miniature: two flat distributions convolved give a triangular one, and convolving a third die in would round it further towards a bell. The total of 36 is also the check — the product of the two sums is 6 × 6, which is every ordered pair of faces, one outcome for each.

3. A single number scales the whole sequence

   1. A one-entry sequence has nothing to overlap with, so every entry of the result is that entry times one entry of the other sequence
   2. k = 0: 2 × 1 = 2
   3. k = 1: 2 × 2 = 4
   4. k = 2: 2 × 3 = 6
   5. The result is 2, 4, 6 and the total is 12, which is 2 × 6

   The degenerate case is worth running once, because it shows that the sliding picture has an end: with one sequence of length one there is never more than one product to add, and the convolution reduces to multiplication. It is the same reason the length formula m + n − 1 gives 1 + 3 − 1 = 3 rather than anything larger.

This page computes the full convolution and only the full convolution. The two variants that keep only part of the result are not offered: the one that returns a sequence the length of the longer input, and the one that returns only the positions where the sequences overlap completely. Neither is well defined for two sequences of even length, and the full result is the one that contains them both — the shorter variants are slices of it rather than different calculations. Each sequence may hold at most two hundred entries, and each value is limited to 1000000 in magnitude, which is a display limit: a convolution multiplies and then adds, so large entries overflow the readable range long before they overflow a double. Every entry of the result is rounded to six decimal places, and the reported total is the sum of the rounded entries, so adding the printed numbers by hand reproduces the printed total rather than a slightly different one. The result is a comma-separated row of numbers and is not localised, so a decimal point stays a full stop whichever language the page is read in. Positions carry the indices and are not labelled individually; the reference table gives the indices explicitly for the default pair.

How do you convolve two sequences by hand?

Slide one sequence past the other and add up the products at each position. With 1, 2, 3 and 4, 5, 6 the first entry is 1 × 4 = 4, the second is 1 × 5 + 2 × 4 = 13, and so on to 3 × 6 = 18 at the far end. The result has five entries, since two sequences of three convolve to a length of 3 + 3 − 1.

How do I check that a convolution is right?

Add up the result and compare it with the product of the two sequence sums. For 1, 2, 3 against 4, 5, 6 that is 90 against 6 × 15, and the two must agree. The reason is that every entry of the result is a sum of pairwise products, and every possible pair from the two sequences appears in exactly one of those sums.

Why does the result have more entries than either sequence?

Because the full convolution keeps the positions where the sequences only partly overlap. With 1, 2, 3 against 4, 5, 6 there are five such positions: one at each end where a single pair meets, and three in the middle where several do. The two shorter variants of the operation — the kind the length of the longer input, and the kind that keeps only complete overlaps — are both slices of this result.

What does convolving two dice have to do with probability?

It counts the outcomes. A single die is a sequence of six ones, one for each face, and convolving that sequence with itself counts the ordered pairs that add up to each total: one way to make 2, two ways to make 3, rising to six ways to make 7 and falling away again. The total of the result, 36, is the number of ordered pairs, which is why dividing each entry by it gives the probability.

Is a moving average a convolution?

Yes. A moving average takes a window of equal weights — five days of a fifth each, for instance — and slides it along the series, which is exactly a convolution with that window as one of the two sequences. That is why the operation turns up in smoothing, in filters and in image processing: the thing being slid is a set of weights, and the thing being smoothed is the sequence.

• Convolution — the definition, the sum over overlapping products, and the length of the result — Wolfram MathWorld (United States)
• Cauchy Product — the same rule applied to the coefficients of two power series, which is what convolving two polynomial coefficient lists computes — Wolfram MathWorld (United States)
• Convolution Theorem — why the transform of a convolution is the product of the transforms, and where the operation is met in signal processing — Wolfram MathWorld (United States)