Discrete LTI Systems

Shave off noise with the impulse response

The upper plot draws, as bars from n = 0 to 20, this digital filter's impulse response h[n] = (1 − α)αⁿ; feed in a single impulse δ[n] and exactly this shape comes out. In the lower plot, the faint line is the input x[n], a step that rises from 0 to 1 at n = 10 with noise mixed in, and the gold bars are the output y[n]. The output is the discrete convolution: h[n] slid across the input, multiplied and summed. At the starting α = 0.2, h[n] has a short tail and the noise passes through almost unchanged. Raise the smoothing strength α to stretch the tail and the filter averages more neighbors, shaving off the noise, but push it too far and the corner of the step blurs and rises late.

The impulse response is the whole system

A discrete LTI system is one that is linear (add inputs and the outputs add too) and time-invariant (delay the input and the output is delayed by the same amount). Such a system is completely determined by its impulse response h[n], the output you get when you feed in an impulse δ[n] (1 at n = 0, 0 everywhere else). This one response is enough because any input x[n] can be split into a sum of impulses, Σ x[k]·δ[n−k]. Since the system is linear and time-invariant, the output for each impulse x[k]δ[n−k] is x[k]·h[n−k], and adding them all up gives the total output.

The output is a sliding weighted sum

That sum, y[n] = Σₖ h[k]·x[n−k], is the discrete convolution. For each output time n, you flip the impulse response h in time, lay it over the input at position n, multiply the overlapping samples and add them all up, then shift one step to get the next output. Compared with the continuous convolution of chapter B, the integral ∫ has become the sum Σ and the curves have become samples, but the principle is identical. A short h[n] mixes in only a few nearby points; a long one reaches further into the past. An h shaped like an even average becomes a low-pass filter that shaves off noise, and an h shaped like a difference between neighboring samples becomes a high-pass filter that amplifies change.

FIR and IIR, and the difference equation

If the impulse response ends after a finite length, the filter is FIR (finite impulse response). A moving average of length M, h[n] = 1/M (n = 0, …, M−1), is the classic example; since it only takes a weighted sum of input samples, it is always stable. If instead the filter is a recursion that feeds back past outputs, its impulse response goes on forever, making it IIR (infinite impulse response). The first screen's filter, y[n] = α·y[n−1] + (1 − α)·x[n], is an example: its impulse response h[n] = (1 − α)αⁿ trails on forever. This recursion is the difference equation, and taking its z-transform as in the E3 unit gives H(z) = (1 − α)/(1 − α z⁻¹), with its pole at z = α. The pole must be inside the unit circle (|α| < 1) for the impulse response to die away and the filter to be stable; IIR filters, which produce long responses with few coefficients, are efficient, but they can diverge if a pole moves outside the circle.

Back to the first screen

The single impulse response at the top of the first screen, h[n] = (1 − α)αⁿ, was the whole of this filter. Raising the smoothing strength α stretched the tail of h[n], so the discrete convolution averaged more neighbors and the noise in the output was shaved off; raising it too far blurred the corner of the step. The output was always y[n] = Σₖ h[k]x[n−k], a weighted sum of h slid across the input. Know the response to a single impulse, and by sliding it you can produce the output for any input. Everything about a discrete LTI system was held in that small h[n].

You have seen the result of filtering by convolution in time, but you have not yet seen in numbers exactly which frequencies this filter keeps and which it kills. The next unit, The DTFT and DFT, spreads the impulse response out over frequency. Evaluating the z-transform H(z) of the impulse response on the unit circle, z = e^jω, gives the DTFT, the frequency response of a discrete system, and for an averaging-shaped h it comes out as a low-pass shape that shrinks at high ω. Sampling the never-ending DTFT at a finite number of frequencies so a computer can actually calculate it gives the DFT, and the algorithm that computes it quickly is the FFT. Convolution in time becomes multiplication again in the frequency domain.