Discrete-Time Convolution

The impulse response, the convolution sum, flip and slide, FIR and IIR systems, and causality and stability read from h[n]

Cambridge, Massachusetts — 1895

Harvard's new Fogg Art Museum has a lecture hall in which nobody can follow a lecture: every word hangs in the air and smears into the next. The senior physicists consider fixing it impossible, and the job goes to Wallace Sabine, who has just become an assistant professor. Sabine measures how long a sound takes to die away in the hall, then changes the room and measures again — with Oriental rugs on the floor, with seat cushions carried in from a nearby theatre, with people in the seats. He finds that the body of an average person shortens the decay about as much as six seat cushions. Out of those nights of measurements comes the reverberation time, the seconds a sound takes to fade by 60 dB, still the first number anyone asks about a concert hall. Sabine went on to design the acoustics of Boston's Symphony Hall (Wallace Clement Sabine). What Sabine was measuring is a room's response to a single sharp sound. Today it has a name — the impulse response — and this lesson shows that it tells you how the room will sound for any sound at all.

Take a linear, time-invariant system

S

in discrete time and feed it the unit sample

\delta[n]

. Call the output the impulse response:

h[n] = S\{\delta[n]\}.

For a room,

h

is the decaying train of echoes after a clap. For a moving average, it is the row of averaging weights. For a bank account with interest, it is the balance that one deposit grows into. Lesson 1-2 wrote every input as a row of shifted, scaled unit samples, and Lesson 1-3 promised that linearity and time invariance would turn that row into an output. Here is how.

y[n] = \sum_{k=-\infty}^{\infty} x[k]\,h[n-k] = (x * h)[n]

The convolution sum. The output of an LTI system is the input convolved with the impulse response.

Derivation

The convolution sum from linearity and time invariance

Start from the decomposition of the input into unit samples (Lesson 1-2):

x[n] = \sum_{k} x[k]\,\delta[n - k].

By definition,

\delta[n] \to h[n]

. Because the system is time-invariant, a unit sample delayed by

k

gives the impulse response delayed by

k

\delta[n - k] \;\to\; h[n - k].

Because it is linear, scaling by the number

x[k]

scales the response, and a sum of inputs gives the sum of the responses:

\sum_k x[k]\,\delta[n - k] \;\to\; \sum_k x[k]\,h[n - k].

The left side is

x[n]

, so the right side is the output:

y[n] = \sum_k x[k]\,h[n - k].

Every step used one of the two properties and nothing else. That is the deep reason LTI systems are the ones we can analyse completely: one experiment,

\delta \to h

, fixes the response to everything.

💡Two ways to read the sum

Input view (superposition): each input sample $x[k]$ launches its own copy of the impulse response, scaled by $x[k]$ and starting at time $k$ . The output is the pile-up of all the copies. This is how to think.
Output view (flip and slide): to get one output value $y[n]$ , write $h[n - k]$ as a function of $k$ — the impulse response flipped (because of the $-k$ ) and slid to start at $n$ — multiply it point by point with $x[k]$ , and add up the products. This is how to compute by hand.

Both are the same sum read in a different order.

📐A three-point average

Let

x = [1,\ 2,\ 3]

n = 0, 1, 2

, and let

h = [\tfrac13,\ \tfrac13,\ \tfrac13]

n = 0, 1, 2

— a three-point moving average. Slide the flipped

h

along

x

$y[0] = \tfrac13(1) = \tfrac13$
$y[1] = \tfrac13(1 + 2) = 1$
$y[2] = \tfrac13(1 + 2 + 3) = 2$
$y[3] = \tfrac13(2 + 3) = \tfrac53$
$y[4] = \tfrac13(3) = 1$

The output has

3 + 3 - 1 = 5

samples: a length-

N

input and a length-

M

impulse response give

N + M - 1

. Notice the ramp at each end, where the averaging window hangs off the data — every real smoothing filter has these edge effects.

Impulse responses come in two kinds. A finite impulse response (FIR) ends: moving averages, the echo

h[n] = \delta[n] + 0.5\,\delta[n - D]

, any filter that only weights past inputs. An infinite impulse response (IIR) never quite ends: the leaky accumulator

y[n] = a\,y[n-1] + x[n]

has

h[n] = a^n u[n]

, a geometric decay, because each output feeds the next. A room is effectively IIR — sound bounces until absorption wins — and Sabine's reverberation time is the time its impulse response takes to fall by 60 dB.

💡The algebra of convolution

Commutative: $x * h = h * x$ — the signal and the system can trade places.
Associative: $(x * h_1) * h_2 = x * (h_1 * h_2)$ — two systems in series act like one with impulse response $h_1 * h_2$ .
Distributive: $x * (h_1 + h_2) = x * h_1 + x * h_2$ — two systems in parallel act like one with $h_1 + h_2$ .
Identity: $x * \delta = x$ — the unit sample is the "do nothing" system.

So a whole block diagram of LTI systems collapses to a single impulse response.

💡Causality and stability, read from h[n]

Causal $\iff h[n] = 0$ for $n < 0$ . The output $y[n] = \sum_k h[k]\,x[n-k]$ uses $x[n - k]$ with $k < 0$ — a future input — only if $h[k] \ne 0$ for some negative $k$ .
BIBO stable $\iff \displaystyle\sum_{n} |h[n]| < \infty$ . The impulse response must be absolutely summable.

Derivation

Why stability means an absolutely summable impulse response

Sufficient. If

|x[n]| \le B

for all

n

, then

|y[n]| = \Big|\sum_k h[k]\,x[n - k]\Big| \le \sum_k |h[k]|\,|x[n-k]| \le B \sum_k |h[k]|,

so a finite

\sum|h|

bounds every output.

Necessary. Suppose

\sum |h[k]| = \infty

. Choose the bounded input

x[-k] = \operatorname{sign}(h[k])

, which is

\pm 1

. At

n = 0

y[0] = \sum_k h[k]\,x[-k] = \sum_k |h[k]| = \infty .

A bounded input gave an unbounded output, so the system is unstable. For

h[n] = a^n u[n]

the sum is

1/(1 - |a|)

when

|a| < 1

and infinite otherwise: the accumulator (

a = 1

) fails.

Young man, in mathematics you don't understand things. You just get used to them.

– John von Neumann, as recalled by Felix T. Smith and quoted in Gary Zukav, The Dancing Wu Li Masters (1979), on Wikiquote

💡Convolution reverb

Record a room's impulse response once — a balloon pop or a swept tone deconvolved — and you can make any dry recording sound as if it had been played in that room: convolve it with

h

. Music software ships libraries of measured impulse responses of cathedrals, studios and concert halls. It is Sabine's measurement, put to work by a computer.

⚠Two classic slips

Forgetting the flip computes the correlation $\sum_k x[k]\,h[k - n]$ instead of the convolution. For a symmetric $h$ the two agree, which is why the mistake survives so long.
Forgetting that the output is longer than the input: $N + M - 1$ samples. Truncating it to $N$ silently throws away the tail — the reverberation itself.

💡Where you will use this

The continuous-time version is Lesson 2-2; impulse responses from difference equations are Lesson 2-3. In Unit 4 convolution becomes multiplication of spectra, and in Lesson 6-2 the FFT computes long convolutions fast. Every FIR filter of Unit 9 is a convolution sum with designed weights.

📚Further reading

Oppenheim and Willsky, Signals and Systems, section 2.1 — discrete-time LTI systems and the convolution sum, with the graphical method.
Steven W. Smith, The Scientist and Engineer's Guide to Digital Signal Processing (California Technical Publishing, 1997), chapters 6–7 — convolution from the input and output sides.
Wallace Clement Sabine on Wikipedia — the Fogg Lecture Hall and the reverberation time.

↓But there is a problem

The convolution sum needs samples. But a telescope's optics, an RC circuit and a seismometer respond continuously, to inputs that never come in samples. Let the samples crowd together and the sum turns into an integral. In 1990 a space telescope worth billions of dollars sent home blurred pictures, and for three years astronomers rescued its science by understanding exactly that integral.