IIR approximation with FIR

On Wed, 05 Oct 2011 13:26:49 -0500, Greg Berchin wrote:

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

I'd have to see that to believe it.  How can a 100-point FIR filter 
execute more efficiently than a 2nd-order IIR filter?  You're talking 100 
MAC operations vs. two or three or four.  Even taking the IIR filter's 
extra precision into account, that still seems like a no-win.

Of course, if you're talking about an IIR filter whose response pretty 
much dies out by the tenth sample, that's a different story.

-- 
www.wescottdesign.com

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

>I'd have to see that to believe it.  How can a 100-point FIR filter 
>execute more efficiently than a 2nd-order IIR filter?  You're talking 100 
>MAC operations vs. two or three or four.  Even taking the IIR filter's 
>extra precision into account, that still seems like a no-win.

I'm tending to agree with you on this. I *have* implemented IIR filters in
logic, and frankly, between the need for extra precision and the need for error
feedback to prevent limit cycles and the like, the *design* of the IIR was much
more difficult than the design of an FIR. But in terms of implementation,
especially given the revelation mentioned in my most recent post, I think that
you're correct.

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

Greg Berchin <gjberchin@chatter.net.invalid> wrote:
> 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.

A Google search for "systolic array" iir seems to return many hits
for 2D and 3D filters.  

One strange idea that I just through about was to design a filter
around every other sample.  Similar to some recent question but
the other way around, design it around z^2 instead of z.  That
likely changes what the filter can do, but also gives you more time
for each sample.  Low frequency filters will be very long as FIR,
so this might work better in that case.  

Otherwise, there is a fair amount of literature on the design
of systolic arrays for filtering.  It might be that with increased
latency you can make up for the problem of pipeline feedback.
Without trying to draw one up, it is not so easy to say.

-- glen

On Wed, 5 Oct 2011 11:44:05 -0700 (PDT), OutputLogic <evgenist@gmail.com> wrote:

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

FDLS can be set up as MA (numerator only), AR (denominator only), or ARMA
(numerator and denominator). All you have to do is set the numerator and
denominator orders accordingly -- denominator order = 0 for MA, numerator 
order = 0 for AR, and both orders != 0 for ARMA.

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

Essentially, yes. If you want to analyze it down to the "nth-degree" then it's a
bit more complicated than that, but still it's pretty easy to use a "cut and
try" approach and get good results.

Greg

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

>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

That'd make it a MAMA filter, no?   ;)


Eric Jacobsen
Anchor Hill Communications
www.anchorhill.com

On Wed, 05 Oct 2011 13:42:32 -0500, Greg Berchin wrote:

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

In particular, the current _output_ value does not have to be computed 
before the next output can begin -- some current _state_ value does, 
however, and the output then needs to be calculated from the current 
states.  So the challenge would be to see if there is a way, and if so to 
find it, to update the filter states with the same efficiency as the FIR 
filter.

I'm not enough of a digital logic guy to see how this might be achieved, 
however.

-- 
www.wescottdesign.com

(snip, I wrote)
> One strange idea that I just through about was to design a filter
> around every other sample.  

Thinking about it some more, what might help is a filter with
no y[n-1] term.  That allows a litte more time, and an additional
register, before the output is used again.   

How much of a restriction is that for a properly functioning filter?

-- glen

> Thinking about it some more, what might help is a filter with
> no y[n-1] term. =A0That allows a litte more time, and an additional
> register, before the output is used again. =A0
>
> How much of a restriction is that for a properly functioning filter?

@Glen,

This is not going to work for a couple of reasons:
 (1) Oversampling rate of the system is very low (x3 .. x5)
 (2) The filter has to process 32 to 64 symbols in parallel (in one
clock). Calculating {y[n+1]..y[n+32]} requires knowing y[n]. So using
every other sample is not going to help much

Thanks,
Evgeni

On Thu, 06 Oct 2011 11:02:37 -0700, OutputLogic wrote:

>> Thinking about it some more, what might help is a filter with no y[n-1]
>> term.  That allows a litte more time, and an additional register,
>> before the output is used again.
>>
>> How much of a restriction is that for a properly functioning filter?
> 
> @Glen,
> 
> This is not going to work for a couple of reasons:
>  (1) Oversampling rate of the system is very low (x3 .. x5) (2) The
>  filter has to process 32 to 64 symbols in parallel (in one
> clock). Calculating {y[n+1]..y[n+32]} requires knowing y[n]. So using
> every other sample is not going to help much
	
The real answer depends a _lot_ on how long of an FIR filter you'd need, 
and to some extent on the pole positions of the IIR (which is related to 
the FIR filter length, to be sure).

If you want to implement an IIR filter, the value of the output at y[n+m] 
only depends on y[n-1], y[n], and inputs at [n+1] through [n+m] (actually 
it would depend on y[n-optimal_lag], y[n], and the various inputs).  Any 
necessary recursion can be handled prior to implementing the filter.  So 
the IIR filter shouldn't be more onerous than (say) a 16-tap FIR filter.  
Even the need for high precision may be relaxed: the effective poles of 
the IIR filter become your original pole positions raised to the 32nd 
power; this pulls them away from 1 and reduces the need for high 
precision.

-- 
www.wescottdesign.com