Real usefullness of the polyphase form in DSP / CPU implementation of a decimator

Started by tsd82 May 13, 2015
Hello all,

I read in a lot of papers that the polyphase form is the right way to
implement a decimation filter, either on FPGA, DSP or CPU.

But if I understand well why it is used in a FPGA (because it enables to
have hardware resources working all the time at the lower rate, and not
from time to time, but at the higher rate), I really cannot understand the
usefullness of the polyphase form in a DSP / CPU (software)
implementation.

Let me explain my poor understanding:

Theoric (naive) implementation of decimation is: 
  [Anti-aliasing FIR / N taps] -> [Downsampling by decimation factor / M]

But practical implementation (in software) consists of running the
anti-aliasing filter only once every M input samples, e.g. we update the
FIR delay line M samples at a time. So the practical complexity is N / M
MAC / input sample.

Likewise, the polyphase implementation consumes also N / M MAC per input
sample. So absolutely no gain in software!

Yet, in papers and lectures about polyphase implementation, they always
compare the polyphase form with the  naive implementation. I don't
understand why.

If anybody has any idea about this, and where I am wrong or what I have
misunderstood, I would be very happy!

Thanks,

Julien

PS : Note that I am only speaking of polyphase applications to FIR +
decimation, not about channelization applications, for which, as I
understand, the Harris method based on polyphase filters and FFT is really
powerfull.



---------------------------------------
Posted through http://www.DSPRelated.com
On Wed, 13 May 2015 17:22:30 -0500, tsd82 wrote:

> Hello all, > > I read in a lot of papers that the polyphase form is the right way to > implement a decimation filter, either on FPGA, DSP or CPU. > > But if I understand well why it is used in a FPGA (because it enables to > have hardware resources working all the time at the lower rate, and not > from time to time, but at the higher rate), I really cannot understand > the usefullness of the polyphase form in a DSP / CPU (software) > implementation. > > Let me explain my poor understanding: > > Theoric (naive) implementation of decimation is: > [Anti-aliasing FIR / N taps] -> [Downsampling by decimation factor / > M] > > But practical implementation (in software) consists of running the > anti-aliasing filter only once every M input samples, e.g. we update the > FIR delay line M samples at a time. So the practical complexity is N / M > MAC / input sample. > > Likewise, the polyphase implementation consumes also N / M MAC per input > sample. So absolutely no gain in software! > > Yet, in papers and lectures about polyphase implementation, they always > compare the polyphase form with the naive implementation. I don't > understand why. > > If anybody has any idea about this, and where I am wrong or what I have > misunderstood, I would be very happy! > > Thanks, > > Julien >
That's because on a decimator, your "naive implementation" is already the polyphase implementation, because on a decimator the polyphase trick is to not calculate the samples that you're not going to use (this is why the same trick doesn't work on IIR filters). The only advantage to doing a smaller MAC every time rather than a larger mac every Mth time is processor load-balancing; you're running more shorter operations instead of one long one. Potentially advantageous if you're not running any kind of preemptive OS because it blocks other tasks for less time. But not a huge deal one way or another. -- Rob Gaddi, Highland Technology -- www.highlandtechnology.com Email address domain is currently out of order. See above to fix.
"tsd82" <105802@DSPRelated> writes:

> Hello all, > > I read in a lot of papers that the polyphase form is the right way to > implement a decimation filter, either on FPGA, DSP or CPU. > > But if I understand well why it is used in a FPGA (because it enables to > have hardware resources working all the time at the lower rate, and not > from time to time, but at the higher rate), I really cannot understand the > usefullness of the polyphase form in a DSP / CPU (software) > implementation. > > Let me explain my poor understanding: > > Theoric (naive) implementation of decimation is: > [Anti-aliasing FIR / N taps] -> [Downsampling by decimation factor / M] > > But practical implementation (in software) consists of running the > anti-aliasing filter only once every M input samples, e.g. we update the > FIR delay line M samples at a time. So the practical complexity is N / M > MAC / input sample. > > Likewise, the polyphase implementation consumes also N / M MAC per input > sample. So absolutely no gain in software! > > Yet, in papers and lectures about polyphase implementation, they always > compare the polyphase form with the naive implementation. I don't > understand why. > > If anybody has any idea about this, and where I am wrong or what I have > misunderstood, I would be very happy! > > Thanks, > > Julien > > PS : Note that I am only speaking of polyphase applications to FIR + > decimation, not about channelization applications, for which, as I > understand, the Harris method based on polyphase filters and FFT is really > powerfull.
Hi Julien, The term "polyphase filtering" has always seemed mysterious and (overly) complex to me. For decimation, the reality of the situation is very simple: don't compute output samples you aren't going to use. That is essentially where the efficiency of "polyphase decimation" is obtained. -- Randy Yates Digital Signal Labs http://www.digitalsignallabs.com
Dear Rob and Randy,

Thanks for your kind answer.

So if I understand well, in textbooks, they introduce the polyphase
technique with the example of FIR decimation, not because of its real
usefullness (except for FPGA/ASIC impl&eacute;mentations), but because it is the
simplest exemple of polyphase technique, opening understanding to, for
example, Harris chanelization technique, maybe IIR polyphase (yet, I have
never seen that in practice for now!).

Kind regards,

Julien


---------------------------------------
Posted through http://www.DSPRelated.com
"tsd82" <105802@DSPRelated> writes:

> Dear Rob and Randy, > > Thanks for your kind answer. > > So if I understand well, in textbooks, they introduce the polyphase > technique with the example of FIR decimation, not because of its real > usefullness (except for FPGA/ASIC impl&Atilde;&copy;mentations), but because it is
the
> simplest exemple of polyphase technique, opening understanding to, for > example, Harris chanelization technique, maybe IIR polyphase (yet, I have > never seen that in practice for now!).
Hi Julien, I believe it is introduced first more for its practical usefulness and wide application and not because it introduces other more complex techniques. But I suppose you'd have to ask the author what his intention was to be sure. Rick Lyons visits this group often - maybe he can tell us why he covers polyphase decimation in his book. @BOOK{lyonsthird, title = "{Understanding Digital Signal Processing}", edition = "third", author = "{Richard~G.~Lyons}", publisher = "Prentice Hall", year = "2011"} Really, why does it matter? Learn the technique for its immediate application and move on. -- Randy Yates Digital Signal Labs http://www.digitalsignallabs.com
On 14.05.2015 21:31, tsd82 wrote:
(snip)

 > maybe IIR polyphase (yet, I have never seen that in practice for now!).
 >
 > Kind regards,
 >
 > Julien


Hi, Julien.

Not quite sure what should "in practice" mean, but IIR polyphase filters 
can indeed be realized with the use of all-pass filters!

I've seen that technique described in the following books:
(A) Chapter 10 ("Recursive Polyphase Filters") of "Multurate Signal 
Processing" by Harris,
(B) Chapter 9 ("A Most Efficient Digital Filter: The Two-Path Recursive 
All-Pass Filter") by Harris in the book "Streamlining Digital Signal 
Processing" (SE) edited by Lyons.

In (A) the technique is discussed in greater detail, while (B) looks to 
be an abridgement.

As far as I could understand, it's a special (yet very effective) class 
of IIR filters (which could be low-pass, high-pass or band-pass). So you 
don't convert an existing IIR design to a polyphase form, but rather 
design a new IIR filter meeting your specifications using all-pass networks.

Evgeny.

On 15.05.2015 11:55, Evgeny Filatov wrote:
> On 14.05.2015 21:31, tsd82 wrote: > (snip) > > > maybe IIR polyphase (yet, I have never seen that in practice for now!). > > > > Kind regards, > > > > Julien > > > Hi, Julien. > > Not quite sure what should "in practice" mean, but IIR polyphase filters > can indeed be realized with the use of all-pass filters! > > I've seen that technique described in the following books: > (A) Chapter 10 ("Recursive Polyphase Filters") of "Multurate Signal > Processing" by Harris, > (B) Chapter 9 ("A Most Efficient Digital Filter: The Two-Path Recursive > All-Pass Filter") by Harris in the book "Streamlining Digital Signal > Processing" (SE) edited by Lyons. > > In (A) the technique is discussed in greater detail, while (B) looks to > be an abridgement. > > As far as I could understand, it's a special (yet very effective) class > of IIR filters (which could be low-pass, high-pass or band-pass). So you > don't convert an existing IIR design to a polyphase form, but rather > design a new IIR filter meeting your specifications using all-pass > networks. > > Evgeny. >
I need to correct my post in that regarding polyphase multirate IIR structures, the text by Harris only considers the cases of 2-to-1 and 8-to-1 down sampling (or 1-to-2 and 1-to-8 up sampling). Does that imply that polyphase multirate IIR filters are possible for N-to-1 down sampling and 1-to-N up sampling? I tend to believe so, although Harris doesn't seem to explicitly state that in the text. Evgeny.
On 05/15/15 13:02, Evgeny Filatov wrote:
> On 15.05.2015 11:55, Evgeny Filatov wrote: >> On 14.05.2015 21:31, tsd82 wrote: >> (snip) >> >> > maybe IIR polyphase (yet, I have never seen that in practice for >> now!). >> > >> > Kind regards, >> > >> > Julien >> >> >> Hi, Julien. >> >> Not quite sure what should "in practice" mean, but IIR polyphase filters >> can indeed be realized with the use of all-pass filters! >> >> I've seen that technique described in the following books: >> (A) Chapter 10 ("Recursive Polyphase Filters") of "Multurate Signal >> Processing" by Harris, >> (B) Chapter 9 ("A Most Efficient Digital Filter: The Two-Path Recursive >> All-Pass Filter") by Harris in the book "Streamlining Digital Signal >> Processing" (SE) edited by Lyons. >> >> In (A) the technique is discussed in greater detail, while (B) looks to >> be an abridgement. >> >> As far as I could understand, it's a special (yet very effective) class >> of IIR filters (which could be low-pass, high-pass or band-pass). So you >> don't convert an existing IIR design to a polyphase form, but rather >> design a new IIR filter meeting your specifications using all-pass >> networks. >> >> Evgeny. >> > > > I need to correct my post in that regarding polyphase multirate IIR > structures, the text by Harris only considers the cases of 2-to-1 and > 8-to-1 down sampling (or 1-to-2 and 1-to-8 up sampling). Does that imply > that polyphase multirate IIR filters are possible for N-to-1 down > sampling and 1-to-N up sampling? I tend to believe so, although Harris > doesn't seem to explicitly state that in the text. > > Evgeny. >
This class of filters is called as "recursive Nth-band" filters. See, http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1086034&isnumber=23585 Best regards, Juha
On 15.05.2015 15:18, ylikaaki wrote:

> This class of filters is called as "recursive Nth-band" filters. See, > http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1086034&isnumber=23585 > > Best regards, > Juha >
Thanks, Juha! That's a great link and more than I could hope for. Best regards, Evgeny.
On 15.05.2015 15:18, ylikaaki wrote:
> On 05/15/15 13:02, Evgeny Filatov wrote: >> On 15.05.2015 11:55, Evgeny Filatov wrote: >>> On 14.05.2015 21:31, tsd82 wrote: >>> (snip) >>> >>> > maybe IIR polyphase (yet, I have never seen that in practice for >>> now!). >>> > >>> > Kind regards, >>> > >>> > Julien >>> >>> >>> Hi, Julien. >>> >>> Not quite sure what should "in practice" mean, but IIR polyphase filters >>> can indeed be realized with the use of all-pass filters! >>> >>> I've seen that technique described in the following books: >>> (A) Chapter 10 ("Recursive Polyphase Filters") of "Multurate Signal >>> Processing" by Harris, >>> (B) Chapter 9 ("A Most Efficient Digital Filter: The Two-Path Recursive >>> All-Pass Filter") by Harris in the book "Streamlining Digital Signal >>> Processing" (SE) edited by Lyons. >>> >>> In (A) the technique is discussed in greater detail, while (B) looks to >>> be an abridgement. >>> >>> As far as I could understand, it's a special (yet very effective) class >>> of IIR filters (which could be low-pass, high-pass or band-pass). So you >>> don't convert an existing IIR design to a polyphase form, but rather >>> design a new IIR filter meeting your specifications using all-pass >>> networks. >>> >>> Evgeny. >>> >> >> >> I need to correct my post in that regarding polyphase multirate IIR >> structures, the text by Harris only considers the cases of 2-to-1 and >> 8-to-1 down sampling (or 1-to-2 and 1-to-8 up sampling). Does that imply >> that polyphase multirate IIR filters are possible for N-to-1 down >> sampling and 1-to-N up sampling? I tend to believe so, although Harris >> doesn't seem to explicitly state that in the text. >> >> Evgeny. >> > > This class of filters is called as "recursive Nth-band" filters. See, > http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1086034&isnumber=23585 > > Best regards, > Juha >
You know a classic work when you see it!.. The best part of fun with a classic work comes from the breadth of knowledge it brings into life by inspiring quality research. That's why the Google Scholar "Cited by" option provides so much fun with the classic works. Multiplierless (ok, actually finite precision) IIR filters? I'm speechless! http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=823523 http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=740130 http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=775386 Best regards, Evgeny.