Digital filters: z-transform and finite-impulse response filters

2014 July 3

Digital filters: z-transform and finite-impulse response filters

Filed under: Uncategorized — gasstationwithoutpumps @ 00:32
Tags: digital filter, finite-impulse reponse, FIR, gnuplot, z-transform

My son decided to try implementing a loudness sensor on the KL25Z board—last night he designed a circuit to interface an electret microphone to the A-to-D on the KL25Z, wired it up, wrote a small test program, and got an LED to be controlled by the loudness on the microphone. He still needs to adjust the gain of his amplifier (the sensitivity was too low) and improve his loudness detection algorithm. Currently the system only responds to very loud noises, but he’d like it to be able to pick out the beat in music even if the music is being played fairly softly.

I think that the best way to do what he wants is with digital filters (and some non-linear computations, like absolute value or squaring), but he doesn’t have any filter theory. I’m going to try writing a few blog posts to cover the basics of implementing some simple digital filters, so that he can try out his ideas.

This post is going to cover the fundamental mathematical tool underlying most digital signal processing: the z-transform (which is related to the Laplace and Fourier transforms in continuous signal processing).

If we have a semi-infinite sequence of numbers, $x_{0}, x_{1}, \ldots$ , then the z-transform of the sequence $X(z)$ is $\sum_{k=0}^{\infty} x_{k} z^{-k}$ . For example, for the constant sequence $x_{k}=c$ , the z-transform is $X(z) = c \sum_{k=0}^{\infty} z^{-k} = \frac{1}{1-z}$ . For the sinusoidal function with angular frequency $\omega$ radians per sample, amplitude A, and phase $\phi$ , $x_{k} = A e^{i(\omega k +\phi)}$ , the z-transform is $X(z) = \frac{Ae^{i\phi}}{1- e^{-i\omega}z}$ .

The z-transform is a linear transform—that is, if we take any two sequences $x_{k}$ and $y_{k}$ with z-transforms $X(z)$ and $Y(z)$ , then the z-transform of $a x_{k} +b y_{k}$ is $a X(z)+ b Y(z)$ .

One thing that is cool about z-transforms is that they can easily represent what happens if we delay a signal. Consider the two sequences $x_{0}, x_{1}, x_{2}, \ldots$ and $0, x_{0}, x_{1}, \ldots$ . If the z-transform of the first sequences is $X(z)$ , then the z-transform of the second sequence is just $z^{-1} X(z)$ .

A linear filter consists just of multiplications by constants, delay elements, and additions. The simplest filters (mathematically) are finite-impulse response filters:

Typical finite-impulse response (FIR) filter

The output $y_{k}$ is computed as $y_{k}=a_{0} x_{k} + a_{1}x_{k-1} + a_{2} x_{k-2} + \cdots a_{5} x_{k-5}$ , and the z-transform is $Y(z) = a_{0} X(z) + a_{1} X(z) z^{-1} + a_{2} X(z) z^{-2} + \cdots a_{5} X(z) z^{-5}$ . We can simplify this to $Y(z)/X(z) = a_{0} + a_{1} z^{-1} + a_{2} z^{-2} + \cdots a_{5} z^{-5}$ , a simple polynomial in $z^{-1}$ . The function $Y(z)/X(z)$ is known as the transfer function of the filter. The transfer function is sometimes written as $H(z)$ .

The impulse response of a filter is the output it provides when the input is 1 for the first sample and 0 thereafter. The z-transform of an impulse is the constant function 1, so the z-transform of the impulse response of a filter is just the transfer function for the filter. For the FIR filter in the picture above, the impulse response is $a_{0}, a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, 0, 0, \ldots$ . Because the response is zero after a while, this is a finite impulse response.

When we are designing or analyzing filters, we often want to think about what they do to sinusoids, since we know that adding, multiplying, and delaying sinusoids of a given frequency $e^{i \omega t}$ produces another sinusoid, but with a different amplitude and phase $A e^{i (\omega t + \phi)}$ .

How do we convert the transfer function of the filter into the phasor $A e^{i \phi}$ ?

Note that delaying a sinusoid by 1 time unit is the same as subtracting $\omega$ from its phase, so multiplying by the z-transform by $z^{-1}$ must be the same as multiplying by $e^{-i\omega}$ or setting $z=e^{i\omega}$ .

So we can get the phasor for a given angular frequency just by plugging $z=e^{i\omega}$ into the transfer function! This makes plotting the amplitude and phase response of a digital filter very simple.

Let’s look at a very simple filter averaging the last 4 samples, so $y_{k}= 1/4 (x_{k} + x_{k-1} + x_{k-2} + x_{k-3})$ , and $H(z)= 1/4 (1+z^{-1}+z^{-2}+z^{-3})$ . If we plot the gain (the absolute value of Y/X) as a function of frequency f, we can see that this is a low-pass filter:

This is a low-pass filter, with the half-power point, where the gain is 0.707, around 0.11536 cycles per sample, and gain goes to zero at frequencies of 1/4 and 1/2 (ω=π/2 or π), but there is a substantial extra peak around a frequency of 0.36614 cycles/sample. It is possible to design low-pass FIR filters with better characteristics than this one!

The phase change is small for small frequencies (as the output is only delayed about 1.5 samples from the input), but does funny things in the higher frequencies.

Here is the gnuplot source code for the gain plot above:

set title "Averaging 4 adjacent samples"
set key bottom left
set samples 10000

set ylabel "Gain (y/x)"
set logscale y
set yrange [0.009:1.1]

set xlabel "frequency [cycles/sample]"
set logscale x
set xrange [0.001:0.5]

# transfer function
H(z)= (1+z**(-1)+z**(-2)+z**(-3))/4

j=sqrt(-1)
amplitude(omega) = abs(H(exp(j*omega)))
phase(omega) = imag(log(H(exp(j*omega)))) * 180/pi  # phase in degrees

plot amplitude(2*pi*x) notitle

I rarely use FIR filters (other than when I’m being very lazy and just averaging a few samples for downsampling), but usually use infinite-response filters, which I’ll leave for a subsequent post.

Comments (1)

1 Comment »

[…] I wrote a very brief introduction to z-transforms and finite-impulse-response filters. Today I’ll try to do infinite-impulse-response (IIR) filters. Obviously, one blog post […]

Pingback by Digital filters: infinite-impulse-response filters | Gas station without pumps — 2014 July 3 @ 17:13 | Reply

RSS feed for comments on this post. TrackBack URI

Gas station without pumps

2014 July 3