datasheets.com EBN.com EDN.com EETimes.com Embedded.com PlanetAnalog.com TechOnline.com
Events
UBM Tech
UBM Tech

Design Article

# Analyze FIR filters using high-school algebra

## 2/15/2012 2:28 PM EST

Thinking about FIR filters as polynomials

So, here's the mental connection I want you to make: think of that ordered sequence of values, representing the coefficients of our FIR filter, as a polynomial in some variable, we'll call it z. A polynomial is just the sum of successive powers of our variable, each one multiplied by some coefficient. That's like we just defined our FIR filter to be.

When working with sampled signals and the systems that process them, we make heavy use of this variable z, and also its inverse, z^-1. It doesn't have a simple physical meaning, but it's intimately associated with time. z^-1 is particularly connected with the act of delaying a signal by a single sample period (mathematically, it's referred to as an operator).

In a causal system, the output can only be influenced by things that have already happened, in other words delayed versions of an input signal. The consequence is that you'll mostly find negative powers of z turning up in filter equations. We can just multiply through by some large power of z to make the polynomials have a much more familiar form. You don't need to understand the derivation and use of the so-called z-transform in order to do practical things with polynomials in z and z^-1.

Here's the polynomial form of the filter shown in Figure 1. To make the equation more compact, I've trimmed the number of significant digits in the coefficients. It's shown in both the negative power [1] and positive power [2] forms.

This might not seem like a big deal – isn't it just another way of expressing what we already know about that filter? Well, it permits us to use some powerful fundamental tools of algebra to analyze, and eventually to synthesize polynomials with useful properties. The key thing is that we can always factorize any such polynomial, rendering it as a product of individual terms that each have either linear or quadratic form. Does this yet bring back memories of those algebra classes at school?

To factorize such a polynomial, we need to find its roots. These are the values of the variable that cause the value of the polynomial to vanish. Most math manipulation tools will have functions that give you the roots of a polynomial. The roots will either be real (giving a linear term) or in complex pairs, which each multiply up into a quadratic term. The overall polynomial is equal to the product of all these quadratic and linear terms.

Let's take our example filter, find the roots and therefore the individual factors. I used an Excel root finder that seemed to work well.

Table 1: All the roots of the polynomial in equation [2].

There are fourteen roots – which is good, because it was a fourteenth order polynomial (the fifteenth tap is the constant term, i.e. it multiplies the zeroth power of z) – of which four are purely real and the rest come in complex conjugate pairs. Remember that classic formula for the solutions of a quadratic equation? When the expression inside the square root is negative, that's where the imaginary part of the root comes from, and the plus-or-minus sign tells you there are two of them, with opposite signs of the imaginary part.

Now we can write down the factors by multiplying up all the terms of the form (z - root). We bundle up those complex pairs into quadratic factors, which will have nice real coefficients, as we can show by multiplying out a conjugate pair of roots, x+jy and x-jy:

Doing this on all the root or root pairs (pick the two that have the same real part) in Table 1, we get equation 4:

Just to make sure of my work, I multiplied [4] out again, (well, Excel did), and Figure 2 is the proof that we get back the same filter.

By the way, this response was obtained by using Excel's FFT function directly on the impulse response. Yet another useful way of calculating the frequency response if you don't have a simulator to hand. This filter only has 15 interesting time points in its impulse response, of course; I padded it out to 1024 points with extra zero values, to get an FFT plot with nice close frequency spacing to give a smooth plot.

But you may be getting restive again – what have we learned by doing all this? Well, here's the useful thing. It turns out that the product of these factors represents the behaviour of a filter made up of a series connection of blocks, each one of which implements a small filter with a polynomial given by that factor. So by factorizing the FIR filter's big polynomial, we have developed a set of small filters (each with either two or three tap weights) that could be connected in series to give the same filter behaviour as the original filter.

Now, IIR filters are almost always designed as series connection of second-order (i.e. quadratic) pieces. But it's rare that people bother to look at the equivalent factorized decomposition of an FIR filter. That's because it generally doesn't confer any sort of advantage since FIR filters are already so simple to implement. But it's a great tool to analyze the coefficient sets that you get from your chosen FIR design software.

My main goal is not to get you breaking down someone else's FIR filter design using these tools. What's really interesting is to look at the behavior that the factors themselves exhibit. We can then separately manipulate each factor to potentially make it do something we want. If we create some factors from scratch, each of which does something useful and interesting, and then multiply them all up to get a polynomial, then this polynomial's coefficients are those of an FIR filter that does all those interesting things at once.

Figure 2: Response of the polynomial you get by multiplying equation [4] back up.

Just to tempt you, have a think about this. Our FIR filter has three nulls in the stopband (Figures 1 and 2). And our factorization of the polynomial [4] shows that it has three factors that have a constant term (the coefficient of z^0) of unity. This is not a coincidence <g>. So next time, we'll work out how to drive this process, creating factors that contribute the particular stopband behaviour we want. This'll show you that there's more than one root (ouch) to good filter design! best / Kendall

To view the Filter Wizard's archive of spells click here

P.S. Check out my Cypress blog at www.cypress.com/go/thefilterwizard - you can also email me from there.

About the author:
Kendall Castor-Perry is a Principal Architect at Cypress Semiconductor,doing mixed-signal system analysis and design for the new PSoC platform. Kendall uses decades of experience in analog engineering, filtering and signal processing to capture signals across many domains, extract the information from them and do something useful with it.

For more articles like this and others related to audio design, visit Audio Designline and/or subscribe to the monthly Audio newsletter (free registration).

This article originally appeared on EE Times Europe.

BicycleBill

2/15/2012 3:20 PM EST

What high school in the US gets to this level of algebra?--you're lucky if they even go to second-order exponents or polynominals. Many stop at the y = x + N level.

But besides that minor complaint, a very good article.

Sign in to Reply

Frank Eory

2/15/2012 5:30 PM EST

Other than academic curiosity, I fail to see the advantage of factoring the polynomial of the full FIR filter just to see a bunch of neat little sub-filters.

BTW Bill, it is quite common for U.S. high school students to get through a first year of calculus in high school, not to mention factoring polynomials, manipulating complex numbers and lots of other fun stuff :)

Sign in to Reply

kendallcp

2/20/2012 1:21 PM EST

Hi Frank - wait for part 2, hope the point will be much clearer then!

Sign in to Reply

Chipmuenk

2/23/2012 6:36 AM EST

Hi Kendall,

well written & fun-to-read article as always from the filter guru! So, maybe I'm just a hair-splitter, but shouldn't it read *four* nulls and *four* first order terms in the last section?

Cheers,

Christian

Sign in to Reply

kendallcp

2/23/2012 4:23 PM EST

If we didn't split hairs, how would we know what's inside them (-8b

But in this instance I stand by my assertion. Check equation [4]: it has three quadratic factors that have unity z^0, and three nulls in the stopband. I'm not counting the almost-null at Nyquist, on the grounds that 1.052235 doesn't equal unity...

Sign in to Reply

Chipmuenk

2/24/2012 8:37 AM EST

Oops - my only excuse is a bad cold slowing down my brain. I mixed up nulls on the real axis with conjugate complex nulls on the unit circle ...

Sign in to Reply

#### Please sign in to post comment

Navigate to related information

## Most Popular

 1 Slideshow: Google I/O puts 7 platforms on parade 2 ST's strategy is a tale of two segments 3 Slideshow: How knockoff nation mastered ecosystem 4 FDSOI gains three design wins 5 Teardown: Samsung Galaxy S4 6 Exclusive: TSMC plots system super chips 7 Arduino board plugs DIYers into the cloud for \$69 8 Invisible embedded: 4-, 8-, 16-bit MCUs still sell 9 Bit-banging pulse density modulation 10 Slideshow: Astronaut sings Bowie in space