Filter banks

Here one tone, $\cos(0.30\pi n)$, is split into a low band and a high band, each band keeps every 2nd sample, and the two are rebuilt and added. Watch the lines at 0.70π: each band has an alias there, but in the sum they cancel.

Two bands, two aliases that cancel

An audio coder spends few bits on the bands you hardly hear and more on the ones you do. To do that, it first splits the sound into bands. This page is about splitting a signal into bands and putting it back together, without losing anything.

A bank of filters that splits a signal is an analysis bank. Here it has two filters: a low-pass $H_0(z)$ and a high-pass $H_1(z)$. Each band now holds about half the frequencies, so by Downsampling and decimation (22.1) it can keep every 2nd sample. I write that step as ↓2.

The two bands together then have as many samples per second as the input had. A bank that keeps the total rate the same is critically sampled. Nothing is wasted, and that matters when every sample costs bits.

The synthesis bank goes back. Each band is upsampled with a zero after every sample, as in Upsampling and interpolation (22.2); I write that as ↑2. Then each band goes through its own filter, $F_0(z)$ or $F_1(z)$, and the two are added.

There is a catch. A band is not cut off cleanly at $\pi/2$, so by 22.1 keeping every 2nd sample aliases. Let’s see exactly what ↓2 followed by ↑2 does. It keeps the even samples and puts zeros at the odd ones, so it multiplies the signal by

which is 1 for even $n$ and 0 for odd $n$.

Properties and the inverse z-transform (16.2) showed that multiplying by $a^n$ turns $X(z)$ into $X(z/a)$. With $a=-1$, $(-1)^nx[n]$ has the transform $X(-z)$. So the pair ↓2, ↑2 turns $V(z)$ into

On the unit circle, $-z=e^{j(\Omega+\pi)}$, so $V(-z)$ is the spectrum slid by $\pi$. That is the frequency shift of the section “Slide the spectrum round the circle” in Properties of the DTFT (12.3).

Try it on one tone. Since $(-1)^n\cos(0.3\pi n)=\cos(0.7\pi n)$, the pair turns $\cos(0.3\pi n)$ into $\tfrac12\cos(0.3\pi n)+\tfrac12\cos(0.7\pi n)$. Half the tone stays, and half of it appears at $0.7\pi$, where there was nothing. That new line is the alias.

Now follow both bands through the bank. The low band is $H_0(z)X(z)$ before ↓2, and after ↑2 and $F_0$ it is $\tfrac12F_0(z)\big[H_0(z)X(z)+H_0(-z)X(-z)\big]$. The high band is the same with 1 in place of 0. Add the two and sort the terms:

with

$T_\text{dist}$ is the distortion transfer function. It acts on the signal itself, like the $H(z)$ of Transfer functions, poles & zeros (16.3). $T_\text{alias}$ is the alias transfer function, and it acts on the slid copy $X(-z)$.

So each band has an alias term of its own. But we choose $F_0$ and $F_1$, so we can make the two bands’ aliases cancel: $T_\text{alias}(z)=0$. That is aliasing cancellation.

If, as well, $T_\text{dist}(z)=z^{-n_0}$, the output is the input delayed by $n_0$ samples. That is perfect reconstruction.

The pair I’ll use is the Daubechies pair of 4 taps, called db2. Its low-pass taps are

The high-pass reverses them and flips every other sign, $h_1[n]=(-1)^nh_0[3-n]$, which gives −0.12941, −0.22414, 0.83652 and −0.48296. The synthesis filters are the two reversed: $f_0[n]=h_0[3-n]$ and $f_1[n]=h_1[3-n]$.

The taps of $h_0$ add up to $\sqrt2$, so its gain at $\Omega=0$ is $\sqrt2$, not 1. The picture at the top of the page divides both gains by $\sqrt2$, so that each pass band reads 1.

That picture sends one tone, $\cos(0.30\pi n)$, through this bank. It shows each band rebuilt on its own, and then their sum.

Notice that the alias is not small in either band: 0.313 of a tone of size 1. It is only the sum that is 0.

It is like two clerks who copy the same column of figures. One writes a figure 5 too high and the other writes it 5 too low. Each copy is wrong, but their sum is right.

After the clip, use the slider to scale the high band by a gain $g$ from 0 to 1, as an equaliser would.

The tone in the sum is the low band’s 0.890 plus $g$ times the high band’s 0.110. The alias is $(1-g)\times0.3128$, because only the fraction $g$ of the high band’s alias is there to cancel the low band’s. Try 0: the alias is back to 0.313, and the tone is 0.890.

So the cancellation is a balance. Process one band, and part of the alias comes back. An audio coder that stores one band more coarsely than the other pays this price too.

Why the aliases cancel

Reversing the taps of a filter turns $H(z)$ into $H(z^{-1})$: put $m=-n$ in $\sum_nh[-n]z^{-n}$ and it becomes $\sum_mh[m]z^{m}$. The reversed 4 taps then need a delay of 3 to start at $n=0$ again, a factor $z^{-3}$. So $F_0(z)=z^{-3}H_0(z^{-1})$ and $F_1(z)=z^{-3}H_1(z^{-1})$. Put $m=3-n$ in the transform of $h_1[n]=(-1)^nh_0[3-n]$ and you get

Put that into the two terms of $T_\text{alias}$:

They are equal and opposite for every $z$, so $T_\text{alias}(z)=0$. That holds for every tone, not only 0.30π.

On the unit circle, $F_k(e^{j\Omega})$ is $e^{-j3\Omega}$ times the conjugate of $H_k(e^{j\Omega})$, because the taps are real (12.3, “The rules that carry over”). So $T_\text{dist}$ there is $\tfrac12e^{-j3\Omega}\big(\lvert H_0\rvert^2+\lvert H_1\rvert^2\big)$. Daubechies chose $h_0$ so that $\lvert H_0\rvert^2+\lvert H_1\rvert^2=2$ at every $\Omega$, and then $T_\text{dist}(z)=z^{-3}$.

That is why the tones in the instrument, 0.890 and 0.110, add to 1.

The simplest such pair is the Haar pair, $h_0=(1,1)/\sqrt2$ and $h_1=(1,-1)/\sqrt2$. It has 2 taps, so its delay is 1 sample. Its split is gentle: at 0.30π its low and high gains are 0.89 and 0.45. So each band’s alias is bigger, 0.405 at this tone, and the two still cancel.

The name QMF, quadrature mirror filter, comes from an older and simpler choice: $H_1(z)=H_0(-z)$, so the high-pass is the low-pass slid by $\pi$. With $F_0=H_0$ and $F_1=-H_1$, the alias term is $\tfrac12[H_0(z)H_0(-z)-H_0(-z)H_0(z)]=0$. The aliases cancel here too.

But perfect reconstruction fails. Split $H_0$ into its two polyphase components, as in Polyphase structures (22.4): $H_0(z)=E_0(z^2)+z^{-1}E_1(z^2)$. Then

For an FIR filter that is one delay only if $E_0$ and $E_1$ each have a single tap. So the classic QMF reconstructs perfectly only when $H_0$ has 2 taps, as Haar’s does. Longer QMF designs, such as Johnston’s, get close and accept a small ripple in $T_\text{dist}$.

There is a cost to db2 as well. Its taps are not symmetric, so by the section “Why symmetric taps give a straight phase” of Linear-phase systems (17.3), its phase is not a straight line. Among pairs built the db2 way, only Haar has symmetric taps. Banks that need a straight phase use different filters for analysis and synthesis, called biorthogonal pairs.

One prototype, eight channels, a perfect sum

Two bands are often not enough. A uniform bank splits the band from 0 to $2\pi$ into $M$ equal channels. The easy way to make it uses one low-pass, the prototype $p[n]$, and shifts it to each centre.

By 12.3, multiplying by $e^{j\Omega_1n}$ slides a spectrum by $\Omega_1$. So channel $k$ has the taps $p[n]\,e^{j2\pi kn/M}$, centred at $2\pi k/M$. This is a DFT filter bank: the arrows $e^{j2\pi kn/M}$ are the ones in the DFT.

My prototype is a Hann window of 16 samples, the periodic one of Inverting the STFT (15.6). It is scaled so its taps add to 1, so its gain at $\Omega=0$ is 1: $p[n]=w[n]/8$. With $M=8$, the channels sit $2\pi/8=0.25\pi$ apart.

These eight channels are the STFT of Spectrograms & the STFT (15.5) in disguise. Channel $k$‘s output at sample $n$ weights the 16 samples ending at $n$ by the window and by an arrow turning at $2\pi k/8$, and adds them. That is one cell of the STFT of the section “A row of short spectra”, at frequency $2\pi k/8$. Its window is $p$ back to front, its frame ends at $n$, and only an arrow of size 1 in front differs.

Watch the thick line at the end: added as complex numbers, the eight channels are exactly a delay of 8 samples, so nothing is lost.

Notice that the channels overlap: the magnitudes of the eight gains add to between 1.0000 and 1.0620, not to 1. Added as complex numbers, with their phases, they give exactly 1 at every $\Omega$.

It is like eight spotlights on a stage. Their beams overlap, but added together they light the stage evenly.

Why exactly a delay? Add the taps of the eight channels:

When 8 divides $n$, every arrow is 1 and the sum is $8p[n]$. Otherwise the eight arrows are equal steps round the circle, and they add to 0, as the roots of unity did in Complex numbers for signals (3.3).

So the sum keeps only $p[0]$ and $p[8]$, times 8. The Hann window is 0 at $n=0$ and 1 at $n=8$, and $8p[8]=1$. The eight channels add up to $\delta[n-8]$, a delay of 8 samples.

This is the arithmetic of the section “Windows that add up to a constant” in 15.6, with time and frequency swapped. There, copies of a window shifted in time added up to a constant. Here, copies of its spectrum shifted in frequency add up to a pure delay.

In the instrument every channel runs at the full rate, so there are 8 times as many samples as in the input. A practical bank keeps only every 8th output of each channel, which makes it critically sampled. Then it does not run 8 filters: it runs the 8 polyphase components of $p$ at the low rate and one 8-point FFT (22.4).

The MDCT

Audio codecs use a critically sampled bank called the MDCT, the modified discrete cosine transform. Each block makes $N$ new coefficients from $N$ new samples, so nothing is added to the rate. But each block’s window is $2N$ samples long, so neighbouring windows overlap by 50 %. It uses cosines in place of the DFT’s complex arrows.

Taken alone, one block cannot give back its $2N$ samples from $N$ coefficients: what it returns is aliased in time. Where two neighbouring blocks overlap, their aliases are equal and opposite, and overlap-add, as in 15.6, cancels them. This is time-domain aliasing cancellation, the twin of the first instrument with time in place of frequency.

AAC uses blocks of 1024 coefficients, with windows of 2048 samples. MP3 first splits the sound into 32 bands with a polyphase bank, then takes an MDCT with 18 coefficients in each band: 576 lines. Opus and Vorbis use the MDCT too.

Worked example

Let’s redo the page’s numbers by hand, from the filter gains.

1. The db2 bank at 0.30π. In the filter strip’s units the gains are 0.94344 (low) and 0.33156 (high) at 0.30π, and the other way round at 0.70π. The tone goes through $H_k$ and then $F_k$ at 0.30π, so the low band’s tone is $0.94344^2=0.890$ and the high band’s $0.33156^2=0.110$.

The alias goes through $H_k$ at 0.30π and $F_k$ at 0.70π. So both bands’ aliases are $0.94344\times0.33156=0.313$, with opposite signs. The tones add to 1.000, the aliases to 0, and the output is the input 3 samples late.

2. Processing breaks the cancellation. Scale the high band by $g=0.5$. The alias left is $(1-0.5)\times0.3128=0.156$, and the tone is $0.890+0.5\times0.110=0.945$.

3. The Haar pair at 0.30π. Here $\lvert H_0\rvert/\sqrt2=\cos(0.15\pi)=0.891$ and $\lvert H_1\rvert/\sqrt2=\sin(0.15\pi)=0.454$. Each band’s alias is $\cos(0.15\pi)\cos(0.35\pi)=0.405$, and the tones are 0.794 and 0.206, adding to 1.

4. The DFT bank. The sum of the eight channels’ taps is $8p[n]$ at $n=0$ and $n=8$, and 0 elsewhere. With $p[0]=0$ and $p[8]=1/8$ that is $\delta[n-8]$. The magnitudes of the gains add to between 1.0000 and 1.0620.

5. In code. pywt.Wavelet('db2') in PyWavelets holds the four filters. Its rec_lo is $h_0$ as written here and rec_hi is $h_1$; dec_lo and dec_hi are the same taps reversed. scipy.signal.upfirdn(h, x, 1, 2) filters and keeps every 2nd sample in one call.

Where you’ll meet this

Filter banks are inside audio coders (MP3, AAC, Opus), equalisers with many bands, and hearing aids, which adjust the gain band by band. Some echo cancellers work band by band too, at a low rate in each. Software radios use DFT banks to pull many channels out of one wide band at once; they call them channelisers.

Split the low band again, and again, and you get the wavelet transform of Wavelets (23.2), built on the db2 pair of this page. How a codec decides how many bits each band gets is Perceptual audio coding (29.3).

Reference card