IIR approximation with FIR

I need to implement a certain IIR filter in FPGA. The circuit has to
process several samples in one clock, which requires to unfold the IIR
feedback loop. If I do that, the circuit area and critical path become
too large.

My question is if there is a reasonably simple algorithm to
approximate IIR with FIR. I've seen lengthy and impractical academic
papers on how to do it.
At this point I'm thinking of taking an impulse response of the IIR
and simply "truncating" its tail. Is this going to work ? There is
some margin of error that can be tolerated.

Thanks,
Evgeni

OutputLogic <evgenist@gmail.com> wrote:
> I need to implement a certain IIR filter in FPGA. The circuit has to
> process several samples in one clock, which requires to unfold the IIR
> feedback loop. If I do that, the circuit area and critical path become
> too large.

Are you using a systolic array?  I know they work well for FIR, and
I believe also IIR, though I haven't tried designing one.

Systolic arrays are pretty easy to add more pipeline registers to
get more throughput and shorter critical path (and more latency).

> My question is if there is a reasonably simple algorithm to
> approximate IIR with FIR. I've seen lengthy and impractical academic
> papers on how to do it.
> At this point I'm thinking of taking an impulse response of the IIR
> and simply "truncating" its tail. Is this going to work ? There is
> some margin of error that can be tolerated.

I would guess that, like truncated polynomials, you want the
coefficients to be slightly different than from just truncation.

-- glen

>I need to implement a certain IIR filter in FPGA. The circuit has to
>process several samples in one clock, which requires to unfold the IIR
>feedback loop. If I do that, the circuit area and critical path become
>too large.
>
>My question is if there is a reasonably simple algorithm to
>approximate IIR with FIR. I've seen lengthy and impractical academic
>papers on how to do it.
>At this point I'm thinking of taking an impulse response of the IIR
>and simply "truncating" its tail. Is this going to work ? There is
>some margin of error that can be tolerated.
>
>Thanks,
>Evgeni
>
Hello,

truncating is least-squares optimal, but usually that's not exactly what I
want (see here for details:
http://signal.hut.fi/spit/publications/1996j5.pdf)
..................
You can design a filter with varying accuracy in arbitrary bands in Matlab.
My own implementation can be found here, with a couple of examples:
http://www.dsprelated.com/showcode/210.php
Works great at compile time, won't help you in real time.
..................
As a _simple_ algorithm, what comes to mind is windowing. Try some flat-top
window (raised cosine). Basically, it's the same tradeoff as in the usual
windowing discussion for FFT - out-of-band rejection vs edge accuracy.

On 10/04/2011 11:41 PM, OutputLogic wrote:
 > I need to implement a certain IIR filter in FPGA. The circuit has to
 > process several samples in one clock, which requires to unfold the IIR
 > feedback loop. If I do that, the circuit area and critical path become
 > too large.
 >
 > My question is if there is a reasonably simple algorithm to
 > approximate IIR with FIR. I've seen lengthy and impractical academic
 > papers on how to do it.
 > At this point I'm thinking of taking an impulse response of the IIR
 > and simply "truncating" its tail. Is this going to work ? There is
 > some margin of error that can be tolerated.

Evgeni,

One way would be to use the frequency domain least-squares algorithm
(FDLS) championed by Greg Berchin. If you do some Googling on his name
and these keywords, you should be able to learn what is involved, but
basically you can sample the response of the IIR filter and use that
as input to the FDLS algorithm, which can be operated in "FIR" mode.
The result would be a (numerator) polynomial (denominator = 1, i.e.,
FIR) approximating that response.

--Randy

On Tue, 4 Oct 2011 21:41:51 -0700 (PDT), OutputLogic <evgenist@gmail.com> wrote:

>At this point I'm thinking of taking an impulse response of the IIR
>and simply "truncating" its tail. Is this going to work ? There is
>some margin of error that can be tolerated.

Yes, it is going to work, provided that you use the right definition of "work".

Recall that windowing in one domain is equivalent to convolution in the other.
So if you truncate the impulse response of your filter in the time domain, it is
equivalent to windowing with a rectangular window. That, in turn, is equivalent
to convolving the frequency response of your filter with the transform of the
rectangular window (a sinc function).

Thus you have complete control over the results -- you can know exactly the
effects of the window length (and type). You just have to do the arithmetic.

In fact, if you can accommodate the entire impulse response (very coarsely
defined, for our purposes, as the time at which the impulse response amplitude
falls below the quantization noise level in the arithmetic that you implement),
then your results will be identical to those of the prototype IIR filter.

This process is similar to the Impulse Invariance filter design technique,
except that Impulse Invariance is usually associated with the emulation of
analog filters.

Greg

OutputLogic wrote:

> I need to implement a certain IIR filter in FPGA. 

And the application of this filter is what?

> The circuit has to
> process several samples in one clock, which requires to unfold the IIR
> feedback loop. If I do that, the circuit area and critical path become
> too large.

Understood.

> My question is if there is a reasonably simple algorithm to
> approximate IIR with FIR.
> At this point I'm thinking of taking an impulse response of the IIR
> and simply "truncating" its tail. Is this going to work ?

That works, however it could result in impractically long response.

> There is
> some margin of error that can be tolerated.

Start from the application requirements, then consider different 
variants of realization.


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

On Tue, 04 Oct 2011 21:41:51 -0700, OutputLogic wrote:

> I need to implement a certain IIR filter in FPGA. The circuit has to
> process several samples in one clock, which requires to unfold the IIR
> feedback loop. If I do that, the circuit area and critical path become
> too large.
> 
> My question is if there is a reasonably simple algorithm to approximate
> IIR with FIR. I've seen lengthy and impractical academic papers on how
> to do it.
> At this point I'm thinking of taking an impulse response of the IIR and
> simply "truncating" its tail. Is this going to work ? There is some
> margin of error that can be tolerated.
> 
> Thanks,
> Evgeni

Yabut -- in general IIR filters use less computation resources than FIR.  
You have a computation resource problem and you want to go to something 
that's going to be _worse_?

Perhaps there's a way to get your transfer function with an IIR structure 
that will be a better fit?  Not knowing your proposed IIR structure I 
can't say, of course.

-- 
www.wescottdesign.com

On Wed, 05 Oct 2011 13:03:32 -0500, Tim Wescott <tim@seemywebsite.com> wrote:

>Yabut -- in general IIR filters use less computation resources than FIR.  
>You have a computation resource problem and you want to go to something 
>that's going to be _worse_?

Possibly not. An advantage of an FIR implementation is that it can be
parallelized and/or pipelined in ways that an IIR implementation can not. In
particular, with an IIR filter the current output value has to be completed
before work on the next output value can begin. (Well ... strictly speaking you
can do the MA part, but not the AR part.) Not so with FIR. This can lead to
significant efficiencies in logic, especially if the FPGA clock is much higher
than the sample clock.

Greg

On Wed, 05 Oct 2011 13:26:49 -0500, Greg Berchin <gjberchin@chatter.net.invalid>
wrote:

>Possibly not. An advantage of an FIR implementation is that it can be
>parallelized and/or pipelined in ways that an IIR implementation can not. In
>particular, with an IIR filter the current output value has to be completed
>before work on the next output value can begin.

Hmm ... the more that I think about this, the more convinced I become that the
AR portion of an ARMA (IIR) filter could be implemented as a MA (FIR) filter. So
the "causality" issue mentioned above remains, but that should not affect the
efficiency with which the filter can be implemented in logic.

Greg

@Glen,

The filter has to process 32-64 samples every clock. I don't think
pipelined systolic array is going to handle this.

@Tim,

Implementing parallel IIR requires unfolding the feedback loop, and
that doesn't scale well. I found that even processing 4 symbols in a
clock (in this specific filter) consumes too much resources and the
critical path (of combinatorial elements) becomes too long.

@Vladimir,

Filter spec is available at this link: http://twitpic.com/6o0ggg
It's a one-zero, two-polls linear equalizer.

@Randy, Greg,

The method of finding coefficients described in FDLS is exactly what I
need. It looks like it can be designed as an adaptive filter. A slower
processor calculates new coefficients on a subset of data and updates
them as the channel conditions change.

If I understand correctly, if the FDLS algorithm has only numerator
coefficients, that essentially gives the FIR approximation.

So I'm concluding that there is nothing fundamentally wrong with
truncating the IIR tail and approximating it with FIR, as soon as the
truncated data is below quantization error.


Thanks,
Evgeni