4.3 — LTI Systems and Convolution

Hit a bell once. It rings and fades. That ringing is the bell's impulse response — everything the bell does, in one measurement.

Now play a whole tune on the bell. Each strike sets off the same ringing, scaled by how hard you hit and shifted to when you hit. What you hear is all those overlapping rings added together.

That is convolution. The rest of this chapter is that sentence made precise, and then made calculable.

1. The impulse response

For an LTI system, h(t) is defined as the output when the input is a unit impulse \delta(t).

Chapter 4.2 showed that for an LTI system this single signal determines everything. Here is the argument once more, in continuous time, because it is worth seeing both ways.

Start from the sifting property of Chapter 4.1:

x(t)=\int_{-\infty}^{\infty}x(\tau)\delta(t-\tau)\,d\tau

Read that as a decomposition rather than a triviality. It says: the signal x is a continuous sum of impulses, one at each instant \tau, each weighted by the signal's value there.

Now feed it through the system.

• The system's response to \delta(t) is h(t), by definition.
• Time-invariance: its response to \delta(t-\tau) must be h(t-\tau).
• Linearity: its response to a weighted sum is the weighted sum of the responses, and this holds for a continuous sum (an integral) as well as a discrete one.

\boxed{y(t)=\int_{-\infty}^{\infty}x(\tau)h(t-\tau)\,d\tau = x(t)*h(t)}

The asterisk denotes convolution. In discrete time the integral is a sum:

y[n]=\sum_{k=-\infty}^{\infty}x[k]h[n-k]

The physical reading, which is the one to hold on to: the output right now is built from all the past inputs, each weighted by how much the system still remembers of an input from that long ago. h(t-\tau) is exactly "how much does the system still remember, now at time t, of what happened at time \tau".

2. Making convolution visual

The formula has h(t-\tau) in it, and the minus sign in front of \tau means the impulse response appears reversed in the integral. That reversal is where every misunderstanding starts, so here is the mechanical procedure.

The four steps: flip, shift, multiply, integrate.

1. Flip. Take h(\tau) and reverse it to get h(-\tau).
2. Shift. Slide it right by t to get h(t-\tau).
3. Multiply. Multiply point by point with x(\tau).
4. Integrate. The area under that product is y(t), one single number.

Then repeat for every t, sliding the flipped h across the whole of x and recording the overlap area at each position.

Convolution of two rectangular pulses. The flipped impulse response slides across the input; the overlap area starts at zero, grows linearly, peaks at full overlap, and falls away. Plotting that area against position gives a triangle, twice as wide as either input.

Two facts worth extracting from the picture, because they are the sanity checks you will use constantly:

• Widths add. Convolving a signal of width W_1 with one of width W_2 gives a result of width W_1+W_2. A 3-sample input through a 5-tap filter gives 7 samples.
• Areas multiply. \int y = \left(\int x\right)\left(\int h\right). If you convolve with something whose area is 1, the total area of your signal is preserved — which is why filter coefficients are normalised to sum to 1 when you do not want the signal's average level to change.

3. Worked discrete convolution

x[n]=\{1,2,3\} starting at n=0, and h[n]=\{1,1,1\} — a three-point moving sum.

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

Compute each output index by listing which products contribute.

n=0: only k=0 overlaps. y[0]=x[0]h[0]=1\times1=1

n=1: k=0,1. y[1]=x[0]h[1]+x[1]h[0]=1+2=3

n=2: k=0,1,2. y[2]=1\times1+2\times1+3\times1=6

n=3: k=1,2 (since h ended). y[3]=2+3=5

n=4: k=2. y[4]=3

y[n]=\{1,3,6,5,3\}

Check the length: 3+3-1=5 ✓. Check the area: \sum x=6, \sum h=3, product 18; and 1+3+6+5+3=18 ✓.

The polynomial multiplication trick

Notice something. Write x and h as polynomial coefficients:

(1+2z+3z^2)(1+z+z^2) = 1+3z+6z^2+5z^3+3z^4

Identical. Convolution is polynomial multiplication, and it is also long multiplication of numbers without carrying. Multiply 123 by 111 and you get 13,653 — the same digits, once the carries are done.

Why this matters: it is the bridge to Chapter 4.6. The Z-transform makes a signal into a polynomial, and multiplying polynomials is exactly what convolution does, so convolution in time becomes multiplication in the transform domain. That is the single most useful fact in this entire Part.

4. Properties, and what each one buys

Commutative: x*h = h*x.

Swapping which signal is called the input and which the system changes nothing. Practically: flip whichever one is simpler. For a 3-tap filter on a 10,000-sample signal, flip the filter.

Associative: (x*h_1)*h_2 = x*(h_1*h_2).

Two systems in series are equivalent to one system whose impulse response is the convolution of the two. This is why you can design a complicated filter as a chain of simple sections and then, if you want, collapse them into one.

Distributive: x*(h_1+h_2) = x*h_1+x*h_2.

Two systems in parallel add their impulse responses.

Identity: x*\delta = x. Convolving with an impulse changes nothing, which is what "unit impulse" means.

Shifting: x(t)*\delta(t-t_0)=x(t-t_0). Convolving with a shifted impulse shifts the signal. A pure delay line has h(t)=\delta(t-t_0), and echo effects are built by convolving with a few impulses at chosen delays.

Differentiation: \frac{d}{dt}(x*h) = \frac{dx}{dt}*h = x*\frac{dh}{dt}. The derivative can be applied to either one.

5. Convolution as filtering — where the intuition pays

Three impulse responses, three familiar behaviours.

Moving average — a low-pass filter

h[n]=\tfrac15\{1,1,1,1,1\}

Each output is the average of five neighbouring inputs. Rapid changes get averaged away; slow ones survive. It is a low-pass filter, and the coefficients sum to 1 so the average level is unchanged.

Chapter 5.2 shows its frequency response is a sinc-shaped curve with awkward ripples, which is why it is not a good low-pass filter. But it is the cheapest one that exists and it is everywhere in embedded code.

Difference — a high-pass filter

h[n]=\{1,-1\}

Each output is the change from one sample to the next. Constants vanish; rapid changes are emphasised. A high-pass filter, and a discrete differentiator.

Its coefficients sum to zero, which is exactly the condition for killing DC.

The exponential — a first-order low-pass

h[n]=(1-\alpha)\alpha^n u[n]

Each output is a weighted average of all past inputs, with the weight decaying geometrically into the past. This is the discrete equivalent of the RC filter from Chapter 1.5, and it is implemented in one line:

y[n]=\alpha y[n-1]+(1-\alpha)x[n]

That single line is the most-used filter in all of embedded software — smoothing a sensor reading, tracking a running average, damping a display. Its infinite impulse response comes for free from the feedback, which is why it costs one multiply and one add instead of the dozens a moving average of similar smoothness would need.

6. Correlation, and why it is not convolution

Cross-correlation looks almost identical but has no flip:

R_{xy}(\tau)=\int x(t)y(t-\tau)\,dt

It measures similarity as a function of relative shift. Where the correlation peaks tells you the delay at which the two signals line up best.

The relationship is exactly one flip:

R_{xy}(\tau)=x(\tau)*y(-\tau)

Autocorrelation is a signal correlated with itself. It peaks at zero lag (a signal always matches itself best), and it reveals hidden periodicity: a periodic component produces a secondary peak at its period, even when the signal looks like pure noise on a plot.

Where correlation is the whole technique:

• Radar and sonar. Transmit a known pulse, correlate the echo with it, and the peak position gives the time of flight and therefore the range. Correlating rather than simply detecting the echo pulls signals out of noise far below the noise floor, because the noise correlates with the reference at only chance levels.
• GPS. Chapter 8.2 in full: each satellite transmits a distinct pseudorandom code, and the receiver correlates against each code. The peak's timing gives the range and the code identifies the satellite. The received signal is far below the thermal noise floor, and correlation is the only reason it can be found at all.
• Pitch detection. Autocorrelate a voice segment and the first strong peak after zero is the pitch period.
• Template matching in images. Correlate a small patch with a large image; the peak is where it occurs.

The name "matched filter" is the same idea from the systems side: the filter that maximises the signal-to-noise ratio when detecting a known shape in noise is the one whose impulse response is that shape, reversed. Chapter 7.3 uses it for every digital receiver.

7. The circular convolution trap

When Chapter 5.1 computes convolution using the FFT, something changes that is a genuine source of bugs.

The FFT computes circular convolution, in which the signal is treated as if it wraps around: what falls off the right end reappears on the left. That is not usually what you want, and the symptom is that the beginning of your output is contaminated by material from the end.

The fix is zero-padding. If x has length N and h has length M, the true linear convolution has length N+M-1. Pad both to at least that length with zeros before transforming, and the wrap-around lands entirely in the zeros where it does no harm.

Worked example. A 1000-sample block and a 100-tap filter. The result is 1099 samples, so pad both to 2048 (the next power of two, which the FFT prefers) and the circular result equals the linear one exactly.

For a continuous stream you cannot pad forever, so the standard techniques are overlap-add (convolve each block separately and add the overlapping tails) and overlap-save (process overlapping blocks and discard the contaminated portion of each). Chapter 5.1 develops both.

8. Why convolution is worth the effort

\text{cost} = O(NM)

for a length-N signal and length-M filter. For 10,000 samples and a 100-tap filter that is a million multiply-accumulate operations — real work.

Via the FFT it becomes O((N+M)\log(N+M)). For the same numbers that is about 130,000 operations, roughly eight times faster, and the advantage grows with size. For a 4096-tap filter the speedup is over two hundredfold, which is the difference between real-time and not.

But the deeper reason to understand convolution is not computational. It is that convolution in time equals multiplication in frequency:

x(t)*h(t) \;\longleftrightarrow\; X(f)\cdot H(f)

That single correspondence is why frequency-domain thinking dominates this entire volume. A messy sliding-and-integrating operation becomes ordinary multiplication. Cascading filters becomes multiplying their responses. Designing a filter becomes drawing the shape you want in frequency and transforming back.

The next chapter builds the transform that makes that correspondence true.

---

Chapter 4.4 introduces the Fourier series and transform, and turns the sliding integral of this chapter into a product.

Every formula above, built from scratch

None of the results in this chapter are worth memorising, because each one can be rebuilt in under a minute from something simpler. What follows is that rebuilding, one result at a time, so the formula and the reason for it sit on the same page as the explanation that needed them.

Convolution

y(t)=\int_{-\infty}^{\infty}x(\tau)h(t-\tau)d\tau, \qquad y[n]=\sum_kx[k]h[n-k]

Derivation: write x as a sum of scaled shifted impulses (the sifting property), apply time-invariance to say each impulse produces a shifted h, then apply linearity to add the responses.

Properties:

x*h=h*x, \qquad (x*h_1)*h_2=x*(h_1*h_2), \qquad x*(h_1+h_2)=x*h_1+x*h_2

x*\delta=x, \qquad x(t)*\delta(t-t_0)=x(t-t_0)

Length: N+M-1 for inputs of length N and M.

Area: \int y = \left(\int x\right)\left(\int h\right).

Cost: O(NM) directly, O(N\log N) via the FFT.

Correlation

R_{xy}(\tau)=\int x(t)y(t-\tau)dt = x(\tau)*y(-\tau)

Convolution flips one signal; correlation does not. Autocorrelation peaks at zero lag.