Window-method FIR design

Start from the perfect low-pass and keep only its middle taps. Below, the cut keeps 21, then 41, then 81 taps. Watch the bracket at the edge shrink, and the dotted level at the top stay where it is.

Cut the ideal, and the edge ripples

In Filter specifications (18.1) we wrote down how close to ideal a low-pass has to be. Now I want to build one. The plan is the simplest I know: start from the perfect filter and keep the part of it that matters.

On the page Frequency response of discrete-time systems (12.4), the ideal low-pass with cutoff $\Omega_c$ had this impulse response. I call it the desired response, $h_\text{des}[n]$:

It never ends in either direction, which is why it cannot be built. But its values shrink as $n$ moves away from 0, so the part near the peak carries most of it.

So let’s keep only that part. Shift $h_\text{des}$ to the right by $\alpha$ samples, so that the kept part starts at $n=0$, and keep $N_h=2\alpha+1$ taps:

The taps are symmetric about $\alpha$. By Linear-phase systems (17.3), the filter is then linear phase with a delay of $\alpha$ samples, and its gain is the real zero-phase response $H_\text{zp}(\Omega)$.

The picture at the top of the page uses 12.4’s own example, $\Omega_c=0.25\pi$, whose centre tap is $h_\text{des}[0]=0.25\pi/\pi=0.25$. It cuts it to 21, 41 and then 81 taps. To compare the cuts I measure an edge width. It is the distance in $\Omega$ from the last point before the cutoff where the gain is 0.9 to the first point after it where it is 0.1.

Watch what moves and what stays. The edge width roughly halves each time the taps double: it is about $1.8\pi/N_h$. The highest value hardly moves. It stays near 1.09, an overshoot of about 9 % of the jump from 1 to 0, which is the bump of Convergence and the Gibbs phenomenon (7.3).

After the clip, set the number of taps yourself with the slider. At 61 taps the highest value is 1.084 and the edge width 0.029π. Try 101: the edge narrows to 0.017π, and the highest value is still 1.086. Then try 11. The edge is now so wide, 0.179π, that the highest value, 1.078, is at $\Omega=0$ and not next to the edge.

Why does the ripple stay? Keeping $N_h$ taps multiplies $h_\text{des}[n-\alpha]$ by a rectangular window: 1 on the kept taps and 0 everywhere else. By Properties of the DTFT (12.3), multiplying in time convolves the spectra. So the gain is the ideal box smeared by the rectangular window’s spectrum.

As $N_h$ grows, that spectrum’s main lobe narrows, so the edge gets steeper. Its side lobes narrow too, but they keep their height relative to the main lobe. They are what makes the ripple, so the ripple keeps its height as well.

A smoother window has smaller side lobes (Window functions compared, 15.2). So let’s multiply by one of those instead. Windows for filters are the symmetric kind: $w[n]$ for $n=0$ to $N_h-1$ is symmetric about $\alpha$. In SciPy that is get_window(name, N_h, fftbins=False), and NumPy’s np.hanning is symmetric already.

15.2 used periodic windows, which are made for spectra. A symmetric window keeps the product symmetric, so the filter stays linear phase. That gives the window design:

A window trades a wider edge for less ripple

The instrument below keeps the 41 taps and changes only the window: rectangular, which is the plain cut, then Hann, Hamming and Blackman. It is like sanding a sawn edge. The splinters go, and the edge gets rounder.

I write $\delta$ for a design’s ripple: the largest distance of its gain from 1 in the pass band, or from 0 in the stop band. For a window design the ripples in the two bands come out nearly equal, so one $\delta$ describes both. The instrument gives the stop band’s ripple in dB, $20\log_{10}\delta$.

Its transition is measured with that $\delta$. It runs from the last $\Omega$ below the cutoff where the gain is within $\delta$ of 1 to the first $\Omega$ above it where the gain is within $\delta$ of 0. It is not the edge width of the first instrument, which used the fixed levels 0.9 and 0.1.

After the clip, press each window’s button to compare them yourself. Notice that Blackman’s stop band is 54 dB below the plain cut’s, while its transition is six times as wide.

A window’s side lobe is not the filter’s ripple

Hann’s highest side lobe is −31.5 dB (15.2), yet the Hann filter reaches −44 dB. Why the difference? The convolution adds up the window’s spectrum $W$ over a stretch as wide as the box. As $\Omega$ crosses the edge, that stretch slides off $W$, so the gain there is a running area under $W$.

A running area is set by how much area the side lobes hold, not by how tall the tallest one is. Side lobes that alternate in sign and shrink quickly add up to very little. So each window reaches more as a filter than its side lobe suggests.

The transition shrinks like $1/(N_h-1)$, so I give it as a multiple of $\pi/(N_h-1)$. The table puts the textbook values (Oppenheim and Schafer, table 7.2) beside my own measurements at 201 taps, with each window’s highest side lobe from 15.2.

Now let’s size a Hann design for the running spec of 18.1. It needs 40 dB, and Hann reaches 44. The transition is $\Delta\Omega=0.125\pi$, so $6.2\pi/(N_h-1)\le0.125\pi$, which gives $N_h-1\ge49.6$ and $N_h\ge51$. The shortest Hann design that really passes has 50 taps: the table is a guide, not a guarantee.

From the spec to the taps

The table makes you pick from four windows with fixed ripples. The Kaiser window of 15.2 has a knob, $\beta$, and Kaiser found two formulas that turn a spec straight into $\beta$ and a length (Oppenheim and Schafer, §7.6). A window design has one ripple $\delta$ in both bands, so take the smaller of $\delta_\text{pass}$ and $\delta_\text{stop}$, and $A_\text{stop}=-20\log_{10}\delta$.

For $A_\text{stop}$ from 21 to 50 dB, which covers the running spec, the first formula is

Above 50 dB it is $\beta=0.1102\,(A_\text{stop}-8.7)$. Below 21 dB it is $\beta=0$, the rectangular window, which reaches 21 dB by itself. The second formula gives the length:

These are not 15.2’s side-lobe rule. There $\beta$ was chosen for a window’s side lobe; here it is chosen for a filter’s ripple. Place the cutoff in the middle of the transition, $\Omega_c=(\Omega_\text{pass}+\Omega_\text{stop})/2$. In SciPy, kaiserord gives both numbers and firwin gives the taps.

One difference from the first two instruments: firwin scales the taps so that the gain at $\Omega=0$ is exactly 1. The plain product $w[n]\,h_\text{des}[n-\alpha]$ does not. Think of the formulas as a recipe’s baking time. It is a good start, but you still check the cake. Below, the formulas size a design for the running spec, and the zones check it.

The formula was 0.2 dB short, and one more tap fixed it. Notice that 38 is even, so the centre $\alpha=18.5$ falls between two taps. By 17.3 an even-length symmetric filter has a zero forced at $z=-1$, but a low-pass does not mind a zero at $\Omega=\pi$.

After the clip, drag the stop edge yourself, or use the arrow keys; the pass edge stays at 1000 Hz. The widget takes Kaiser’s length and adds one tap at a time until the design passes. $\beta$ stays 3.40, because $A_\text{stop}$ stays 40 dB. At 1250 Hz Kaiser’s estimate is 73 taps, and 74 pass. At 2000 Hz, 19 taps pass, as estimated.

Halve the transition and the length doubles: 37 taps at 500 Hz, 73 at 250 Hz. The estimate is right or one tap short across the whole range.

One low-pass, four filters

The other three shapes can be built from low-passes. Start with a high-pass. Subtract the low-pass from a pure delay:

The delay $\delta[n-\alpha]$ passes every frequency with gain 1 and the same delay $\alpha$, so the high-pass’s zero-phase response is $1-H_\text{zp}(\Omega)$. Where the low-pass passes, the high-pass stops, and the other way round.

This needs an odd $N_h$, so that $\alpha$ is a whole number of samples. There is a second reason. An even-length symmetric filter has a zero forced at $z=-1$ (17.3), so it cannot pass $\Omega=\pi$, and SciPy’s firwin refuses an even-length high-pass.

Subtracting from 1 turns the low-pass’s pass-band ripple into the high-pass’s stop-band ripple. So design the low-pass to the stricter $\delta$. A different route also works: by 12.3, multiplying by $(-1)^n$ slides the response by $\pi$, so $(-1)^nh[n]$ is a high-pass with cutoff $\pi-\Omega_c$.

A band-pass from $\Omega_1$ to $\Omega_2$ is a low-pass with cutoff $\Omega_2$ minus a low-pass with cutoff $\Omega_1$, both with the same $N_h$ and window: $h_\text{bp}=h_{\text{lp},\Omega_2}-h_{\text{lp},\Omega_1}$. A band-stop is $\delta[n-\alpha]$ minus a band-pass. The figure builds all four from one 39-tap Kaiser design.

Worked example

Let’s redo the page’s numbers by hand where we can, and with SciPy where we can’t.

1. The ideal, cut. With $\Omega_c=0.25\pi$ and 41 taps, $\alpha=20$ and the centre tap is $h[20]=0.25$. Every fourth tap from the centre is 0, because $\sin(0.25\pi\cdot4k)=\sin(k\pi)=0$. The gain peaks at 1.099, dips to −0.082 and has an edge width of 0.045π.

That dip, 0.0825 below zero, is the rectangular window’s ripple in the second instrument: $20\log_{10}0.0825=-21.7$ dB.

2. Kaiser for the running spec. The stop band’s 0.01 is stricter than the pass band’s 0.05, so $A_\text{stop}=40$ dB. Then $\beta=0.5842\cdot19^{0.4}+0.07886\cdot19=1.8970+1.4983=3.3953$. The transition is $\Delta\Omega=2\pi\cdot500/8000=0.125\pi=0.3927$ rad/sample.

The length formula gives $N_h-1\ge(40-7.95)/(2.285\cdot0.3927)=35.72$, so $N_h-1=36$ and $N_h=37$. The cutoff goes in the middle of the transition, $(1000+1500)/2=1250$ Hz. There 37 taps fail by a little, −39.80 dB at 1500 Hz. 38 taps pass, at −41.68 dB.

The 38 taps have their centre between $h[18]$ and $h[19]$, which both equal 0.3009. The ideal there, half a sample from its centre, is $\sin(0.3125\pi\cdot0.5)/(0.5\pi)=0.3001$, so the window and the scaling barely touch the middle. The end taps are −0.0016.

3. Other windows on the running spec. I tried firwin with each window and growing $N_h$ until the design passed. The table gives the shortest length that passes, and the shortest odd one. Kaiser’s tuned $\beta$ saves 12 taps over Hann.

4. A high-pass from the 39-tap low-pass. The low-pass’s centre tap is 0.3139, so the high-pass’s centre tap is $1-0.3139=0.6861$. All the other taps just change sign. The low-pass has pass-band deviation 0.0136 and stop band −40.57 dB. The high-pass swaps them: pass-band deviation 0.0094, and stop band $20\log_{10}0.0136=-37.30$ dB.

The band-pass’s centre tap is $0.6869-0.3139=0.3730$, and the band-stop’s is $1-0.3730=0.6270$. Every cutoff gain is 0.50 to two decimals.

5. The window table at 201 taps. I used firwin(201, 0.25, window=name) and the rules of the second instrument: the ripple beyond the first null after the cutoff, and the transition between the points within that ripple of 1 and of 0. That gave stop bands of −21.2, −43.9, −53.7 and −75.3 dB, and transitions of $1.88\pi$, $6.25\pi$, $6.69\pi$ and $11.17\pi$ over 200.

Where you’ll meet this

The window method is the default FIR design in SciPy (firwin) and MATLAB (fir1). It makes anti-alias and decimation filters (Downsampling and decimation, 22.1), audio crossovers and biomedical filters. Reach for it wherever a quick, reliable linear-phase design is enough.

When every tap counts, Optimal FIR design (19.3) meets the same spec with fewer. Frequency-sampling design (19.2) designs from samples of the gain instead. Whether an FIR is the right choice at all is Choosing FIR or IIR (20.6), and long FIRs run fast with Fast convolution (14.3).

Reference card