Let's say you want to implement an FIR filter $h[k]$ with $L$ taps and downsample the output:

$v[k] = x[k] * h[k]$

$y[m] = v[kD]$

The "naive" way would be to compute all the samples of $v[k]$, then compute $y[m]$. This should have complexity of $O(LD)$ to process a block of $D$ samples.

The "less naive" way would be to just compute every $D^{th}$ sample of $y[m]$ directly:

$y[m] = v[mD] = \sum_{l = 0}^{L-1} x[mD - l] h[l]$

This should have a complexity of $O(LD/D) = O(L)$ to process a block of $D$ samples.

The "smart" way, according to everything I read (e.g. Proakis & Manolakis Digital Signal Processing: Principles, Algorithms, and Applications, 4th ed. p.771, also here), is to use a polyphase filter/decimator.

This seems to have the same computational burden: every $D^{th}$ timestep, you are computing the output of $D$ filters, each of which has $L/D$ taps, for a total complexity of roughly $O(DL/D) = O(L)$.

Is my analysis correct? If so, what is the advantage of using a polyphase decimator if the "skip $D$" method has the same complexity and is much easier to implement?


Yes, they have the same complexity because they are exactly the same. By calculating every $D^{th}$ sample you'll see there are $D$ filters needed - each with $L/D$ taps.

So there is no advantage because the are exactly the same.


One advantage of the polyphase filter is when hardware resources are limited. The polyphase approach replaces a $L$ tap filter with $N$ filter sets of $L/N$ taps. Once you've done that you can just use a single $L/N$ filter set and swap coefficients.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.