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

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

Started by ●May 13, 2015

Reply by ●May 13, 20152015-05-13

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.

Reply by ●May 14, 20152015-05-14

"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

Reply by ●May 14, 20152015-05-14

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é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

Reply by ●May 14, 20152015-05-14

"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Ã©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

Reply by ●May 15, 20152015-05-15

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.

Reply by ●May 15, 20152015-05-15

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.

Reply by ●May 15, 20152015-05-15

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

Reply by ●May 15, 20152015-05-15

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.

Reply by ●May 15, 20152015-05-15

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.