Special FIR filters

Take the slope of a noisy signal and the noise usually wins. Below, one noisy sine goes through two filters that take its slope. Watch the bottom panel: one output is buried in noise, and the other lies close to the true slope.

A slope from samples

Suppose you log a car’s speed once per sample and want its acceleration. Acceleration is the rate of change of speed, its slope. The speedometer jitters a little, and that is the trouble. The jitter changes faster than the speed does, so it is the jitter that changes the slope most.

The design methods of Window-method FIR design (19.1) to Optimal FIR design (19.3) made band filters: pass some frequencies, stop others. On this page the same methods make four other filters. Each one starts from a different ideal response, and that ideal response is the only new thing on each part of the page.

On Properties of the Fourier transform (8.2) you saw that differentiation multiplies the spectrum by $j\omega$. The same holds for samples.

Take $x[n]=x_c(nT_s)$ with $T_s=1$, from a wave with nothing at or above half the sample rate. The slope of $x_c$ at the sample times has the spectrum $j\Omega X(e^{j\Omega})$ for $\lvert\Omega\rvert<\pi$. So the ideal differentiator is the filter

where “des” means desired, as in 19.1. Its gain is $\Omega$: a wave twice as fast comes out twice as steep.

The simplest slope you can take from samples is the first difference $y[n]=x[n]-x[n-1]$ of Oversampling and noise shaping (11.3). On Frequency response of discrete-time systems (12.4) its gain came out as $2\lvert\sin(\Omega/2)\rvert$. For slow waves that is close to $\Omega$: at $0.04\pi$ it is 0.12558, against 0.12566. At $\pi$ it is 2 instead of $\pi$.

Both curves rise all the way to $\pi$. That is the problem: the jitter has energy at every frequency, and its fastest parts get the most gain.

A slow signal needs the gain $\Omega$ only as far as the signal goes. Above that I want gain 0. A differentiator that follows $\Omega$ up to a cutoff $\Omega_c$ and is 0 above it is a band-limited differentiator:

Its taps come from the inverse DTFT of The DTFT (12.2), the same step that gave 12.4 the ideal low-pass:

The second line splits $e^{j\Omega m}$ into $\cos(\Omega m)+j\sin(\Omega m)$. The cosine part, $\Omega\cos(\Omega m)$, is odd in $\Omega$ and integrates to 0, and $j\cdot j=-1$ gives the minus sign. The third line is integration by parts. At $m=0$ the integrand $j\Omega$ is odd, so $h_\text{des}[0]=0$.

These taps are antisymmetric, $h_\text{des}[-m]=-h_\text{des}[m]$. The window method of 19.1 does the rest. Keep $N_h=2\alpha+1$ taps and multiply by a window: $h[n]=w[n]\,h_\text{des}[n-\alpha]$. I use the Kaiser window with $\beta=3.40$ that 19.1 chose for 40 dB, and 61 taps, so $\alpha=30$.

An antisymmetric filter of odd length is type III of Linear-phase systems (17.3), so its gain is forced to 0 at $\Omega=0$ and at $\Omega=\pi$. At $\Omega=0$ that is what a differentiator should do, because a constant has slope 0. At $\pi$ it does no harm as long as $\Omega_c$ is below $\pi$, because the ideal is 0 there too.

A differentiator that ignores the noise

The picture at the top of the page sends one noisy sine through the first difference and through a 61-tap band-limited differentiator with $\Omega_c=0.2\pi$, and compares both outputs with the true slope.

It draws the outputs moved back by their delays. Why are they moved back? The first difference is antisymmetric with two taps, so it delays by $\alpha=0.5$ samples (17.3). The 61-tap filter delays by 30.

Look at the input first: the noise is barely visible there. Then look at the first difference: the noise swamps the slope. The sine’s slope is at most 0.126 per sample, and the noise in the output is 0.075 RMS, more than half of that. The 61-tap output lies close to the true slope.

When the clip has finished, drag across the gain panel to set $\Omega_c$ yourself, or use the arrow keys.

Choosing $\Omega_c$ trades noise against signal. At $0.10\pi$ the error falls to 0.0025, because less noise gets through. At $0.05\pi$ it rises to 0.0423, because now the cutoff cuts into the sine itself: the gain at $0.04\pi$ is only 0.066, about half of the 0.126 it should be. Above $0.2\pi$ the error grows again, to 0.0138 at $0.30\pi$ and 0.0319 at $0.50\pi$.

At $\pi$ the error is 0.0954, worse than the first difference. With $\Omega_c=\pi$ the design follows $\Omega$ over the whole band. It follows it more closely than the first difference does, so it gives the noise even more gain. Its taps are $\cos(\pi m)/m$, and this full-band ideal really wants type IV, like the first difference: it needs gain $\pi$ at $\pi$, and type III is forced to 0 there (17.3). An even length, with its centre between two samples, avoids that zero.

Half-band: every other tap is zero

Now a low-pass, with one special cutoff. A half-band low-pass has its cutoff at $\Omega_c=0.5\pi$, half of the band from 0 to $\pi$. The ideal low-pass of 12.4 has the taps $\sin(\Omega_cm)/(\pi m)$ and $h[0]=\Omega_c/\pi$. With $\Omega_c=0.5\pi$ they are

At every even $m$ other than 0, $\sin(\pi m/2)$ is the sine of a whole number of half turns, which is 0. So every other tap is 0, like a checkerboard on which half the squares are empty by design. The window cannot undo that, because it multiplies each tap and 0 times anything is 0. The Kaiser window is 1 at its centre, so the centre tap stays 0.5.

The instrument below draws a 23-tap half-band filter, its taps and its gain, and then turns the gain curve half a turn.

Watch the dashed copy as it turns. It lands on the curve at every point, ripples included. Why? From 17.3, a symmetric filter of odd length has

In a half-band filter only the odd $m$ are left in the sum. For odd $m$, $\cos(m(\pi-\Omega))=-\cos(m\Omega)$, so

Add the two lines and every cosine cancels. Only $2h[\alpha]=1$ is left, which is $H_\text{zp}(\Omega)+H_\text{zp}(\pi-\Omega)=1$. A ripple of 0.0035 above 1 at some $\Omega$ in the pass band is a ripple of 0.0035 above 0 at $\pi-\Omega$ in the stop band.

Half-band filters are used where a signal’s rate is halved or doubled, in Downsampling and decimation (22.1) and Upsampling and interpolation (22.2). Halving the rate throws away half of the outputs, and half of the taps are zero. So a cascade of half-band stages is the cheapest way to lower a rate by a power of 2.

A Hilbert transformer

The third filter, in its ideal form, changes no sizes. It turns every cosine into a sine. A Hilbert transformer has the ideal response

Its gain is 1 everywhere except at 0 and $\pi$. Its phase is $-\pi/2$, a quarter turn back, for positive frequencies. A cosine is two arrows, $\cos(\Omega_0n)=\tfrac12e^{j\Omega_0n}+\tfrac12e^{-j\Omega_0n}$. The filter multiplies the first arrow by $-j$ and the second by $+j$, which gives $\tfrac{1}{2j}\big(e^{j\Omega_0n}-e^{-j\Omega_0n}\big)=\sin(\Omega_0n)$.

Its taps are again an inverse DTFT. Folding the negative frequencies onto the positive ones, as for the differentiator, leaves

For odd $m$, $\cos(\pi m)=-1$ and the taps are $2/(\pi m)$. For even $m$, including $m=0$, they are 0.

The taps are antisymmetric, and with an odd length that is type III again: its gain is forced to 0 at 0 and at $\pi$ (17.3). Its phase is $-\pi/2-\alpha\Omega$. That is 17.3’s generalised linear phase with $\beta=-\pi/2$, because here the real factor $H_\text{zp}$ of 17.3 is negative.

The ideal jumps from $+j$ to $-j$ at $\Omega=0$, and again at $\pi$. No filter with a finite number of taps can jump. So the gain of a real design must fall to 0 near both ends, and type III makes it reach 0 exactly there. The figure shows a 31-tap design, windowed like the others.

The figure is static, because The Hilbert transform and the analytic signal (27.2) gives the Hilbert transformer a page of its own. There it turns a real signal into a complex one whose size is the signal’s envelope.

Delay by a fraction of a sample

The last filter does nothing to a signal but delay it. Delaying by a whole number of samples is easy: $z^{-n_0}$. But what if two microphones are 7.25 samples apart, and you want to line up their signals?

A delay by a number of samples $n_0$ that is not a whole number is a fractional delay. Its output should be the wave read between the samples, $y[n]=x_c\big((n-n_0)T_s\big)$.

On Reconstruction (10.3) you rebuilt $x_c$ from its samples by adding a sinc pulse at every sample. Read that sum at the time $(n-n_0)T_s$, with $T_s=1$:

That is a convolution of $x$ with the taps $h[n]=\mathrm{sinc}(n-n_0)$: samples of a sinc centred at $n_0$. The sinc never ends, so I keep 16 taps and taper them with a Hann window centred at $n_0$ too, $w(t)=0.5+0.5\cos(\pi t/8)$ for $\lvert t\rvert\le8$. The taps are $h[n]=\mathrm{sinc}(t)\,w(t)$ at $t=n-n_0$, for $n=0$ to 15.

Below, $n_0$ moves from 7 to 7.25 and then to 7.5.

Notice the taps at $n_0=7$: every one is 0 but $h[7]$, because a sinc is 0 at every whole number but its centre. Move $n_0$ by a quarter of a sample, and every tap changes.

When the clip has finished, drag the dotted $n_0$ line yourself, from 7 to 8, or use the arrow keys.

Why does it work? The taps are the reconstruction pulses of 10.3, read at times shifted by $n_0$, so $y[n]\approx x_c\big((n-n_0)T_s\big)$. The window keeps the sum short.

It fails near $\pi$. At $n_0=7.5$ the taps are type II, which forces the gain to 0 at $\pi$ (17.3), and at $0.9\pi$ the gain is already 0.70. At $n_0=7.25$ it is 0.863 at $0.9\pi$. Our test wave at $0.2\pi$ is far from that edge.

An all-pass filter from All-pass systems (17.1) also gives a fractional delay. Its gain is 1 at every frequency, but its phase is bent, so the delay is not the same at every frequency.

Worked example

Here are the numbers behind the four filters, so you can check them by hand or in a few lines of code.

1. First difference as a differentiator. Its gain $2\sin(\Omega/2)$ is 0.12558 at $0.04\pi$, against $\Omega=0.12566$, and 2 at $\pi$, against $\pi$. White noise of RMS $x_\text{noise,rms}$ comes out of a filter with RMS $x_\text{noise,rms}\sqrt{\sum h[n]^2}$, its noise gain from Simple smoothing filters (18.2). For the first difference that is $\sqrt{1^2+1^2}=\sqrt2=1.414$. For the 61-tap design with $\Omega_c=0.2\pi$ it is 0.149. Times the measured noise RMS of 0.0530, that predicts 0.0750 and 0.0079 of noise in the outputs, close to the errors 0.0752 and 0.0075. Almost all of each error is noise.

2. Band-limited taps. With $\Omega_c=0.2\pi$ and 61 taps, the formula gives $-0.02529$ at $m=1$ and $-0.04478$ at $m=2$. The window makes them $h[31]=-0.0253$ and $h[32]=-0.0445$, and $h[30]=0$. The taps are exactly antisymmetric.

3. Half-band. Of the 23 taps, 13 are not zero, and the centre is 0.5. The nearest taps are $1/\pi=0.318$ before the window and 0.315 after it. The pass band deviates from 1 by at most 0.0035 up to $0.3\pi$. The stop band from $0.7\pi$ is at most 0.0035, which is −49.0 dB. The two are mirror images.

4. Hilbert, 31 taps. Before the window the taps next to the centre are $2/\pi=0.637$ and $2/(3\pi)=0.212$. After it they are 0.633 and 0.200. The gain is within 0.0143 of 1 from $0.1\pi$ to $0.9\pi$, but only 0.382 at $0.02\pi$ and 0.812 at $0.05\pi$. Multiply $H$ by $e^{j15\Omega}$ to take out the delay: the real part of what is left is 0 to within $10^{-14}$, so the phase is $-\pi/2-15\Omega$ for every $\Omega$ between 0 and $\pi$.

5. Fractional delay. At $n_0=7.25$ the taps from $n=5$ to 9 are 0.082, −0.169, 0.898, 0.294 and −0.114. At $n_0=7.5$ they are 0.099, −0.194, 0.631, 0.631 and −0.194. The largest errors on $\cos(0.2\pi n)$ are 0, 0.00012 and 0.00018 for $n_0=7$, 7.25 and 7.5. The group delay $\tau_g$ (12.4) at $0.1\pi$, $0.25\pi$, $0.5\pi$ and $0.75\pi$ equals $n_0$ to 3 decimals, both for 7.25 and for 7.5.

Where you’ll meet this

Band-limited differentiators find velocity from position and acceleration from velocity in sensors, robotics and vehicle logs, where the signal is slow and the noise is not. Half-band stages do most of the work in decimators and interpolators (22.1, 22.2). Hilbert transformers make the analytic signal (27.2), which radio receivers and envelope detectors use.

Fractional delays align microphone arrays and steer beamformers. They change sample rates by any ratio in Resampling by any factor (22.3), and they tune the strings and tubes of physical models in Audio effects (29.2). Modems use them to read a received signal at the right instant, in Digital modulation and OFDM (27.5).

One more special FIR filter is the minimum-phase one. Flip the zeros of a linear-phase design that lie outside the unit circle, as on Minimum phase (17.2), and the gain stays while the delay shrinks.

Reference card