Polyphase structures

A 12-tap low-pass that decimates by 4 can filter every input and throw three outputs in four away. Or its taps can be sorted into four short branches that each run at the low rate. Watch the two bars of work per kept output: 48 multiplies against 12, for the same outputs.

Split the taps by phase, run each part slowly

In Downsampling and decimation (22.1) a decimator filters every input sample and then keeps one output in $M$. The other $M-1$ outputs are computed and thrown away, so $(M-1)/M$ of its multiplies are wasted. In Upsampling and interpolation (22.2) the interpolator wastes work the other way: most of its multiplies meet the zeros it inserted.

On this page I move the rate change past the filter, so that nothing is computed for nothing. In block diagrams I draw downsampling by $M$ as a box marked ↓M, and upsampling by $L$ as a box marked ↑L.

The noble identity

Take any filter $G(z)=\sum_j g[j]\,z^{-j}$ and replace every $z$ by $z^M$. Then every delay becomes $M$ delays:

Its taps sit only at multiples of $M$, with zeros between. Feed it $x[n]$ and keep every $M$-th output, the one at $Mn$:

Every sample it touches is one that ↓M keeps, so it acts exactly like $G(z)$ on the kept samples. This is the noble identity: $G(z^M)$ followed by ↓M equals ↓M followed by $G(z)$. The filter can move after the rate drop, where it runs $M$ times less often.

A decimation filter $h[n]$ is not of the form $G(z^M)$: its taps sit at every $n$. So I split it into $M$ parts that are. Sort the taps by $n\bmod M$, the remainder when $n$ is divided by $M$. Tap $Mj+k$ goes to part $k$, for $k=0,\dots,M-1$:

Here $E_k(z)=\sum_j h[Mj+k]\,z^{-j}$ is the $k$-th polyphase component: the filter whose taps are $h[k]$, $h[M+k]$, $h[2M+k]$, and so on. “Phase” here means the remainder $k$.

Every branch after the downsampler

Each term $z^{-k}E_k(z^M)$ is a delay of $k$ followed by a filter in $z^M$. Keeping every $M$-th sample of a sum is the sum of the kept samples, so ↓M can go into each branch. By the noble identity it then passes $E_k(z^M)$, which becomes $E_k(z)$.

So branch $k$ delays the input by $k$, keeps every $M$-th sample, $x[Mn-k]$, and filters it with $E_k$ at the low rate. In the time domain, put $m=Mj+k$ in the decimator’s sum:

The inner sum is branch $k$. In hardware the delays and downsamplers at the front are often drawn as one switch, the commutator. It deals the input samples round the $M$ branches, one each, so every branch gets every $M$-th sample. Once each branch has its sample, the branch outputs are added into one output.

Think of four cashiers, each serving every fourth customer. The other way is one cashier doing all the work, with supervisors throwing most of it away. The picture at the top of the page does this with a 12-tap low-pass and $M=4$: four branches of 3 taps.

Notice what its end caption claims: the outputs are the same in both forms. Nothing is approximated. The polyphase form only skips the outputs that the direct form throws away.

The interpolator, the other way round

The interpolator of 22.2 inserts zeros, ↑L, and then filters. There is a second noble identity for it: ↑L followed by $G(z^L)$ equals $G(z)$ followed by ↑L. The taps of $G(z^L)$ are $L$ apart. At the outputs $Ln$ they meet only original samples, and in between only zeros, so the result is $G(z)$‘s output with zeros inserted.

Split $H(z)$ the same way, with $L$ in place of $M$. Then output number $Ln+k$ is made by branch $k$ alone:

For 12 taps and $L=4$, each output comes from one branch of $12/4=3$ taps, so no multiply ever meets an inserted zero. Here the commutator sits at the output: it collects one sample from each branch in turn.

The table “Multiplies per output” counts the work for the jobs of this chapter.

The decimator’s cost per output falls from $MN_h$ to $N_h$, the filter’s length. The interpolator’s falls from $N_h$ to $N_h/L$. The 44.1 to 48 kHz converter of Resampling by any factor (22.3) gains both ways at once: it skips the zeros and the discarded outputs. That leaves one branch, 20 or 21 taps, for each output.

No multiplications: integrators and combs

A decimator at megahertz rates wants something cheaper still, with no multiplier at all. Two pieces built from adders and delays will do it.

The first is the running sum of Operations on amplitude (2.2), $s[n]=s[n-1]+x[n]$. By The z-transform (16.1) a delay is $z^{-1}$, so $S(z)=X(z)/(1-z^{-1})$. I call $1/(1-z^{-1})$ an integrator.

The second is the feed-forward comb of Resonators, notches and combs (17.4), $y[n]=x[n]-x[n-M]$, which is $1-z^{-M}$. I just call it a comb. Put the two in a row:

This is 6.1’s geometric sum, and it is an $M$-point running sum. It is $M$ times the $M$-point moving average of Simple smoothing filters (18.2).

Now the noble identity again. The comb $1-z^{-M}$ is $G(z^M)$ with $G(z)=1-z^{-1}$, so it can move after ↓M and become $1-z^{-1}$ at the low rate. The integrator stays at the high rate.

Use $N$ integrators, then ↓M, then $N$ combs. Here $N$ counts stages, not points: the average has $M$ points. Moved back in front of ↓M, the combs and integrators make the filter

and it has only adders and delays. It is a CIC filter, short for cascaded integrator–comb.

Its gain is a moving average’s gain, to the power $N$. By Frequency response of discrete-time systems (12.4), the $M$-point average has gain $\lvert\sin(M\Omega/2)\rvert/\lvert M\sin(\Omega/2)\rvert$, with zeros at $\Omega=2\pi k/M$. So the CIC, scaled to 1 at 0 Hz, has

On a dB scale the power $N$ becomes a factor $N$: each stage adds the same number of dB.

The instrument takes $M=8$, from 64 kHz to 8 kHz, and keeps 0 to 1 kHz. After ↓8 the rate is 8 kHz, so a component folds onto 0 to 1 kHz if it lies within 1 kHz of 8, 16, 24 or 32 kHz.

The nearest such frequency is 7 kHz, and the gain there is the largest of all those bands. So the gain at 7 kHz is the one number to watch. In $\Omega$, 7 kHz is $2\pi\cdot7/64=0.21875\pi$.

Think of stacking identical sieves. Each one catches the same share of what is left. Besides the gain at 7 kHz I watch the droop: the loss inside the kept band, at its top edge.

Notice the two readouts as $N$ grows. Each stage adds another −16.95 dB at 7 kHz, but only −0.221 dB at 1 kHz. The clip’s end caption says why: each stage multiplies the gain by the same moving-average curve, so its dB add.

What it costs

The CIC has no multipliers, but it pays in register size. At 0 Hz the $M$-point running sum has gain $M$, so the CIC has gain $M^N$: here up to $8^6=262\,144$. The gain panel divides by this, which is why 0 Hz sits at 0 dB.

The registers must hold numbers $M^N$ times bigger than the input. That takes $N\log_2M$ extra bits: 3 per stage here, from 3 bits for one stage to 18 for six.

The integrators are a worry. A running sum of a signal that does not average to zero grows without end, so in fixed point it overflows. In the two’s complement arithmetic of Finite word-length effects (21.3), it wraps round.

Here that does no harm, as long as each register has those $N\log_2M$ extra bits. In a register of $B$ bits, a wrap changes a value by a whole multiple of $2^B$. Adds and subtracts carry such an error through unchanged, so the combs’ output is off by a multiple of $2^B$ at most.

The true output fits in $B$ bits, so the last wrap lands it exactly on the true value. The combs undo the integrators’ wrapping exactly.

The droop grows with $N$ too, −0.884 dB at 1 kHz for four stages. A short FIR after the CIC, running at the low rate, lifts the top of the kept band back up. It is called a compensation filter.

Worked example

1. Counting multiplies. A decimator with $N_h$ taps that filters every input does $MN_h$ multiplies per kept output; in polyphase form it does $N_h$. For 12 taps and $M=4$ that is 48 against 12, and for 22.1’s 75 taps it is 300 against 75. An interpolator with 12 taps and $L=4$ does 12 multiplies per output directly, 9 of them by zero, and 3 in polyphase form.

2. The CIC gain at 7 kHz, by hand. With $M=8$ at 64 kHz, $\Omega/2=7\pi/64$ at 7 kHz, and $M\Omega/2=7\pi/8$. One stage gives $\sin(7\pi/8)/(8\sin(7\pi/64))=0.38268/(8\cdot0.33689)=0.14199$, which is −16.95 dB. At 1 kHz the top is $\sin(\pi/8)$, also 0.38268, and the bottom is $8\sin(\pi/64)=0.39254$. That gives 0.97489, or −0.221 dB.

3. How many stages for 60 dB? Each stage gives 16.95 dB at 7 kHz, and $60/16.95=3.54$. So $N=3$ gives −50.86 dB, not enough, and $N=4$ gives −67.82 dB. Take 4 stages: the droop at 1 kHz is −0.884 dB, and the registers need $4\cdot3=12$ extra bits.

4. Register width. An 8-bit input through that 4-stage CIC needs registers of $8+12=20$ bits. The largest output is $127\cdot8^4=520\,192$, which fits in 20 bits but not in 19.

Where you’ll meet this

Sigma-delta converters (Oversampling and noise shaping, 11.3) sample at megahertz rates, and their first decimation stages are usually CIC filters. So are the first stages of software radios. At those rates a multiplier is expensive and an adder is cheap. A polyphase FIR then does the last, sharper stages at the lower rate.

SciPy’s upfirdn and resample_poly work in polyphase form, which is why 22.3’s 44.1 to 48 kHz job costs about 20 multiplies per output. The Farrow structure of 22.3 is close kin: it works like a polyphase filter with a branch for every fractional position $\mu$, its taps computed from $\mu$ rather than stored.

In Filter banks (23.1), the polyphase components of one prototype filter build a whole bank of band filters at once.

Reference card