Is multistage rate-changing actually more efficient?

Oli Charlesworth wrote:
> Hello all,
> 
> This is a question which probably boils down to "what am I missing?".
> 
> It seems to be commonly stated that for interpolation or decimation,
> it's generally more computationally efficient to perform the operation
> in multiple stages, i.e. factorise the rate-change factor, and design a
> lower-order filter for each stage.  I completely accept that designing
> the individual filters in this way achieves a lower complexity, but I'm
> beginning to question whether one actually needs to implement the rate
> change in separate stages.
> 
> Consider a system where we need to decimate by L = L1.L2.  (For the sake
> of argument, let's assume that neither L1 nor L2 equals 2, so that we
> can't "cheat" by implementing half-band filters.)  Using the typical
> approach, we might come up with two decimation filters, H1 and H2, of
> length N1 and N2 respectively.  i.e. our system is:
> 
> --> H1 --> v L1 --> H2 --> v L2 -->
> 
> If implemented as polyphase filters, the number of operations per input
> sample is (N1 / L1) + (N2 / L1.L2).
> 
> But we could construct an equivalent overall filter H as the convolution
> of H1 and H2', where H2' is H2 simply upsampled by L1 by zero-stuffing.
>  The equivalent overall system would be:
> 
> --> H --> v L1.L2 -->
> 
> The order of H is now approximately N1 + L1.N2.  Therefore, the number
> of operations per input sample in this approach is (N1 + L1.N2) / L1.L2
> = (N1 / L1.L2) + (N2 / L2).
> 
> It would seem, therefore, that depending on the particular values being
> used, the single stage approach may be as efficient or more efficient
> than the multi-stage approach.
> 
> What am I missing?  (Or, where have I made a mistake?)

The number of taps per output sample for the polyphase filter:

N2 + L2N1

The number of taps per output sample for the filter in one stage:

N2L1 + 2N1


Substitute the formula for estimating N1,N2 depending on L1,L2 and see 
that filter in one stage is going to take more.

Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com