Digital Signal Processing. The Scientist and Engineers Guide. Steven W. Smith

610 END

TABLE 18-1

for standard convolution is directly proportional to the number of points in the filter kernel. In comparison, the time required for FFT convolution increases very slowly, only as the logarithm of the number of points in the

Impulse Response Length

filter kernel. The crossover occurs when the filter kernel has about 40 to 80 samples (depending on the particular hardware used).

The important idea to remember: filter kernels shorter than about 60 points can be implemented faster with standard convolution, and the execution time is proportional to the kernel length. Longer filter kernels can be implemented faster with FFT convolution. With FFT convolution, the filter kernel can be made as long as you like, with very little penalty in execution time. For instance, a 16,000 point filter kernel only requires about twice as long to execute as one with only 64 points.

The speed of the convolution also dictates the precision of the calculation (just as described for the FFT in Chapter 12). This is because the round-off error in the output signal depends on the total number of calculations, which is directly proportional to the computation time. If the output signal is calculated faster, it will also be calculated more precisely. For instance, imagine convolving a signal with a 1000 point filter kernel, with single precision floating point. Using standard convolution, the typical round-off noise can be expected to be about 1 part in 20,000 (from the guidelines in Chapter 4). In comparison, FFT convolution can be expected to be an order of magnitude faster, and an order of magnitude more precise (i.e., 1 part in 200,000).

Keep FFT convolution tucked away for when you have a large amount of data to process and need an extremely long filter kernel. Think in terms of a million sample signal and a thousand point filter kernel. Anything less won't justify the extra programming effort. Don't want to write your own FFT convolution routine? Look in software libraries and packages for prewritten code. Start with this book's web site (see the copyright page).

CHAPTER

Recursive Filters

19

Recursive filters are an efficient way of achieving a long impulse response, without having to perform a long convolution. They execute very rapidly, but have less performance and flexibility than other digital filters. Recursive filters are also called Infinite Impulse Response (IIR) filters, since their impulse responses are composed of decaying exponentials. This distinguishes them from digital filters carried out by convolution, called Finite Impulse Response (FIR) filters. This chapter is an introduction to how recursive filters operate, and how simple members of the family can be designed. Chapters 20, 26 and 33 present more sophisticated design methods.

The Recursive Method

To start the discussion of recursive filters, imagine that you need to extract information from some signal, x[ ]. Your need is so great that you hire an old mathematics professor to process the data for you. The professor's task is to filter x[ ] to produce y[ ], which hopefully contains the information you are interested in. The professor begins his work of calculating each point in y[ ] according to some algorithm that is locked tightly in his over-developed brain. Part way through the task, a most unfortunate event occurs. The professor begins to babble about analytic singularities and fractional transforms, and other demons from a mathematician's nightmare. It is clear that the professor has lost his mind. You watch with anxiety as the professor, and your algorithm, are taken away by several men in white coats.

You frantically review the professor's notes to find the algorithm he was using. You find that he had completed the calculation of points y[0] through y[27] , and was about to start on point y[28] . As shown in Fig. 19-1, we will let the variable, n, represent the point that is currently being calculated. This means that y[n] is sample 28 in the output signal, y[n& 1] is sample 27, y[n& 2] is sample 26, etc. Likewise, x[n] is point 28 in the input signal,

319

x[n& 1] is point 27, etc. To understand the algorithm being used, we ask ourselves: "What information was available to the professor to calculate y[n] , the sample currently being worked on?"

The most obvious source of information is the input signal, that is, the values: x[n], x[n& 1], x[n& 2], þ. The professor could have been multiplying each point in the input signal by a coefficient, and adding the products together:

y [n ] ' a0 x [n ] % a1 x [n & 1] % a2 x [n & 2] % a3 x [n & 3] % þ

You should recognize that this is nothing more than simple convolution, with the coefficients: a0, a1, a2, þ, forming the convolution kernel. If this was all the professor was doing, there wouldn't be much need for this story, or this chapter. However, there is another source of information that the professor had access to: the p r e v i o u s l y calculated values of the output signal, held in: y[n& 1], y[n& 2], y[n& 3], þ. Using this additional information, the algorithm would be in the form:

In words, each point in the output signal is found by multiplying the values from the input signal by the "a" coefficients, multiplying the previously calculated values from the output signal by the "b" coefficients, and adding the products together. Notice that there isn't a value for b0 , because this corresponds to the sample being calculated. Equation 19-1 is called the recursion equation, and filters that use it are called recursive filters. The "a" and "b" values that define the filter are called the recursion coefficients. In actual practice, no more than about a dozen recursion coefficients can be used or the filter becomes unstable (i.e., the output continually increases or oscillates). Table 19-1 shows an example recursive filter program.

Recursive filters are useful because they bypass a longer convolution. For instance, consider what happens when a delta function is passed through a recursive filter. The output is the filter's impulse response, and will typically be a sinusoidal oscillation that exponentially decays. Since this impulse response in infinitely long, recursive filters are often called infinite impulse response (IIR) filters. In effect, recursive filters convolve the input signal with a very long filter kernel, although only a few coefficients are involved.

FIGURE 19-1

Recursive filter notation. The output sample being calculated, y[n] , is determined by the values from the input signal, x[n], x[n& 1], x[n& 2], þ, as well as the previously calculated values in the output signal, y[n& 1], y[n& 2], y[n& 3], þ. These figures are shown for n ' 28 .

The relationship between the recursion coefficients and the filter's response is given by a mathematical technique called the z-transform, the topic of Chapter 33. For example, the z-transform can be used for such tasks as: converting between the recursion coefficients and the frequency response, combining cascaded and parallel stages into a single filter, designing recursive systems that mimic analog filters, etc. Unfortunately, the z-transform is very mathematical, and more complicated than most DSP users are willing to deal with. This is the realm of those that specialize in DSP.

There are three ways to find the recursion coefficients without having to understand the z-transform. First, this chapter provides design equations for several types of simple recursive filters. Second, Chapter 20 provides a "cookbook" computer program for designing the more sophisticated Chebyshev low-pass and high-pass filters. Third, Chapter 26 describes an iterative method for designing recursive filters with an arbitrary frequency response.

FIGURE 19-2

Single pole low-pass filter. Digital recursive filters can mimic analog filters composed of resistors and capacitors. As shown in this example, a single pole low-pass recursive filter smoothes the edge of a step input, just as an electronic RC filter.

Single Pole Recursive Filters

Figure 19-2 shows an example of what is called a single pole low-pass filter. This recursive filter uses just two coefficients, a0 ' 0.15 and b1 ' 0.85 . For this example, the input signal is a step function. As you should expect for a low-pass filter, the output is a smooth rise to the steady state level. This figure also shows something that ties into your knowledge of electronics. This lowpass recursive filter is completely analogous to an electronic low-pass filter composed of a single resistor and capacitor.

The beauty of the recursive method is in its ability to create a wide variety of responses by changing only a few parameters. For example, Fig. 19-3 shows a filter with three coefficients: a0 ' 0.93 , a1 ' & 0.93 and b1 ' 0.86 . As shown by the similar step responses, this digital filter mimics an electronic RC high-pass filter.

These single pole recursive filters are definitely something you want to keep in your DSP toolbox. You can use them to process digital signals just as you would use RC networks to process analog electronic signals. This includes everything you would expect: DC removal, high-frequency noise suppression, wave shaping, smoothing, etc. They are easy to program, fast

Digital Filter

to execute, and produce few surprises. The coefficients are found from these simple equations:

The characteristics of these filters are controlled by the parameter, x, a value between zero and one. Physically, x is the amount of decay between adjacent samples. For instance, x is 0.86 in Fig. 19-3, meaning that the value of each sample in the output signal is 0.86 the value of the sample before it. The higher the value of x, the slower the decay. Notice that the

FIGURE 19-4

Example of single pole recursive filters. In (a), a high frequency burst rides on a slowly varying signal. In (b), single pole low-pass and high-pass filters are used to separate the two components. The low-pass filter uses x = 0.95, while the high-pass filter is for x = 0.86.

filter becomes unstable if x is made greater than one. That is, any nonzero value on the input will make the output increase until an overflow occurs.

The value for x can be directly specified, or found from the desired time constant of the filter. Just as R× C is the number of seconds it takes an RC circuit to decay to 36.8% of its final value, d is the number of samples it takes for a recursive filter to decay to this same level:

EQUATION 19-4

Time constant of single pole filters. This

equation relates the amount of decay x ' e & 1 /d between samples, x, with the filter's time

constant, d, the number of samples for the filter to decay to 36.8%.

For instance, a sample-to-sample decay of x ' 0.86 corresponds to a time constant of d ' 6.63 samples (as shown in Fig 19-3). There is also a fixed relationship between x and the -3dB cutoff frequency, fC , of the digital filter:

EQUATION 19-5

Cutoff frequency of single pole filters.

The amount of decay between samples, x, x ' e & 2 BfC is related to the cutoff frequency of the

filter, fC , a value between 0 and 0.5.

This provides three ways to find the "a" and "b" coefficients, starting with the time constant, the cutoff frequency, or just directly picking x.

Figure 19-4 shows an example of using single pole recursive filters. In (a), the original signal is a smooth curve, except a burst of a high frequency sine wave. Figure (b) shows the signal after passing through low-pass and high-pass filters. The signals have been separated fairly well, but not perfectly, just as if simple RC circuits were used on an analog signal.

Frequency

Figure 19-5 shows the frequency responses of various single pole recursive filters. These curves are obtained by passing a delta function through the filter to find the filter's impulse response. The FFT is then used to convert the impulse response into the frequency response. In principle, the impulse response is infinitely long; however, it decays below the single precision roundoff noise after about 15 to 20 time constants. For example, when the time constant of the filter is d ' 6.63 samples, the impulse response can be contained in about 128 samples.

The key feature in Fig. 19-5 is that single pole recursive filters have little ability to separate one band of frequencies from another. In other words, they perform well in the time domain, and poorly in the frequency domain. The frequency response can be improved slightly by cascading several stages. This can be accomplished in two ways. First, the signal can be passed through the filter several times. Second, the z-transform can be used to find the recursion coefficients that combine the cascade into a single stage. Both ways work and are commonly used. Figure (c) shows the frequency response of a cascade of four low-pass filters. Although the stopband attenuation is significantly improved, the roll-off is still terrible. If you need better performance in the frequency domain, look at the Chebyshev filters of the next chapter.

The four stage low-pass filter is comparable to the Blackman and Gaussian filters (relatives of the moving average, Chapter 15), but with a much faster execution speed. The design equations for a four stage low-pass filter are:

Narrow-band Filters

A common need in electronics and DSP is to isolate a narrow band of frequencies from a wider bandwidth signal. For example, you may want to eliminate 60 hertz interference in an instrumentation system, or isolate the signaling tones in a telephone network. Two types of frequency responses are available: the band-pass and the band-reject (also called a notch filter). Figure 19-6 shows the frequency response of these filters, with the recursion coefficients provided by the following equations: