Reply by gretzteam March 9, 20122012-03-09
>I'm not even sure that the IIR polyphase filtering suffers much >disadvantage in cases of extreme downsampling: yes, in the IIR case you >have to update the kernel every time, but in the FIR case you have a LONG
>filter kernel to compute each time. >
Here is a great example of polyphase IIR filter used for decimation. I doubt that one could do better with any form of FIR filter, considering all aspects of the implementation such as data wordlenght, coefficient quantization, amount of memory etc... http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4645807 I have a copy here if anyone is interested.
Reply by mnentwig March 8, 20122012-03-08
my generic answer to the generic question:

If you're doing communications, audio etc where real-time response on the
time scale of a FIR filter's group delay isn't critical: Consider FIR
first.

In control systems where the added group delay affects a feedback loop,
consider IIR first.

If you're struggling with the computational effort, look for an efficient
implementation that gets the job done (for example, CIC is recursive but
FIR). There are a few well-known optimizations for FIR, such as exploit a
symmetric impulse response, a half-band filter with every second
coefficient zero or a [1/2 1 1/2] three-tap FIR at the highest rate using
bit shift multipliers for example.
Reply by Tim Wescott March 6, 20122012-03-06
On Tue, 06 Mar 2012 11:47:03 -0500, robert bristow-johnson wrote:

> On 3/6/12 12:23 AM, Tim Wescott wrote: >> On Mon, 05 Mar 2012 12:49:31 -0500, robert bristow-johnson wrote: >> >>> On 3/5/12 11:35 AM, Tim Wescott wrote: >>>> >>>> One does get some computational improvement in an FIR because one can >>>> skip computations where one can't in an IIR -- >>> >>> kinda hard to do efficient polyphase filtering with IIR. >> >> I was kinda snippy the last time, > > don't sweat it. i am on and off here spottily. and i don't think > you're one of the snippy's here at comp.dsp. whether or not i'm in that > group is for other people to judge. > >> but: I'm not so sure that it's all that bad. If you use a filter form >> that realizes all poles in the states and only applies zeros on the >> output side, then I think you could do polyphase filtering with IIR, >> and do it fairly efficiently. > > well, you don't have to compute the feedforward paths for output samples > you don't keep, but you do have to do it for the feedback paths for > *every* intermediate sample. > > the issue is: what if the upsample ratio is very large? like say, what > if you're converting from 48000 to 44100? you have to upsample by 137 > (stuffing in 136 zeros), LPF, and then throw away 159 out of 160 > samples. with FIR you just drop anchor at, pick the correct set of > coefficients (that's the "polyphase" thingie), and do a, say, 32-tap > FIR. with IIR you have to do *something* for each of those 160 samples, > including the 159 you don't keep.
No you don't. You only need to run the IIR filter kernel at 48000ksps, then for the output samples you can "drop anchor" (I like that phrase) at the appropriate times and read out the best estimate of the output at that point. You do need 147 (your 137 was a typo, I think) different sets of output coefficients to cycle through as you read out at 44100, but this is akin to the 147 different FIR kernels that you need. So all in all, the "polyphase filtering with IIR" vs polyphase with FIR should work out to a very similar tradeoff to "regular old" filtering with IIR vs FIR.
> but if the OP is simply downsampling by a factor of 2 or 3, i think that > an IIR LPF (and tossing out 1 or 2 samples) might be more efficient than > a 32-tap FIR LPF. > >> I'm pretty sure that this would mean that you'd have to implement the >> filter stages in parallel, rather than in cascade; > > dunno what you mean here, Tim. > >> this, in turn, would >> mean that the coefficients for going from the states to the output >> would have obscure (and possibly lengthly) derivations. But I think it >> could be done. >> >> But then -- the OP didn't mention polyphase filtering, just decimation. > > right. which is the *latter* portion of the chore of polyphase > filtering. essentially what the OP is doing is polyphase filtering > without the step of upsampling and zero-stuffing. everything else is > the same: the LPFing and picking out the samples you wanna keep. > >> If you're decimating by an integer amount, then you're not going to be >> doing polyphase filtering at all -- just ignoring some of the output. > > well, you're doing *part* of what polyphase filtering is about. > conceptually, with polyphase filtering, you are upsampling, then LPFing, > then ignoring some of the output. doing it with an FIR saves you from > unnecessary computations of output samples that you know a priori are > ignored. but the IIR has still has to go through those ignored samples > because it's needed to update its states.
See above -- update the states, yes. Do the whole upsample/downsample thing -- no. I'm not even sure that the IIR polyphase filtering suffers much disadvantage in cases of extreme downsampling: yes, in the IIR case you have to update the kernel every time, but in the FIR case you have a LONG filter kernel to compute each time. And besides, if you're doing extreme downsampling then you can probably come pretty close by preceding your polyphase filter with a CIC stage or three, then use a final filter to clean up the signal the way you want it as you downsample. -- My liberal friends think I'm a conservative kook. My conservative friends think I'm a liberal kook. Why am I not happy that they have found common ground? Tim Wescott, Communications, Control, Circuits & Software http://www.wescottdesign.com
Reply by robert bristow-johnson March 6, 20122012-03-06
On 3/6/12 12:23 AM, Tim Wescott wrote:
> On Mon, 05 Mar 2012 12:49:31 -0500, robert bristow-johnson wrote: > >> On 3/5/12 11:35 AM, Tim Wescott wrote: >>> >>> One does get some computational improvement in an FIR because one can >>> skip computations where one can't in an IIR -- >> >> kinda hard to do efficient polyphase filtering with IIR. > > I was kinda snippy the last time,
don't sweat it. i am on and off here spottily. and i don't think you're one of the snippy's here at comp.dsp. whether or not i'm in that group is for other people to judge.
> but: I'm not so sure that it's all that > bad. If you use a filter form that realizes all poles in the states and > only applies zeros on the output side, then I think you could do polyphase > filtering with IIR, and do it fairly efficiently.
well, you don't have to compute the feedforward paths for output samples you don't keep, but you do have to do it for the feedback paths for *every* intermediate sample. the issue is: what if the upsample ratio is very large? like say, what if you're converting from 48000 to 44100? you have to upsample by 137 (stuffing in 136 zeros), LPF, and then throw away 159 out of 160 samples. with FIR you just drop anchor at, pick the correct set of coefficients (that's the "polyphase" thingie), and do a, say, 32-tap FIR. with IIR you have to do *something* for each of those 160 samples, including the 159 you don't keep. but if the OP is simply downsampling by a factor of 2 or 3, i think that an IIR LPF (and tossing out 1 or 2 samples) might be more efficient than a 32-tap FIR LPF.
> I'm pretty sure that this would mean that you'd have to implement the > filter stages in parallel, rather than in cascade;
dunno what you mean here, Tim.
> this, in turn, would > mean that the coefficients for going from the states to the output would > have obscure (and possibly lengthly) derivations. But I think it could > be done. > > But then -- the OP didn't mention polyphase filtering, just decimation.
right. which is the *latter* portion of the chore of polyphase filtering. essentially what the OP is doing is polyphase filtering without the step of upsampling and zero-stuffing. everything else is the same: the LPFing and picking out the samples you wanna keep.
> If you're decimating by an integer amount, then you're not going to be > doing polyphase filtering at all -- just ignoring some of the output.
well, you're doing *part* of what polyphase filtering is about. conceptually, with polyphase filtering, you are upsampling, then LPFing, then ignoring some of the output. doing it with an FIR saves you from unnecessary computations of output samples that you know a priori are ignored. but the IIR has still has to go through those ignored samples because it's needed to update its states. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by Tim Wescott March 6, 20122012-03-06
On Mon, 05 Mar 2012 12:49:31 -0500, robert bristow-johnson wrote:

> On 3/5/12 11:35 AM, Tim Wescott wrote: >> >> One does get some computational improvement in an FIR because one can >> skip computations where one can't in an IIR -- > > kinda hard to do efficient polyphase filtering with IIR.
I was kinda snippy the last time, but: I'm not so sure that it's all that bad. If you use a filter form that realizes all poles in the states and only applies zeros on the output side, then I think you could do polyphase filtering with IIR, and do it fairly efficiently. I'm pretty sure that this would mean that you'd have to implement the filter stages in parallel, rather than in cascade; this, in turn, would mean that the coefficients for going from the states to the output would have obscure (and possibly lengthly) derivations. But I think it could be done. But then -- the OP didn't mention polyphase filtering, just decimation. If you're decimating by an integer amount, then you're not going to be doing polyphase filtering at all -- just ignoring some of the output. -- Tim Wescott Control system and signal processing consulting www.wescottdesign.com
Reply by Tim Wescott March 5, 20122012-03-05
On Mon, 05 Mar 2012 12:49:31 -0500, robert bristow-johnson wrote:

> On 3/5/12 11:35 AM, Tim Wescott wrote: >> >> One does get some computational improvement in an FIR because one can >> skip computations where one can't in an IIR -- > > kinda hard to do efficient polyphase filtering with IIR.
I'm not so sure. Upon what do you base this supposition? What is your chosen method for doing polyphase filtering in IIR, and what leads you to believe that it is the optimal way?
>> but that may not >> necessarily outweigh the advantages of an IIR for specific cases. >> >> > if you're downsampling by a factor or 2 or 3, *maybe* the IIR would be > more efficient. you would still compute 1 or 2 in-between samples that > you would then just throw away. but the IIR might be so > >> (Mostly, the FIR is going to beat the IIR hands down. But for cases >> where you're not decimating much, and you don't care at all about lots >> of unequal phase delay, or you don't want the "preecho" of an FIR >> filter -- using an IIR filter may be to your advantage). >> >> > you don't have to have pre-echo with an FIR. your FIR kernal might be a > minimum-phase design rather than a linear-phase design. like the IIR > filtering, this sample rate conversion would not be invariant with > respect to direction. play the sound file backwards and downsample and > you will not get the same set of samples (but reversed, of course) as > you would from downsampling in the forward direction. that may or may > not be important to you.
Well, true. -- My liberal friends think I'm a conservative kook. My conservative friends think I'm a liberal kook. Why am I not happy that they have found common ground? Tim Wescott, Communications, Control, Circuits & Software http://www.wescottdesign.com
Reply by Tim Wescott March 5, 20122012-03-05
On Mon, 05 Mar 2012 20:50:11 +0000, glen herrmannsfeldt wrote:

> Tim Wescott <tim@seemywebsite.com> wrote: >> On Mon, 05 Mar 2012 04:34:11 -0600, Nasser M. Abbasi wrote: > > (snip, quoting a paper) >>> and it said in 2.3.1 under "How do I implement decimation?" >>> >>> "To implement the filtering part, you can use either FIR or IIR >>> filters." > >>> Is this true? > > (snip) >> A FIR is nearly always the best choice. But there are no fundamental >> reasons why, for some particular task, that an IIR wouldn't be better >> than an FIR. > >> But it would have to be a corner case. > > Note that the statement above doesn't say anything about better or > worse. I would, then, say that the statement is true. > > If it said that you SHOULD use IIR, for example, then it might be > questionable. > > Probably one should read the actual paper to see if other parts of the > explanation might make a difference, but I don't see anything wrong as > written above.
If it said you _should_ use IIR I'd be questioning it, for sure! -- My liberal friends think I'm a conservative kook. My conservative friends think I'm a liberal kook. Why am I not happy that they have found common ground? Tim Wescott, Communications, Control, Circuits & Software http://www.wescottdesign.com
Reply by glen herrmannsfeldt March 5, 20122012-03-05
Tim Wescott <tim@seemywebsite.com> wrote:
> On Mon, 05 Mar 2012 04:34:11 -0600, Nasser M. Abbasi wrote:
(snip, quoting a paper)
>> and it said in 2.3.1 under "How do I implement decimation?" >> >> "To implement the filtering part, you can use either FIR or IIR >> filters."
>> Is this true?
(snip)
> A FIR is nearly always the best choice. But there are no > fundamental reasons why, for some particular task, that an > IIR wouldn't be better than an FIR.
> But it would have to be a corner case.
Note that the statement above doesn't say anything about better or worse. I would, then, say that the statement is true. If it said that you SHOULD use IIR, for example, then it might be questionable. Probably one should read the actual paper to see if other parts of the explanation might make a difference, but I don't see anything wrong as written above. -- glen
Reply by robert bristow-johnson March 5, 20122012-03-05
On 3/5/12 11:35 AM, Tim Wescott wrote:
> > One does get some computational improvement in an FIR because one can > skip computations where one can't in an IIR --
kinda hard to do efficient polyphase filtering with IIR.
> but that may not > necessarily outweigh the advantages of an IIR for specific cases. >
if you're downsampling by a factor or 2 or 3, *maybe* the IIR would be more efficient. you would still compute 1 or 2 in-between samples that you would then just throw away. but the IIR might be so
> (Mostly, the FIR is going to beat the IIR hands down. But for cases > where you're not decimating much, and you don't care at all about lots of > unequal phase delay, or you don't want the "preecho" of an FIR filter -- > using an IIR filter may be to your advantage). >
you don't have to have pre-echo with an FIR. your FIR kernal might be a minimum-phase design rather than a linear-phase design. like the IIR filtering, this sample rate conversion would not be invariant with respect to direction. play the sound file backwards and downsample and you will not get the same set of samples (but reversed, of course) as you would from downsampling in the forward direction. that may or may not be important to you. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by Tim Wescott March 5, 20122012-03-05
On Mon, 05 Mar 2012 04:36:28 -0600, Nasser M. Abbasi wrote:

(top posting fixed)

> On 3/5/2012 4:34 AM, Nasser M. Abbasi wrote: >> >> For downsampling (decimation) one normally uses low pass filter before >> downsampling (anti-aliasing filter). >> >> I have thought that FIR is the best choice here for the low pass filter >> implementation for this case. But I was reading this page: >> >> http://www.dspguru.com/dsp/faqs/multirate/decimation >> >> and it said in 2.3.1 under "How do I implement decimation?" >> >> "To implement the filtering part, you can use either FIR or IIR >> filters." >> >> Is this true? I remember reading or looking at a lecture where it said >> that FIR is the correct choice for this case, and IIR would be a bad >> choice, I do not remember now the exact reason now, been a while... >> >> Thought to ask the experts here what they think.
> btw, the page does mentions, later on, the following > > "The fact that only the outputs which will be used have to be calculated > explains why decimating filters are almost always implemented using FIR > filters!" > > So may be then the first statment need to be rewritten. > > So, no problem. all is fine.
I disagree with the above statement. That may be the justification that the author uses, but the same general tradeoff exists between IIR and FIR filters when doing decimation as when doing any other task. One does get some computational improvement in an FIR because one can skip computations where one can't in an IIR -- but that may not necessarily outweigh the advantages of an IIR for specific cases. (Mostly, the FIR is going to beat the IIR hands down. But for cases where you're not decimating much, and you don't care at all about lots of unequal phase delay, or you don't want the "preecho" of an FIR filter -- using an IIR filter may be to your advantage). -- My liberal friends think I'm a conservative kook. My conservative friends think I'm a liberal kook. Why am I not happy that they have found common ground? Tim Wescott, Communications, Control, Circuits & Software http://www.wescottdesign.com