Discrete convolution

Two input spikes each launch a copy of $h[n]$. Step Which copy through Copy 0, Copy 1 and Sum, and watch how the sum is built.

Naming what you already built

Last page, I fed a system a short input, one number-worth of “spike” at a time, and watched each spike launch its own scaled, shifted copy of the impulse response $h[n]$. The output was just those copies, added up. I used $h[n]=1,\,0.5,\,0.25$ and an input $x[0]=2$, $x[1]=1$, and got $y=2,2,1,0.25$ by stacking two launched copies.

That construction is common enough to earn its own name and its own symbol. It’s called convolution, and I write it $y=x*h$. Nothing new is happening here: the picture at the top of the page just draws both launched copies and their sum at once, instead of placing them one spike at a time.

Notice its Sum is exactly the same output trace I built by hand last page, $2,2,1,0.25$: convolution is that construction, now with a name.

Flip and slide: a mechanical way to compute it

Overlaying every copy at once works, but it means drawing a separate copy for every input sample. There’s a faster, purely mechanical way to get the same numbers, one output value at a time, and it’s the picture worth having in your head whenever you see convolution.

Here’s the recipe in words. To find the output at one instant, flip $h$ left-to-right, slide it so it sits at that instant, multiply every pair of numbers that now overlap, and add up the products. That total is $y[n]$ at that instant. Slide to the next instant and do it again.

Written down, that recipe is

Read it the same way you just did it by hand. $n$ is the instant you’re asking about. $k$ runs over every index where $x$ or $h$ has a value. $h[n-k]$ is $h$, flipped and slid to instant $n$: plugging in $k=n$ gives $h[0]$, sitting right under $x[n]$, and every other $k$ lands on some other flipped, shifted sample of $h$. Multiplying by $x[k]$ and summing over every $k$ is exactly “multiply the overlaps and add them up.” The $*$ symbol is shorthand for this whole sum: $x*h$ means “compute $y[n]$ this way for every $n$.”

Drag Position n from 0 to 3, one step at a time, and read Total at this position.

Notice it retraces the same four numbers, $2,2,1,0.25$, one at a time instead of all at once, exactly matching the sum trace from the last instrument.

It does not matter which one you flip

The recipe said “flip $h$.” Nothing in the arithmetic actually needs it to be $h$ that gets flipped rather than $x$: flipping and sliding $x$ under a fixed $h$ multiplies and adds up the exact same pairs, just written down the other way around, $y[n]=\sum_k h[k]\,x[n-k]$.

Slide Position n, then switch Flip between Flip h and Flip x at the same position.

Notice the picture underneath looks completely different, but the plotted output trace never moves: $x*h$ and $h*x$ give the identical numbers. Convolution is commutative, so it never matters which sequence you call “the input” and which you call “the impulse response.”

How long is the output

Flip-and-slide only has something to multiply while the flipped, sliding sequence still overlaps the fixed one at all. Slide it in from far enough away and there’s no overlap yet, so $y[n]=0$; slide it out far enough past the other side and there’s no overlap left, so $y[n]=0$ again. In between, for two finite sequences of length $N_x$ and $N_h$, there are exactly $N_x+N_h-1$ sliding positions with any overlap at all, so that’s how many samples of $y$ can be nonzero.

But if $h$ never quite settles to zero (an infinite impulse response, previewed here and covered properly later), there’s no “far enough past the other side”: the output can keep going forever too, even while it keeps shrinking.

Switch h type between Finite pulse and Decaying, and read the verdict readout.

Notice the finite pulse’s output hits exactly zero right after $n=3$, matching a 3-sample $x$ and a 2-sample $h$, $N_x+N_h-2=3$, while the decaying $h$‘s output only ever gets smaller, never hitting zero on the nose.

Same rule, different h

Every one of those instruments ran the exact same flip-and-slide machinery. What changes the effect entirely is only the numbers you put in $h$.

Average a handful of neighboring samples together and you get a moving average, a simple smoother: it’s what a running weather report does when it quotes “the average of the last three days’ temperatures” instead of today’s alone, damping out day-to-day noise. Put a small copy of the signal a few samples later, scaled down, and you get an echo, the same effect as sound bouncing off a far wall and arriving again, quieter, a moment after the original. Subtract the sample before it from each sample, $h=[1,-1]$, and you get back the first difference from 2.2: the same “how fast is it changing” measurement, now written as a convolution.

Step Filter through Moving average, Echo and Differencer on the same noisy clip.

Notice the output trace looks completely different each time, even though it’s the identical flip-and-slide rule running underneath, just with a different $h$.

Two more views of the same numbers

There are two other ways to describe exactly the same operation, and both are useful later.

Write a sequence’s samples as the coefficients of a polynomial in a placeholder variable $z$: the sequence $1,2,3$ becomes $1+2z+3z^2$. Multiply two such polynomials the ordinary way you learned in algebra, collecting like powers of $z$, and the coefficients of the product are exactly the convolution of the two original sequences. It’s the same arithmetic you already know, just with $z^n$ standing in for “the sample at index $n$.”

The other view stacks $h$‘s job into a grid of numbers, a matrix $H$, where every column is a shifted copy of $h$; multiplying that matrix by the vector $x$ produces $y=Hx$, the same output as convolution, one row of the grid at a time. This is only a light preview, matrices get their own full treatment in a linear algebra course, but it’s worth seeing once here.

Switch View between Polynomial and Matrix.

Notice both land on the exact same output numbers as every earlier instrument, just written two more ways.

Worked example

Multiply the polynomials $(1+2z+3z^2)$ and $(1+z)$, matching $x=1,2,3$ and $h=1,1$:

• $y[0]=1\cdot1=1$
• $y[1]=1\cdot1+2\cdot1=3$
• $y[2]=2\cdot1+3\cdot1=5$
• $y[3]=3\cdot1=3$

So $x*h=1,3,5,3$, a sequence of length $3+2-1=4$, exactly the numbers both the polynomial and matrix views above land on.

For the moving-average case, take $h=\tfrac13,\tfrac13,\tfrac13$ and let $x$ be a step, $x[n]=1$ for $n\ge0$ and $0$ before. Then $y[0]=\tfrac13$, $y[1]=\tfrac23$, $y[2]=1$, and $y[n]=1$ for every $n\ge2$: the running average climbs up to, then settles at, the step’s steady value.

Where you’ll meet this

Every audio effect that smooths, echoes or filters a recording, every camera blur, and every “apply this impulse response” trick from the last page, runs on exactly this sum: flip one sequence, slide it past the other, multiply the overlaps, and add. Chapter 14 comes back to it from a different angle and finds a way to compute the exact same $y$ far faster once the sequences get long.

Reference card