Recursive Digital Filters: A Concise Guide

Introduction

A digital filter takes a series of numbers $x_{0},x_{1},\ldots$ as input and produces the series of numbers $y_{0},y_{1},\ldots$ as output. The type of filter we are going to talk about is called a linear time invariant filter. In its most general form the output is related to the input as follows.

	$\displaystyle y_{n}=$	$\displaystyle\;c_{0}x_{n}+c_{1}x_{n-1}+c_{2}x_{n-2}+\ldots+c_{N}x_{n-N}$		(1)
		$\displaystyle+d_{1}y_{n-1}+d_{2}y_{n-2}+\ldots+d_{M}y_{n-M}$

The equation shows that the current output $y_{n}$ is a weighted sum of the current input $x_{n}$ , the previous inputs and the previous outputs. The weight of the $k^{th}$ previous input, $x_{n-k}$ , is the constant $c_{k}$ , and the weight of the $k^{th}$ previous output, $y_{n-k}$ , is the constant $d_{k}$ . Equation 1 can be written more succinctly as

$y_{n}=\sum_{k=0}^{N}c_{k}x_{n-k}+\sum_{k=1}^{M}d_{k}y_{n-k}$

(2)

To find out how the filter behaves you have to take the z-transform of this equation. To take the z-transform of any sequence of numbers $x_{0},x_{1},\ldots$ you multiply each $x_{k}$ by $z^{-k}$ and sum up all the products. Assume for now that is just some complex number and let be the z-transform of the sequence, then the equation is

$X(z)=\sum_{k=0}^{\infty}x_{k}z^{-k}$

(3)

This definition of the z-transform is usually called the one-sided z-transform since the summation goes from to $\infty$ . The full z-transform takes the summation from $-\infty$ to $\infty$ but we will only deal with sequences for which $x_{k}=0$ for so it becomes equivalent to the one sided transform in this case.

The z-transform is a way to compactly represent a possibly infinite sequence of numbers. The following are some examples of z-transforms (in all cases $x_{n}=0$ for ).

$x_{n}=\begin{cases}1,\;n=0\\ 0,\;n>0\end{cases}\qquad\qquad X(z)=1$

(4)

$x_{n}=1,\;n\geq 0\qquad\qquad X(z)=\frac{1}{1-z^{-1}}=\frac{z}{z-1}$

(5)

$x_{n}=n,\;n\geq 0\qquad X(z)=\frac{z^{-1}}{(1-z^{-1})^{2}}=\frac{z}{(z-1)^{2}}$

(6)

In general may not have a simple form as in these examples. If you are familiar with generating functions then the z-transform looks like a generating function for the $x_{n}$ sequence in the variable $z^{-1}$ and this is essentially what it is. If you are not familiar with generating functions, don’t worry, they won’t come up again.

The system function for a digital filter is a z-transform that can be used to analyze how the filter behaves with different inputs. The system function will always have the form of the ratio of two polynomials. To find the system function, multiply both sides of equation 2 by $z^{-n}$ and sum over from to $\infty$ . On the left side of the equation, you have

$\sum_{n=0}^{\infty}y_{n}z^{-n}=Y(z)$

(7)

which is the z-transform of the output sequence. On the right side you have terms of the form

$\sum_{n=0}^{\infty}x_{n-k}z^{-n}\qquad\text{and}\qquad\sum_{n=0}^{\infty}y_{n-% k}z^{-n}$

For the purpose of describing the operation of a digital filter we can assume zero initial conditions which simply means that both the $x_{n}$ and $y_{n}$ sequence is zero for . In this case the above equations are equivalent to

$z^{-k}\sum_{n=0}^{\infty}x_{n}z^{-n}\quad\text{and}\quad z^{-k}\sum_{n=0}^{% \infty}y_{n}z^{-n}$

The summations are the z-transforms of $x_{n}$ and $y_{n}$ so the two equations are just

$z^{-k}X(z)\quad\text{and}\quad z^{-k}Y(z)$

Using these results, the z-transform of equation 2 becomes

$Y(z)=\sum_{k=0}^{N}c_{k}z^{-k}X(z)+\sum_{k=1}^{M}d_{k}z^{-k}Y(z)$

(8)

Rearranging the terms in this equation gives you the filter’s system function

$H(z)=\frac{Y(z)}{X(z)}=\frac{\sum_{k=0}^{N}c_{k}z^{-k}}{1-\sum_{k=1}^{M}d_{k}z% ^{-k}}$

(9)

The system function is the ratio of the z-transform of the output to the input. By definition must also be the z-transform of some sequence which we will call $h_{n}$ . In terms of $h_{n}$ , we can write as

$H(z)=\sum_{n=0}^{\infty}h_{n}z^{-n}$

(10)

The sequence $h_{0},h_{1},\ldots$ is called the impulse response of the filter. The name comes from the fact that it is the response of the filter to the input given by eq. 4 which is called an impulse. Equation 9 says that but for an impulse so we have or

$\sum_{n=0}^{\infty}y_{n}z^{-n}=\sum_{n=0}^{\infty}h_{n}z^{-n}$

(11)

Equating coefficients of $z^{-n}$ gives $y_{n}=h_{n}$ as the output when the input is an impulse. For a general sequence of inputs $x_{0},x_{1},x_{2},\ldots$ the output can be found by convolving the inputs with the impulse response. To see what this means, write as follows

$\displaystyle\sum_{n=0}^{\infty}y_{n}z^{-n}=$	$\displaystyle\left(\sum_{n=0}^{\infty}h_{n}z^{-n}\right)\left(\sum_{n=0}^{% \infty}x_{n}z^{-n}\right)$	(12)
$\displaystyle=$	$\displaystyle\left(h_{0}+h_{1}z^{-1}+h_{2}z^{-2}+\ldots\right)$
	$\displaystyle\left(x_{0}+x_{1}z^{-1}+x_{2}z^{-2}+\ldots\right)$

When you perform the multiplication on the right and equate coefficients of $z^{-n}$ on the two sides of the equation, you find that

$y_{n}=\sum_{k=0}^{n}h_{k}x_{n-k}$

(13)

The summation on the right is called the convolution of the $h_{n}$ and $x_{n}$ sequence. This equation shows why the system function and the impulse response are so important. Suppose the input is $x_{n}=z^{n}$ so that the $n^{th}$ input is the $n^{th}$ power of the complex number . According to eq. 13, the output is then

$y_{n}=\sum_{k=0}^{n}h_{k}z^{n-k}=z^{n}\sum_{k=0}^{n}h_{k}z^{-k}=z^{n}H_{n}(z)$

(14)

The output is the same as the input multiplied by the function $H_{n}(z)$ which looks like the system function . It is not quite the same since the summation only goes to whereas the system function summation goes to infinity, as defined in equation 10.

But we are only interested in stable filters for which $|z|\leq 1$ and the terms in the impulse response, $h_{n}$ , decrease with increasing so that $H_{n}(z)$ becomes closer and closer to as increases, and in the limit $H_{\infty}(z)=H(z)$ . This means that after the filter has been running for awhile, its output for the input $x_{n}=z^{n}$ will, to a good approximation, be $y_{n}=z^{n}H(z)$ . The filter simply multiplies the input by the factor to get the output.

For inputs of the form $x_{n}=z^{n}$ the system function tells you all you need to know about what the output will be. One important class of inputs of this form occurs when $z=e^{j\theta}$ and $x_{n}=e^{jn\theta}=\cos n\theta+j\sin n\theta$ . The $x_{n}$ are points on the unit circle in the complex plane (we are using $j=\sqrt{-1}$ which is the more common convention in engineering work). An example of such a sequence is shown in figure 1.

Figure 1: Sequence of points on the unit circle.

As the index increases, the points $x_{n}$ move around the unit circle in angular steps of size $\theta$ . The angle $\theta$ acts as a dimensionless frequency. To see how this can be related to a real frequency, recall that a periodic function of time, , can be expressed as a Fourier series which is a weighted sum of the complex exponentials $e^{j2\pi kt/T}$ . When the function is sampled at intervals $\Delta t$ then the complex exponentials become $e^{j2\pi kn\Delta t/T}=e^{jn\theta}$ where $\theta=2\pi k\Delta t/T=2\pi f_{k}/s$ , $f_{k}=k/T$ , $k=\ldots-1,0,1,\ldots$ , and $s=1/\Delta t$ is the sampling rate.

The value of $H(e^{j\theta})$ as $\theta$ ranges from to $2\pi$ or $-\pi$ to $\pi$ is the frequency response of the filter. In polar form it can be written as follows

$H(e^{j\theta})=|H(e^{j\theta})|e^{j\Phi}$

(15)

The magnitude $|H(e^{j\theta})|$ measures how much the filter amplifies or attenuates the input $x_{n}=e^{jn\theta}$ and the phase $\Phi$ measures how much the filter shifts its phase.

Since the value of $H(e^{j\theta})$ will generally be complex, we need to represent in the complex plane. The simplest way to do that is with a pole-zero plot. will be a rational function of two polynomials as shown in eq. 9. The poles of are those values of where goes to infinity. These values are the roots of the denominator polynomial, and $z=\infty$ if the numerator degree is greater than the denominator degree. The zeros of are those values of where is zero. These values are the roots of the numerator polynomial, and $z=\infty$ if the denominator degree is greater than the numerator degree. A pole-zero plot of simply shows the location of the poles and zeros in the complex plane along with the unit circle. Poles are represented by a filled circle “ $\bullet$ ”, and zeros by an unfilled circle “ $\circ$ ”.

Let the the zeros of be $a_{i}e^{j\theta_{i}}$ , $i=1,2,\ldots,M$ , and the poles be $b_{i}e^{j\phi_{i}}$ , $i=1,2,\ldots,N$ , then can be written as

$H(z)=A\frac{\prod_{i=1}^{M}(z-a_{i}e^{j\theta_{i}})}{\prod_{i=1}^{N}(z-b_{i}e^% {j\phi_{i}})}$

(16)

In eq. 9 the coefficients of the numerator and denominator polynomial are real. For the filters we will consider, this will always be true. This means that complex poles or zeros must come in conjugate pairs. If $ae^{j\theta}$ is a complex zero then there must be another zero equal to $ae^{-j\theta}$ and likewise for poles.

Substituting $z=e^{j\theta}$ into equation 16 and taking the magnitude and phase gives the following equations

$|H(e^{j\theta})|=A\frac{\prod_{i=1}^{M}(1-2a_{i}\cos(\theta-\theta_{i})+a_{i}^% {2})}{\prod_{i=1}^{N}(1-2b_{i}\cos(\theta-\phi_{i})+b_{i}^{2})}$

(17)

$\Phi=\sum_{i=1}^{M}\arctan\frac{\sin\theta-a_{i}\sin\theta_{i}}{\cos\theta-a_{% i}\cos\theta_{i}}-\sum_{i=1}^{N}\arctan\frac{\sin\theta-b_{i}\sin\phi_{i}}{% \cos\theta-b_{i}\cos\phi_{i}}$

(18)

The following sections will show how these equations are used.

Return to Table of Contents