Convolution — The Core Operation | DSP-101

The Operation That Defines LTI Systems

In the previous lesson we established that a Linear Time-Invariant (LTI) system is fully characterized by its impulse response h[n]. But how do we actually compute the output y[n] for an arbitrary input x[n]? The answer is convolution — arguably the single most important mathematical operation in all of signal processing.

Convolution is not just a formula to memorize. It emerges naturally from two facts we already know: any signal can be decomposed into a weighted sum of shifted impulses (the sifting property), and an LTI system's response to a shifted, scaled impulse is a shifted, scaled copy of h[n] (by linearity and time-invariance). Put those two facts together and the convolution sum falls out immediately.

The Convolution Sum

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

y[n] is the output of an LTI system with impulse response h[n] when driven by input x[n]. The sum runs over all integers k; in practice it is finite when x or h has finite duration.

The shorthand notation y[n] = (x * h)[n] uses an asterisk to denote convolution. Be careful: in continuous-time signal processing the asterisk also means complex conjugate — context always disambiguates. In discrete-time DSP, x[n] * h[n] unambiguously means the convolution sum above.

Where the Convolution Sum Comes From

Start with the sifting property of the unit impulse δ[n]: any signal x[n] can be written as a superposition of scaled, shifted impulses:

Sifting Property

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

Every sample x[k] weights a unit impulse centered at k. The signal is the sum of all these weighted, shifted impulses.

Now apply the LTI system T{·} to both sides. By linearity, T passes through the sum and the scaling constants. By time-invariance, the response to δ[n − k] is h[n − k] (a k-sample-delayed copy of h[n]). Therefore:

Convolution Derived

y[n] = T\!\left\{\sum_k x[k]\,\delta[n-k]\right\} = \sum_k x[k]\,h[n-k]

Linearity lets the sum pass through T. Time-invariance converts T{δ[n−k]} into h[n−k]. The result is the convolution sum — derived, not assumed.

This derivation makes clear why convolution is not just a clever algorithm: it is the necessary consequence of what it means to be an LTI system. Any system that is both linear and time-invariant must produce its output via convolution. If a system cannot be expressed this way, it is either nonlinear or time-varying.

Graphical Interpretation: Flip, Shift, Multiply, Sum

The four-word mantra “flip, shift, multiply, sum” describes how to evaluate the convolution sum at any single output index n. Think of it as sliding a reversed copy of h over x, multiplying element-wise at each position, and summing the products.

Step 1

Flip

Time-reverse h to get h[−k]. This is the kernel viewed “backwards” along the k-axis.

Step 2

Shift

Translate the flipped kernel by n samples to get h[n−k]. As n increases, the kernel slides rightward.

Step 3

Multiply

Compute the element-wise product x[k] · h[n−k] for every integer k.

Step 4

Sum

Add all the products together. The total is y[n], a single output sample.

Repeat for every value of n to build the complete output sequence. Although this sounds mechanical, the visual intuition is powerful: convolving a signal with a box filter (a rectangle of ones) computes a local average — each output sample is the mean of a sliding window. Convolving with a differentiator kernel highlights abrupt changes. Convolving with an echo kernel superimposes a delayed copy. Every finite-length filter is “its convolution kernel.”

Worked Example

Let x[n] = {1, 2, 3} (nonzero for n = 0, 1, 2) and h[n] = {1, 1} (nonzero for n = 0, 1). The output has length 3 + 2 − 1 = 4 samples.

y[0] = x[0]h[0] = 1·1 = 1

y[1] = x[0]h[1] + x[1]h[0] = 1·1 + 2·1 = 3

y[2] = x[1]h[1] + x[2]h[0] = 2·1 + 3·1 = 5

y[3] = x[2]h[1] = 3·1 = 3

y[n] = {1, 3, 5, 3} — the moving sum of the two-element window.

Algebraic Properties of Convolution

Convolution obeys three algebraic laws that mirror those of ordinary multiplication and simplify the analysis of cascaded and parallel systems:

Commutative

x[n]*h[n] = h[n]*x[n]

You can convolve in either order: x * h = h * x.

Associative

(x*h_1)*h_2 = x*(h_1*h_2)

Two cascaded filters can be replaced by a single combined filter.

Distributive

x*(h_1+h_2) = x*h_1 + x*h_2

Parallel filters can be merged: filtering with (h₁ + h₂) is the same as filtering with h₁ and h₂ separately and adding the outputs.

The commutative property is particularly surprising: it says that applying filter h to signal x gives exactly the same result as applying signal x to filter h. While the two interpretations sound very different, the mathematics is identical. Practically, engineers often pick whichever variable to flip and slide based on which computation is easier for the specific signals involved.

The associative property is the foundation of filter design: two LTI systems in cascade (output of the first feeds the second) behave as a single LTI system whose impulse response is h₁ * h₂. This means the order of cascaded filters does not affect the final output, and a bank of cascaded filters can be pre-computed into one combined kernel offline.

Convolution with the Impulse: The Identity Operation

The unit impulse δ[n] acts as the identity element for convolution, in the same way that multiplying by 1 leaves a number unchanged:

Convolution Identity

x[n]*\delta[n] = x[n]

Convolving any signal with the unit impulse returns the signal unchanged. An LTI system with h[n] = δ[n] is the identity system — it passes every signal through without modification.

More generally, convolving with a shifted impulse δ[n − n₀] produces a pure delay: x[n] * δ[n − n₀] = x[n − n₀]. This tells us that an ideal delay line is an LTI system whose impulse response is a single sample at time n₀. Every digital delay buffer, echo unit, and reverberator is built from this principle.

Output Length and Computational Complexity

When x[n] has N nonzero samples and h[n] has M nonzero samples, the convolution y[n] = x * h has exactly N + M − 1 nonzero samples. This is easy to see: the first nonzero output sample occurs when the first nonzero samples of x and h overlap, and the last occurs when the last nonzero samples of each pass through each other.

Output Length

L_y = N + M - 1

A signal of length N convolved with a kernel of length M produces an output of length N + M − 1. For an IIR filter (infinite M), the output extends indefinitely.

Direct computation of the convolution sum requires approximately N · M multiply-accumulate operations per output sample — O(N·M) overall. For long signals and long filters this can be expensive. The Fast Fourier Transform (FFT) offers a way to compute convolution in O((N+M) log(N+M)) operations using the convolution theorem, which states that convolution in time equals pointwise multiplication in frequency. This FFT-based convolution is the workhorse of modern audio processing, image filtering, and communications systems.

Direct vs. FFT Convolution

For a 1-second audio segment at 44,100 Hz (N = 44,100 samples) filtered by a room impulse response of 0.5 seconds (M = 22,050 samples), direct convolution requires roughly 44,100 × 22,050 ≈ 972 million multiplications. FFT convolution reduces this to around (66,150) × log₂(66,150) ≈ 1.1 million operations — nearly 1000× faster. In practice, the overlap-add or overlap-save method applies FFT convolution in streaming blocks.

Direct: O(N·M) | FFT: O((N+M) log(N+M))

FIR and IIR: Two Families of LTI Systems

Convolution naturally divides LTI systems into two families based on the duration of the impulse response:

FIR (Finite Impulse Response) systems have an impulse response h[n] that is nonzero for only a finite number of samples. Their convolution sum is a finite sum — easy to compute directly and guaranteed to be stable. Moving-average filters, matched filters, and most window-designed filters are FIR. The output at any instant n depends on a finite window of past inputs.

IIR (Infinite Impulse Response) systems have an impulse response that extends to infinity. They are typically implemented via difference equations rather than direct convolution, because summing infinitely many terms is not feasible. A first-order recursive filter y[n] = αy[n−1] + x[n] has impulse response h[n] = αⁿu[n] — it decays exponentially but never truly ends. IIR filters can achieve sharp frequency selectivity with far fewer coefficients than equivalent FIR filters, but they require careful stability analysis (|α| < 1 for the example above).

FIR Output

y[n] = \sum_{k=0}^{M-1} h[k]\,x[n-k]

Finite sum over M taps. Always stable; linear phase achievable.

IIR Difference Equation

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

Recursive: output depends on past outputs. Stable when |α| < 1.

The next lesson explores the Impulse Response and LTI Systems in depth: how to characterize any LTI system through h[n], how FIR and IIR difference equations generate their impulse responses, and how cascaded and parallel systems combine.

Key Takeaways

Convolution y[n] = Σ x[k]·h[n−k] is the fundamental output formula for any LTI system; it follows directly from linearity, time-invariance, and the sifting property.
The four-step graphical method — flip h, shift by n, multiply with x element-wise, sum — provides an intuitive way to evaluate convolution at each output index.
Convolution is commutative (x*h = h*x), associative ((x*h₁)*h₂ = x*(h₁*h₂)), and distributive over addition.
The unit impulse δ[n] is the identity element: x[n] * δ[n] = x[n]; a shifted impulse δ[n−n₀] acts as a pure delay.
Convolving a length-N signal with a length-M kernel produces a length-(N+M−1) output; direct computation costs O(N·M), while FFT convolution costs O((N+M)log(N+M)).
FIR systems have finite-length impulse responses and are always stable; IIR systems have infinite-length impulse responses, implemented via recursive difference equations, and require explicit stability checks.