3
$\begingroup$

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?

$\endgroup$

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.