1.16 Multi-stage interpolation and decimation

Multistage decimation

In the single-stage interpolation structure illustrated in , the required impulse response of $H(z)$ can be very long for large $L$ .

Consider, for example, the case where $L=30$ and the input signal has a bandwidth of ${\omega }_0=0.9\pi \mathrm{radians}$ . If we desire passband ripple ${\delta }_p=0.002$ and stopband ripple ${\delta }_s=0.001$ , then Kaiser's formula approximates the required FIR filter length to be $$N_h\approx \frac{-10\lg ({\delta }_P{\delta }_S)-13}{2.3\Delta (\omega )}\approx 900$$ choosing $\Delta (\omega )=\frac{2\pi -2{\omega }_0}{L}$ as the width of the first transition band ( i.e. , ignoring the other transition bands for this rough approximation). Thus, a polyphaseimplementation of this interpolation task would cost about $900$ multiplies per input sample.

Consider now the two-stage implementation illustrated in .

We claim that, when $L$ is large and ${\omega }_0$ is near Nyquist, the two-stage scheme can accomplish the same interpolation task with less computation.

Let's revisit the interpolation objective of our previous example. Assume that $L_1=2$ and $L_2=15$ so that $L_1{L}_2=L=30$ . We then desire a pair $\{F(z), G(z)\}$ which results in the same performance as $H(z)$ . As a means of choosing these filters, we employ a Noble identity to reverse the order of filtering andupsampling (see ).

It is now clear that the composite filter $G(z^{15})F(z)$ should be designed to meet the same specifications as $H(z)$ . Thus we adopt the following strategy:

• Design $G(z^{15})$ to remove unwanted images, keeping in mind that the DTFT $G(e^{i\times 15\omega })$ is $\frac{2\pi }{15}$ -periodic in $\omega$ .
• Design $F(z)$ to remove the remaining images.

The computational savings of the multi-stage structure result from the fact that the transition bands in both $F(z)$ and $G(z)$ are much wider than the transition bands in $H(z)$ . From the block diagram , we can infer that the transition band in $G(z)$ is centered at $\omega =\frac{\pi }{2}$ with width $\pi -{\omega }_0=0.1\pi \mathrm{rad}$ . Likewise, the transition bands in $F(z)$ have width $\frac{4\pi -2{\omega }_0}{30}=\frac{2.2}{30}\pi \mathrm{rad}$ . Plugging these specifications into the Kaiser length approximation, we obtain $$N_g\approx 64$$ and $$N_f\approx 88$$ Already we see that it will be much easier, computationally, to design two filters of lengths $64$ and $88$ than it would be to design one $900$ -tap filter.

As we now show, the computational savings also carry over to the operation of the two-stage structure. As a point ofreference, recall that a polyphase implementation of the one-stage interpolator would require $N_h\approx 900$ multiplications per input point. Using a cascade of two single-stage polyphase interpolators to implement thetwo-stage scheme, we find that the first interpolator would require $N_g\approx 64$ per input point $x(n)$ , while the second would require $N_f\approx 88$ multiplies per output of $G(z)$ . Since $G(z)$ outputs two points per input $x(n)$ , the two-stage structure would require a total of $$\phantom{}\approx 64+2\times 88=240$$ multiplies per input. Clearly this is a significant savings over the $900$ multiplies required by the one-stage structure. Note that it was advantageous tochoose the first upsampling ratio ( $L_1$ ) as small as possible, so that the second stage ofinterpolation operates at a low rate.

Multi-stage decimation can be formulated in a very similar way. Using the same example quantities as we did for the caseof multi-stage interpolation, we have the block diagrams and filter-design methodology illustrated in and .