Multistage Decimation

In the single-stage interpolation structure illustrated in Figure 1, the required impulse response of Hz H z can be very long for large LL.

Consider, for example, the case where L=30 L 30 and the input signal has a bandwidth of ω 0 =0.9πradians ω 0 0.9 radians . If we desire passband ripple δ p =0.002 δ p 0.002 and stopband ripple δ s =0.001 δ s 0.001 , then Kaiser's formula approximates the required FIR filter length to be Nh≈-10log10δPδS-132.3Δω≈900 Nh -10 10 δP δS 13 2.3 Δ ω 900 choosing Δω=2π-2 ω 0 L Δ ω 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 900900 multiplies per input sample.

Consider now the two-stage implementation illustrated in Figure 2.

We claim that, when LL is large and ω0ω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 L 1 2 and L 2 =15 L 2 15 so that L 1 L 2 =L=30 L 1 L 2 L 30 . We then desire a pair FzGz F z G z which results in the same performance as Hz H z . As a means of choosing these filters, we employ a Noble identity to reverse the order of filtering and upsampling (see Figure 3).

It is now clear that the composite filter Gz15Fz G z 15 F z should be designed to meet the same specifications as Hz H z . Thus we adopt the following strategy:

The first and second plots in Figure 4 illustrate example DTFTs for the desired signal xn x n and its LL-upsampled version vl 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 Gz15 G z 15 will be able to remove only one image in the frequency range 02π15 0 2 15 . Due to its periodicity, however, Gz15 G z 15 also removes some of the other undesired images, namely those centered at π15+m2π15 15 m 2 15 for m∈ℤ m . Fz F z is then used to remove the remaining undesired images, namely those centered at m2π15 m 2 15 for m∈ℤ m such that mm is not a multiple of 1515. Since it is possible that the passband ripples of Fz F z and Gz15 G z 15 could add constructively, we specify δ p =0.001 δ p 0.001 for both Fz F z and Gz G z , half the passband ripple specified for Hz H z . Assuming that the transition bands in Fz F z have gain no greater than one, the stopband ripples will not be amplified and we can set δ s =0.001 δ s 0.001 for both Fz F z and Gz G z , the same specification as for Hz H z .

The computational savings of the multi-stage structure result from the fact that the transition bands in both Fz F z and Gz G z are much wider than the transition bands in Hz H z . From the block diagram, we can infer that the transition band in Gz G z is centered at ω=π2 ω 2 with width π- ω 0 =0.1πrad ω 0 0.1 rad . Likewise, the transition bands in Fz F z have width 4π-2 ω 0 30=2.230πrad 4 2 ω 0 30 2.2 30 rad . Plugging these specifications into the Kaiser length approximation, we obtain N g ≈64 N g 64 and N f ≈88 N f 88 Already we see that it will be much easier, computationally, to design two filters of lengths 6464 and 8888 than it would be to design one 900900-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 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 N g 64 per input point xn x n , while the second would require N f ≈88 N f 88 multiplies per output of Gz G z . Since Gz G z outputs two points per input xn x n , the two-stage structure would require a total of ≈64+2×88=240 64 2 88 240 multiplies per input. Clearly this is a significant savings over the 900900 multiplies required by the one-stage structure. Note that it was advantageous to choose the first upsampling ratio (L1L1) 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 Figure 5 and Figure 6.