Interpolated FIR filter vs. fast convolution filtering

Hello,

I need to implement very narrow pass band filter and someone told me that
"Interpolated FIR" filter can reduce the computational complexity a lot.
So, I went online and found some papers on IFIR and it indeed looked
promising. However, when I implemented IFIR in Matlab, it did not do much
saving in my scenario. 
This is the spec of the baseband filter which will be used as a prototype
of bandpass filter:

Fpass = 0.005
Fstop = 0.0075
Apass = 0.01
Astop = 50

I used 'fdesign.lowpass' in Matlab. The straight-forward equiripple
approach yielded better result than IFIR approach. I wonder if it is
because the pass band is too narrow so that using IFIR is not beneficial in
my case? 

Also, can someone tell me when we use 'IFIR' vs. 'Fast Convolution
filtering' in general? 
I can guess that using fast-convolution filtering technique is more
beneficial when the number of taps of a filter is very large, by looking at
"computational complexity vs. number of taps" curve I found on some paper,
but I want to make sure that this is really true.
Thanks!

Thomas
 

>Hello,
>
>I need to implement very narrow pass band filter and someone told me that
>"Interpolated FIR" filter can reduce the computational complexity a lot.
>So, I went online and found some papers on IFIR and it indeed looked
>promising. However, when I implemented IFIR in Matlab, it did not do much
>saving in my scenario. 
>This is the spec of the baseband filter which will be used as a prototype
>of bandpass filter:
>
>Fpass = 0.005
>Fstop = 0.0075
>Apass = 0.01
>Astop = 50
>
>I used 'fdesign.lowpass' in Matlab. The straight-forward equiripple
>approach yielded better result than IFIR approach. I wonder if it is
>because the pass band is too narrow so that using IFIR is not beneficial
in
>my case? 
>
>Also, can someone tell me when we use 'IFIR' vs. 'Fast Convolution
>filtering' in general? 
>I can guess that using fast-convolution filtering technique is more
>beneficial when the number of taps of a filter is very large, by looking
at
>"computational complexity vs. number of taps" curve I found on some
paper,
>but I want to make sure that this is really true.
>Thanks!
>
>Thomas
> 
>


oops... my bad. I counted zeros in between the taps. It seems that the 1st
filter is 80 taps and the 2nd filter is 111 taps (excluding zeros).

"gongdori" <16548@dsprelated> wrote in message 
news:3tadnbAL441XpU_NnZ2dnUVZ_umdnZ2d@giganews.com...
> Hello,
>
> I need to implement very narrow pass band filter and someone told me that
> "Interpolated FIR" filter can reduce the computational complexity a lot.
> So, I went online and found some papers on IFIR and it indeed looked
> promising. However, when I implemented IFIR in Matlab, it did not do much
> saving in my scenario.
> This is the spec of the baseband filter which will be used as a prototype
> of bandpass filter:
>
> Fpass = 0.005
> Fstop = 0.0075
> Apass = 0.01
> Astop = 50
>
> I used 'fdesign.lowpass' in Matlab. The straight-forward equiripple
> approach yielded better result than IFIR approach. I wonder if it is
> because the pass band is too narrow so that using IFIR is not beneficial 
> in
> my case?
>
> Also, can someone tell me when we use 'IFIR' vs. 'Fast Convolution
> filtering' in general?
> I can guess that using fast-convolution filtering technique is more
> beneficial when the number of taps of a filter is very large, by looking 
> at
> "computational complexity vs. number of taps" curve I found on some paper,
> but I want to make sure that this is really true.
> Thanks!
>
> Thomas
> 

Hi,

probably the first question I'd ask myself is, am I allowed to decimate the
signal in the filtering process.

If I keep the input rate, I get a narrow-band signal sampled at a high
rate. This is inefficient, regardless by what means the filtering is done.


When comparing the efficiency, I can look at the number of _multipliers_ or
the number of _multiplications_ per processed sample. Those two numbers can
give a very different picture, if the rate is allowed to vary.

>Hi,
>
>probably the first question I'd ask myself is, am I allowed to decimate
the
>signal in the filtering process.
>
>If I keep the input rate, I get a narrow-band signal sampled at a high
>rate. This is inefficient, regardless by what means the filtering is
done.
>
>
>When comparing the efficiency, I can look at the number of _multipliers_
or
>the number of _multiplications_ per processed sample. Those two numbers
can
>give a very different picture, if the rate is allowed to vary.
>
>

Thanks for your reply. Decimation is not allowed on the problem I am
working on. I want to know when to use what filtering technique in general
because both fast convolution filtering and IFIR seem very efficient. My
guess is that fast-convolution filter is more efficient for very sharp
filters, but are they needed in real application? 

Thomas

Can't give you any rule of thumb, sorry.

One question I'd ask myself is what actually causes the cost in my
implementation: Is it multiplications per second (i.e. running everything
on a CPU), or actual multipliers, for example. 
Depending on how I define cost, results will look quite differently.
 

>Can't give you any rule of thumb, sorry.
>
>One question I'd ask myself is what actually causes the cost in my
>implementation: Is it multiplications per second (i.e. running everything
>on a CPU), or actual multipliers, for example. 
>Depending on how I define cost, results will look quite differently.
> 
>

Thanks for your reply.
Yup, that makes perfect sense. For now, I am trying to process massive data
as fast as I can in a PC. I'm using Matlab (or possibly python or C). 
Thus, what's important to me is the multiplication per second. 

I still believe a conventional decimation-filter-interpolation chain might
be a competitive solution. 
The idea is to decimate as early as possible, so that actual filtering can
be done at a lower rate. 

Here is a quick sketch of the decimator. The final stage would need more
taps to meet the ripple requirements, and then you have to interpolate back
to the original rate. There may be smarter ways to do high-rate filtering
(such as CIC or FIR stages with power-of-two coefficients)

== stage 1 ==
Black: cascaded frequency response
Blue: first stage; halfband FIR at highest rate. 
http://www.dsprelated.com/blogimages/MarkusNentwig/comp.dsp/121225/1.png
http://www.dsprelated.com/blogimages/MarkusNentwig/comp.dsp/121225/s1.txt
It can be implemented with 2 multiplications / input sample.

The "trick" is that the decimation filters are ONLY concerned about aliases
that would alias into the passband. Especially at the high rate, that
region is very narrow and allows for a cheap filter. Other aliases are
allowed, later stages will take care of them.

After this stage, throw away every second input sample. 
Implementation: FIR Delay lines shift in increments of 2, decimated samples
are never computed.
 
== stage 2 ==

Blue: second stage
http://www.dsprelated.com/blogimages/MarkusNentwig/comp.dsp/121225/2.png
http://www.dsprelated.com/blogimages/MarkusNentwig/comp.dsp/121225/s2.txt
Halfband filter at rate 1/2, plotted over the whole range. The halfband
"mid-point" (-6 dB) is at f = 0.125, and the frequency response after f =
0.25 is the alias, due to the lower rate.
This one can be implemented using only one multiplication per input sample
at rate 1/2.

=== stage 3 ===
Next halfband stage at rate 1/4. Frequency response repeats after f =
0.125.

http://www.dsprelated.com/blogimages/MarkusNentwig/comp.dsp/121225/3.png
http://www.dsprelated.com/blogimages/MarkusNentwig/comp.dsp/121225/s3.txt

=== stage 4 ===
Next halfband stage at rate 1/8.

http://www.dsprelated.com/blogimages/MarkusNentwig/comp.dsp/121225/4.png
http://www.dsprelated.com/blogimages/MarkusNentwig/comp.dsp/121225/s4.txt

=== stage 5 ===
Next halfband stage at rate 1/16.

http://www.dsprelated.com/blogimages/MarkusNentwig/comp.dsp/121225/5.png
http://www.dsprelated.com/blogimages/MarkusNentwig/comp.dsp/121225/s5.txt

=== stage 6 ===
Next halfband stage at rate 1/32.

http://www.dsprelated.com/blogimages/MarkusNentwig/comp.dsp/121225/6.png
http://www.dsprelated.com/blogimages/MarkusNentwig/comp.dsp/121225/s6.txt

=== stage 7 ===
Final FIR stage at rate 1/64 (this one is not halfband, but symmetric FIR)
http://www.dsprelated.com/blogimages/MarkusNentwig/comp.dsp/121225/7.png
http://www.dsprelated.com/blogimages/MarkusNentwig/comp.dsp/121225/s7.txt
This one needs to be re-designed for tighter ripple specs

Right now, the complete in-band response looks like this:
http://www.dsprelated.com/blogimages/MarkusNentwig/comp.dsp/121225/8.png

As said, this is not meant as a complete solution, just an example how it
can be done. 

>> === stage 1 === It can be implemented with 2 multiplications / input
sample.

actually the first stage can be implemented with *1* multiplication per
input sample because of decimation-by-two.
That's quite important: this one multiplication at rate 1 is worth 64
multiplications at rate 1/64, which could buy me a 127 tap symmetric FIR
filter as final stage, for example...

>>> === stage 1 === It can be implemented with 2 multiplications / input
>sample.
>
>actually the first stage can be implemented with *1* multiplication per
>input sample because of decimation-by-two.
>That's quite important: this one multiplication at rate 1 is worth 64
>multiplications at rate 1/64, which could buy me a 127 tap symmetric FIR
>filter as final stage, for example...
>

Thank you so much for your reply. It seems that the multi-stage multi-rate
filter you mentioned can be very efficient filter indeed. 
Efficiency wise it seems the best among all the candidates. 

When I studied this filter, I noticed that it was "time-varying" filter. It
seemed true because the rate changes in the middle of the filtering
operation . I wonder if it would do anything bad to the signal? Would it
let me preserve both phase and amplitude of the input signal? 
Thanks!

Thomas