Recursive filters

Recursive filters, also known as Infinite Impulse Response (IIR) filters, are filters where the output sample is a linear combination of some number of previous inputs and outputs. In other words,

$y[n] = a_0 x[n] + a_1 x[n-1] + ... + a_N x[N] - b_1 y[n-1] - b_2 y[n-2] - ... - b_N y[N]$

We have written the minus signs of the $$b_i$$ to follow most texts (it is more convenient when discussing the transfer function), but authors interchange $$a_i$$ and $$b_i$$. It can be shown that a digital filter is LTI and causal (outputs depend only on previous inputs and outputs) if and only if it can be described by the above equation.

First, consider the effect of this filter on an input of the form $$x[n] = z^n$$ for some $$z$$. Since it is an LTI system that we have $$y[n] = z^i y[n-i]$$. Hence

$y[n] = z^n \frac {a_0 + a_1 z^{-1} + a_2 z^{-2} + ... + a_N z^{-N}} {1 + b_1 z^{-1} + b_2 z^{-2} + ... + b_N z^{-N}}$

This means the transfer function must be

$H(z) = \frac {a_0 + a_1 z^{-1} + a_2 z^{-2} + ... + a_N z^{-N}} {1 + b_1 z^{-1} + b_2 z^{-2} + ... + b_N z^{-N}}$

So to design a digital filter, we need only pick a transfer function with certain zeroes and poles such that $$H(z)$$ behaves in a certain way on the unit circle.

A common method is to design an analog filter first, and then transform it into a digital filter.

Etymology: An digital impulse is the sequence $$1, 0, 0, ...$$. A filter that only depends on previous inputs is called a Finite Impulse Response filter because if we feed an impulse to such a filter, after some time the output signal will be a sequence of zeroes.

If we allow the filter to involve previous outputs, then it is possible for the impulse signal to cause a response that never dies down, hence the term infinite impulse response.

Zeros and poles

Suppose we have a digital with transfer function

$H(z) = a_0\frac{(z - z_1)...(z - z_n)}{(z - p_1) ... (z - p_n)}$

i.e. $$z_1,...,z_n$$ are the zeroes and $$p_1,...,p_n$$ are the poles of $$H(z)$$.

Geometrically speaking, we see that for any point $$z$$ in the complex plane, $$|H(z)|$$ is simply $$|a_0|$$ times the product of the lengths of the distances of $$z$$ from each zero, divided by the product of the lengths of the distances of $$z$$ from each pole.

Using this fact, one can predict the behaviour of simple digital filters by hand, by looking at the distances between points on the unit circle and the zeroes and poles of the transfer function.

Since roots of a polynomial with real coefficients are real or occur in pairs as complex conjugates, to understand filters, we can first study filters with up to two zeroes or poles, and then view all other filters as a combination of them.

For example, the filter $$y[n] = x[n]$$ preserves the input. Thus $$a_0 = 1$$, and all other coefficients are zero, giving the transfer function $$H(z) = 1$$. As expected, $$|H(z)| = 1$$ everywhere: every frequency has a unit gain. More generally, $$y[n] = a x[n - k]$$ has the transfer function $$H(z) = a$$.

One-pole filters

Consider the transfer function

$H(z) = 1 / (1 - r z^{-1}) = z / (z - r)$

for some real number $$r$$. (We consider the complex case when discussing two-pole filters.) If we want a stable filter we must have $$|r|\lt 1$$. If $$r \gt 0$$, the closest point on the unit circle to $$r$$ is 1, and the furthest is $$-1$$, thus we can see that $$|H(z)|$$ decreases as we go from $$1$$ to $$-1$$ along the unit circle. Thus we have a lowpass filter. Similarly, if $$r \lt 0$$, we have a highpass filter.

The square of the frequency response is

$|H(e^{i\theta})|^2 = \frac{1}{r^2 + 1 - 2r cos\theta}$

Thus if $$r \gt 0$$, the peak gain is $$1 / (1-r)$$ at $$\theta = 0$$, otherwise it is $$1/(1+r)$$ at $$\theta = \pi$$.

One-zero filters

Now consider a digital filter with transfer function

$H(z) = (z - r) / z$

Since this is the reciprocal of the previous case, its frequency response is simply the reciprocal of that of the one-pole filter. Thus for $$r \lt 0$$ we obtain a lowpass filter and for $$r \gt 0$$ we obtain a highpass filter.

The square of the frequency response is

$|H(e^{i\theta})|^2 = r^2 + 1 - 2r cos\theta$

Thus if $$r \gt 0$$, the peak gain is $$1 + r$$ at $$\theta = \pi$$, otherwise it is $$1 - r$$ at $$\theta = 0$$.

If we graph the equations for the frequency responses of the one-zero and one-pole filters, we find that the one-pole filter is "sharper".

When $$r = -1$$, we have $$a_0 = a_1 = 1$$, namely, the filter $$y[n] = x[n] + x[n-1]$$. Setting $$z = 1$$ yields the peak gain $$(1 + 1)/ 1 = 2$$ at 0Hz. This explains the surprisingly effective low-pass filter that simply outputs the average of the input and the previous input.

Two-pole filters

If both poles are real, then we may view the filter as a cascade of two one-pole filters that we have described above. Otherwise the poles are complex conjugates.

Consider a single complex pole $$R e^{i a}$$ with $$R\lt 1$$ for stability. The closest point on the unit circle is $$e^{i a}$$, thus it acts as a bandpass filter with resonance at $$a$$. But at $$-a$$ the gain is not maximal which means the peak gain is not actually at $$a$$. The conjugate to this pole has the same effect. Adding them together guarantees the output is real but the peak gain will not be at $$a$$.

It turns out that the 3dB (half-power) bandwidth is approximately

$B = - \frac{ln(R)}{\pi T}$

where $$R$$ is the pole radius, and $$T$$ is the sampling interval in seconds [Smith04].

Two-zero filters

When both zeroes are real, again we may consider the filter as a cascade of two one-zero filters. Otherwise we have the reciprocal of the previous case, so we end up with a notch filter.

Allpass filters

Consider a filter where for each pole $$p$$ there exists a zero $$z$$ with $$|z| = 1 / |p|$$. Then it turns out the filter will have constant gain across all frequencies. Only the phases of the input signal frequencies are affected. Such a filter is called an allpass filter.

DC blockers

By placing a zero at 1, and pole very close to it (e.g. 0.995 for a 44.1kHz sampling rate [Smith04]) we obtain a filter that removes the DC component of a signal.

Ben Lynn blynn@cs.stanford.edu