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 ω 0 0.9 radians . If we desire passband ripple δ p 0.002 and stopband ripple δ s 0.001 , then Kaiser's formula approximates the required FIR filter length to be Nh -10 10 δP δS 13 2.3 Δ ω 900 choosing Δ ω 2 2 ω 0 L as the width of the first transition band (i.e., ignoring the other transition bands for this rough approximation). Thus, a polyphase implementation 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 ω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 and upsampling (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 15 ω is 2 15 -periodic in ω. Design F z to remove the remaining images. The first and second plots in illustrate example DTFTs for the desired signal x n and its L-upsampled version v l , respectively. Our objective for interpolation, is to remove all but the shaded spectral image shown in the second plot. The third plot shows that, due to symmetry requirements G z 15 will be able to remove only one image in the frequency range 0 2 15 . Due to its periodicity, however, G z 15 also removes some of the other undesired images, namely those centered at 15 m 2 15 for m . F z is then used to remove the remaining undesired images, namely those centered at m 2 15 for m such that m is not a multiple of 15. Since it is possible that the passband ripples of F z and G z 15 could add constructively, we specify δ p 0.001 for both F z and G z , half the passband ripple specified for H z . Assuming that the transition bands in F z have gain no greater than one, the stopband ripples will not be amplified and we can set δ s 0.001 for both F z and G z , the same specification as for H z .

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 ω 2 with width ω 0 0.1 rad . Likewise, the transition bands in F z have width 4 2 ω 0 30 2.2 30 rad . Plugging these specifications into the Kaiser length approximation, we obtain N g 64 and N f 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 of reference, recall that a polyphase implementation of the one-stage interpolator would require N h 900 multiplications per input point. Using a cascade of two single-stage polyphase interpolators to implement the two-stage scheme, we find that the first interpolator would require N g 64 per input point x n , while the second would require N f 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 64 2 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 to choose the first upsampling ratio (L1) as small as possible, so that the second stage of interpolation 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 case of multi-stage interpolation, we have the block diagrams and filter-design methodology illustrated in and .