Skip to content
Signal Theory

Discrete-time systems and FIR and IIR digital filters

The convolution sum, difference equations, transfer function and frequency response, poles and zeros, the moving average, the first-order recursive filter and stability with proof.

4 min read 0 comments

Once sampled and quantised, a signal is a sequence of numbers x[n], and the systems that process it are programs: a microcontroller filtering a sensor reading, an audio processor equalising music, a modem demodulating. In this lesson we see how discrete-time systems are described, their frequency response and the two big families of digital filters, FIR and IIR.

Linear discrete-time systems

The definitions are those of continuous time with sums instead of integrals. The impulse is \delta[n], equal to 1 for n = 0 and 0 elsewhere; the impulse response h[n] fully describes an LTI system, and the output is the convolution sum

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

The proof is identical to the continuous-time one: x[n] = \sum_k x[k]\delta[n - k], then linearity and time invariance. The system is stable if and only if \sum|h[n]| \lt \infty.

Difference equations

In practice a digital filter is described by a difference equation: the current output is a combination of the current and past inputs and, possibly, past outputs:

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

It is literally the program: at each new sample a few multiplications and additions are done. With the Z transform (Mathematical Methods lesson), where a one-sample delay corresponds to multiplying by z^{-1}, we get the transfer function

    \[ H(z) = \frac{b_0 + b_1 z^{-1} + \dots + b_M z^{-M}}{1 + a_1 z^{-1} + \dots + a_N z^{-N}} \]

The roots of the numerator are the zeros, those of the denominator the poles.

Frequency response

A sampled sinusoid x[n] = e^{j\omega n}, with \omega = 2\pi f/f_s the normalised angular frequency, is an eigensignal: the output is H(e^{j\omega})\,e^{j\omega n}. The frequency response is therefore H(z) evaluated on the unit circle, z = e^{j\omega}. Two differences from continuous time:

  • it is periodic with period 2\pi: angular frequencies differing by 2\pi give the same samples (aliasing seen from the other side);
  • it is enough to study it for 0 \le \omega \le \pi, that is from 0 to f_s/2.

Geometric reading. |H(e^{j\omega})| is small when the point e^{j\omega} is close to a zero, large when it is close to a pole. From the pole-zero plot one can “see” the filter’s behaviour.

Poles and zeros in the complex plane and frequency responses of a moving-average filter and a first-order recursive filter
On the left the unit circle with the four zeros of the five-sample moving average (small circles) and the pole of the recursive filter near 1 (cross). On the right the magnitude of the two frequency responses between 0 and π: the moving average vanishes at 2π/5 and 4π/5, the recursive filter falls smoothly.

FIR filters

A finite impulse response (FIR) filter uses only the inputs: y[n] = \sum_{k=0}^{M} b_k x[n - k], and the impulse response is the sequence of coefficients.

Example: the moving average. y[n] = \frac15(x[n] + x[n-1] + \dots + x[n-4]). Summing the geometric series,

    \[ H(z) = \frac15\sum_{k=0}^{4} z^{-k} = \frac15\cdot\frac{1 - z^{-5}}{1 - z^{-1}} \]

The zeros are the fifth roots of unity except z = 1: e^{j2\pi k/5}, k = 1, \dots, 4. The response vanishes at \omega = 2\pi/5, that is at f_s/5, and at its multiples: it is a simple low-pass that completely removes a disturbance of known frequency. With f_s = 250 Hz, five samples cover one period of the 50 Hz mains, which disappears from the measurement.

Advantages: they are always stable (they have no poles away from the origin) and, with symmetric coefficients, they have exactly linear phase, that is no phase distortion. Drawback: a steep transition needs many coefficients, even hundreds.

IIR filters

An infinite impulse response (IIR) filter also uses past outputs (it is recursive).

Example: the first-order filter. y[n] = a\,y[n-1] + (1 - a)\,x[n], with 0 \lt a \lt 1:

    \[ H(z) = \frac{1 - a}{1 - a z^{-1}},\qquad h[n] = (1 - a)\,a^n\,u[n] \]

One pole at z = a, unity gain at DC. It is the “exponential moving average” used everywhere to smooth noisy readings, with a single multiplication per sample; with a = 0.8 the memory is about 1/(1 - a) = 5 samples. It is the digital equivalent of the RC circuit.

Theorem. A causal LTI system with a rational transfer function is stable if and only if all its poles lie inside the unit circle.

Proof (simple poles). Expanding H(z) in partial fractions, the impulse response is a combination of terms c_i\,p_i^n u[n] (plus possibly a finite number of impulses). The series \sum_n |p_i|^n converges if and only if |p_i| \lt 1, so \sum|h[n]| is finite if and only if all poles have magnitude less than 1. ∎

Advantages: steep transitions with few coefficients; they are designed starting from the classic analogue filters (Butterworth, Chebyshev) with the bilinear transform. Drawbacks: nonlinear phase, and the risk of instability if the coefficients, rounded in finite-precision arithmetic, move a pole outside the circle.

In practice

A digital filter is a loop of a few lines of code:

/* first-order filter with a = 0.8 */
float y = 0.0f;
float filter(float x) {
    y = 0.8f * y + 0.2f * x;
    return y;
}

Digital signal processors (DSPs) have dedicated instructions that perform a multiply and an add in a single cycle, and modern microcontrollers have simplified versions of them. The big advantage over analogue filters is repeatability: no component tolerances, no drift with temperature, and the filter is changed by updating the program.

Related articles

Subscribe
Notify of
guest
0 Comments
Oldest
Newest Most Voted
0
Would love your thoughts, please comment.x
()
x