DFFE is #1!

Thanks to all of you, Digital Filters for Everyone is currently number 1 in signal processing books on Amazon. I am touched and honored. Thank you!

Slide and Divide

Am I the only one who didn't know the slide and divide method?

If you've read my book, or the digital filter courses in this blog, you know that I know a thing or two about math in general, and polynomials in particular. But I hadn't heard of "Slide and Divide" until last week. The excellent math teacher at one of the places where I volunteer as a tutor, e-mailed me to Google on it and learn how to do it. I did, and have now been able to help several of her students with it.

You could also Google it, but I'll show it here for those who haven't seen it. To begin with, let's make an example that we know will be factorable:

(3x + 2)(5x - 4) = 15x^2 -2x -8. (Did I do that right?)

The first thing we do is replace c (the -8 in this case) with the product of a and c = -8 x 15 = -120.

Now, we write a new polynomial: x^2 -2x -120. Note that it is NOT equivalent to the one we're trying to factor. It's just a new polynomial that will help us with our job. So let's factor it. It's easier since a = 1.

(x  + 10)(x - 12)

Now, we have to divide the roots by the 15 by which we multiplied c above. (Repeat caveat about equivalence.)

(x + 10/15)(x - 12/15) = (x + 2/3)(x - 4/5)

Now, in the case of fractional roots such as these, we multiply each factor by its root's denominator: 3(x + 2/3) and 5(x-4/5). (Repeat caveat about equivalence.)

Finally, we simplify those: (3x + 2)(5x - 4)

Ordinarily we could FOIL it back out to check, but there's no need since we started with the same factors above.

Pretty slick right? The fact that it violates equivalence along the way was bothersome at first, but that's really just an accounting problem. One keeps track of what's equivalent and not, and uses the rest as intermediate calculations. In the end it's easy to demonstrate that the result is correct.

Amazon's Top 100

Amazon recently published a list of 100 books to read before you die. I checked, and Digital Filters for Everyone wasn't on it. Could that be right? Hey, get Amazon on the phone... 

Surely we're 101, and didn't quite make the cut? Well, not quite. Surprising though it may seem to those of us who do, there are people in the world who will never bother to design a digital filter. It seems like such a waste.

But I am grateful to my loyal followers who have made Digital Filters for Everyone a top seller within its category. I am humbled by your support.

Errata for Digital Filters for Everyone

Thanks to an attentive reader who found a bug that had been in my First Edition and the 1st Printing of my Second Edition. Note that I missed one spot when correcting, so the bottom of page 19 in the 2nd Printing of the Second Edition still has one mistake. Third Printing of Second Edition, which is what you'll get if you order now (and for the past couple weeks) has all known issues resolved. (Second edition ebook came out only after this was resolved.)

I am less concerned about minor bugs that don't much affect understanding, though I'll continue to try to clean those up too. However, since this particular issue could leave you scratching your head, I'm posting the correction here too. Most of you don't need a new book, you just need to see the correct presentation.

Let me know if you have questions.

(The second half of the slide above is from the bottom of page 19 in the current edition. The 1-alpha part was backwards still in the 2nd Printing of the Second Edition. The other errors, however, were corrected in that printing.)

Upcoming Filter Course: Orlando

I'll be teaching a day long filter seminar at this conference on Wednesday October 9th.

Announcing Second Edition

The second edition of my popular filter book, Digital Filters for Everyone, is now available on Amazon. 

An e-book is coming.

The paper book will also be available from other retailers.

Look Inside and other features of the Amazon page will also be populated. 

All of these things take a little time but they are coming.

When all is said and done I intend to keep the first edition for sale indefinitely, but I do intend to raise the price to $35 since I would like to incentivize buyers to take the newer edition which will continue to be $29.99.

The new edition contains everything that was in the old one but also has a chapter on filter applications, a section on fixed point implementation, and more guidance and use examples for the filter equations. The IIR equations are mathematically equivalent to those of the first edition, but the common denominator is written out only once to simplify the presentation (and programming from the book). Likewise, the simple relationships of numerator coefficients are made explicit: if b3 = b1, this is what is written for b3, rather than the full equation. All in all the book is clearer and easier to follow. Nothing is lost, but many new features will be useful. Enjoy!

Digital Filter University - Course VI: FIR Filters

Now time for the long awaited FIR filters!

The general equation and block diagram for FIR filters are shown below. As we have discussed, there is no feedback, no a coefficients.

FIR filters have only zeros, so it takes more effort to get desired characteristics from them than from IIR filters. But they are also inherently stable. And, while all FIR filters are not linear phase, it is easy to make them have a linear phase characteristic. This requires only that the coefficients be symmetric (conjugate symmetric in the case of complex coefficients) about the center.

Take a look at the following example. The symmetric set of coefficients have a nice linear phase and, hence, constant group delay, while the assymetric case does not.

A very common technique for FIR filter design is the Remez exchange algorithm. You can find the guts of the algorithm in a paper, and you can find software that will perform the optimization for you. I will leave such exercises to you and show you two very simple methods of FIR filter design. You can almost do them on the back of a napkin.

The first method of discussion is the Fourier series method. Note that things change a bit depending upon whether N is even or odd. Note alsos that when N is even, m is not an integer. That's OK; everything works out. Just don't be surprised.

Let's consider an example where fc = 250 Hz and Fs = 10 kHz. Use both N = 150 and N = 175 and see if you can get the results below.



The resulting frequency responses are plotted below. Note that N = 150 corresponds to 149th order, etc.

Here's the equation for a bandstop filter. The book gives equations for HP and BP as well.

This example is for a stop band between 1 and 2 kHz, a 20 kHz sample rate and N = 199. Note that this filter is only defined for N odd.

If we zoom up closely on the magnitude characteristics of any of these filters, we'll find ringing such as seen below for the bandstop filter above.

This ringing is called Gibbs Phenomenon, but, so far as I know, has nothing at all to do with Mark Harmon. Instead, it tends to be what happens when things that ought to be infinite are truncated.

For many applications the ringing might not be an issue, but it's actually also very easy to address using window functions which taper the filter coefficient.

There are many different kinds of window functions; three common ones are defined below.

These functions are plotted below for the case of N = 199.

These are applied just by direct multiplication with the filter coefficients. As you can see, the center coefficients don't change much while those farther out are scaled down significantly.

Note the effects of the various windows on the ringing. Rectangular window is another name for no window. In the right hand plot the original (no window) case is removed so the other cases can be compared.

Now for a different FIR filter design method, frequency sampling.

The double bars in the equation for n denote rounding: 4.5 becomes 5. The topless bracket on the sum in the equation for h(n) is the floor function, which means truncation down to the nearest integer: 4.5 becomes 4.

Let's try a highpass example where N = 17, Fs = 23 kHz and fc = 5 kHz. n from the equation above goes from 0 to 8, so we have frequency points at 0, 11.5 / 8, 23 / 8, ... 11.5 kHz as shown below.

We can then set the gain we'd like to have at each of these frequencies. Since we wanted a 5 kHz cutoff, we can go with 0s up through 4.3 kHz, and 1s thereafter. We did this for the first case (solid line in the plot).

There are three things to consider here:

1) if we made a longer filter we'd have more frequency granularity to work with, as well as a generally nice response, since longer filters do that.

2) Even for a short filter, we don't have to use only 1s and 0s. We can use something in between to transition the filter more gradually, and move its cutoff to points we cannot access directly. Note that the response can even go above 1 if you want to put a gain on part of the signal. Don't take it below 0 though. That's negative infinity dB, which should be enough attentuation for anyone.

3) While it is certainly possible to make coefficients using this method, and then apply windows to them as we did for the Fourier series method. Many times one can achieve much the same effect by making gentle transitions as we did for the second case below. That is, the gentle transisitions serve more than one purpose.

Now, for something even more fun.

Initially let r = 1. Then let's use the equation we derived to place pairs of zeros around the unit circle at various (normalized) frequencies.

Now, those could all be cascaded as 2nd order filters or we can convolve the coefficients together to create one long filter with all these zeros in it, as shown below.

The resulting magnitude response is shown below. Notice that it has nulls at the places we specified out zeros.

Now let's change the value of r and try again.

We still get nulls at the same places, but they are no longer take the magnitude response to 0. Furthermore, we've lost the phase linearity (no longer symmetric).

But, for some applications that might be exactly what we want. At the very least, we learned a thing or two about how zeros behave.