FIR Filters

The ideal impulse response, truncation and the window method, Kaiser's formula, linear phase, and equiripple design by Parks–McClellan

Rice University, 1971 — a class project

In August 1970 James McClellan starts graduate school at Rice University in Houston and enrols in a new course, Digital Filters, taught by Thomas Parks and Sidney Burrus. The next spring, during the break, Parks drives from Houston to Princeton for a conference and hears Ed Hofstetter describe a new way of designing FIR filters. He brings the paper home, thinking about Chebyshev approximation theory and the Remez exchange algorithm, and implementing the idea becomes McClellan's project for Parks's Signal Theory course (Parks–McClellan filter design algorithm). It takes them about six weeks. By the end of May 1971 they have designed their first optimal filters, and the algorithm, published in 1972, becomes a standard method for designing FIR filters (Parks–McClellan filter design algorithm). This lesson builds up to it: from the ideal filter that cannot be built, through windows, to the best filter a given length allows.

A finite impulse response filter is a list of coefficients,

y[n] = \sum_{k=0}^{N-1} h[k]\,x[n-k]

: no feedback, no poles away from the origin, always stable. Designing one means choosing

N

numbers so that

H(e^{j\Omega}) = \sum h[k]e^{-j\Omega k}

meets a specification — a passband ripple, a stopband attenuation and a transition band between them.

Derivation

The ideal filter, truncated

The ideal low-pass,

H = 1

for

|\Omega| < \Omega_c

and 0 elsewhere in

(-\pi, \pi]

, has the impulse response

h_d[n] = \frac{1}{2\pi}\int_{-\Omega_c}^{\Omega_c} e^{j\Omega n}\,d\Omega = \frac{\sin(\Omega_c n)}{\pi n},

a sampled sinc: infinitely long and non-causal, as in Lesson 4-4. Keep the

2M + 1

central samples and delay them by

M

, and you have a causal FIR filter. But truncation multiplies

h_d

by a rectangle, so its spectrum is convolved with the rectangle's transform: ripples appear beside both band edges, and the largest stays near 9 % of the jump — about −21 dB in the stopband — however long the filter. That is Gibbs's phenomenon of Lesson 3-2 again. Multiply by a tapered window instead, and the ripples shrink while the transition widens.

💡The window method

Each window buys a roughly fixed stopband attenuation; the length then sets the transition width, which shrinks as

1/N

. Approximately: | Window | Stopband attenuation | |---|---| | Rectangular | 21 dB | | Hann | 44 dB | | Hamming | 53 dB | | Blackman | 74 dB | For a specification of 0.1 dB passband ripple and 60 dB rejection from 1.5 kHz (fs = 8 kHz, passband to 1 kHz), Hamming windows fail at any length tried — 44 dB at 51 taps, 57.7 dB at 101 — while a 101-tap Blackman design reaches 75.3 dB.

💡Kaiser's formula

James Kaiser's window has a parameter

\beta

that trades main-lobe width for side-lobe level continuously, and Kaiser gave formulas that go straight from a specification to a design. For attenuation

A

dB above 50,

\beta = 0.1102(A - 8.7)

, and the length is about

N \approx \frac{A - 7.95}{2.285\,\Delta\Omega} + 1,

where

\Delta\Omega

is the transition width in radians per sample. For 60 dB and a 500 Hz transition at 8 kHz,

\Delta\Omega = 2\pi \times 500/8000

, giving

N \approx 59

; SciPy's kaiserord says 60, with

\beta = 5.653

, and a 61-tap design reaches 60.5 dB.

💡Linear phase

Make the coefficients symmetric,

h[n] = h[N - 1 - n]

, and the terms pair up so that

H(e^{j\Omega}) = e^{-j\Omega(N-1)/2}\,A(\Omega)

with

A(\Omega)

real: the phase is exactly linear, and every frequency is delayed by the same

(N - 1)/2

samples. That is the distortionless transmission of Lesson 4-4, which no causal analog filter achieves — the great advantage of FIR filters.

Equiripple design. A window design spends its error unevenly: the ripples are largest next to the band edges and much smaller elsewhere. The minimax design instead makes the largest weighted error as small as possible; Chebyshev's theory says the optimum spreads the error evenly, rippling between equal peaks — equiripple. The Parks–McClellan algorithm finds that optimum with Remez's exchange method. For the specification above, scipy.signal.remez meets it with 47 taps, against 61 for the Kaiser window, with 0.085 dB of passband ripple and 61.3 dB of stopband attenuation.

It seems that perfection is attained not when there is nothing more to add, but when there is nothing more to remove.

– Antoine de Saint-Exupéry, Terre des hommes (1939), quoted on Wikiquote

🕰Chebyshev's legacy

The theory behind equiripple design is Pafnuty Chebyshev's minimax approximation; the exchange algorithm at its core was published by Evgeny Remez in 1934 (Remez algorithm). Analog designers already knew the pattern: in the 1960s it was well known that the best filters ripple equally, and that the elliptic filter was optimal in Chebyshev's sense (Parks–McClellan filter design algorithm).

⚠Long filters, long delays

A linear-phase FIR filter delays everything by

(N - 1)/2

samples: 30 samples, 3.75 ms, for the 61-tap design at 8 kHz. Halve the transition band and both the length and the delay roughly double. For audio monitoring, control loops and anything interactive, that delay can matter as much as the ripple.

💡Where you will use this

FIR filters do the anti-aliasing inside decimators and resamplers (Lesson 5-3), shape pulses in digital communications, and equalise channels. Their linear phase makes them the choice whenever waveform shape matters; when it does not, the IIR filters of Lesson 9-2 do the job with far fewer coefficients.

📚Further reading

Thomas W. Parks and James H. McClellan, "Chebyshev Approximation for Nonrecursive Digital Filters with Linear Phase", IEEE Transactions on Circuit Theory 19 (1972), 189–194.
Alan V. Oppenheim and Ronald W. Schafer, Discrete-Time Signal Processing (3rd ed., Pearson, 2010), chapter 7.
Parks–McClellan filter design algorithm on Wikipedia.

↓But there is a problem

Forty-seven taps for a modest specification; hundreds for a sharp one. Feedback changes the arithmetic: a handful of poles can do the work of hundreds of taps. The sharpest such filters were found in the 1930s by a Berlin mathematician, whose life ended in the last days of the Second World War.