pros/cons of various FIR structures

I'm looking at two texts for basic info about why any one FIR
structure would be preferable to another:

   Discrete-Time Signal Processing (original edition)
   Oppenheim & Schafer

   Digital Signal Processing: Principles, Algorithms, and Appilcations
   3rd edition
   Proakis & Manolakis

I also looked in the FIR FAQ at http://www.dspguru.com, the comp.dsp
FAQ, and numerous web pages and online tutorial documents.  This was
not discussed in a grad course I took, either.  Is there anywhere a
simple summary of pros/cons for the various FIR structures?

Thanks.

Fred
-- 
Fred Ma, fma@doe.carleton.ca
Dept. of Electronics, Carleton University, Ottawa, Ontario, Canada

Fred Ma wrote:

> I'm looking at two texts for basic info about why any one FIR
> structure would be preferable to another:
> 
>    Discrete-Time Signal Processing (original edition)
>    Oppenheim & Schafer
> 
>    Digital Signal Processing: Principles, Algorithms, and Appilcations
>    3rd edition
>    Proakis & Manolakis
> 
> I also looked in the FIR FAQ at http://www.dspguru.com, the comp.dsp
> FAQ, and numerous web pages and online tutorial documents.  This was
> not discussed in a grad course I took, either.  Is there anywhere a
> simple summary of pros/cons for the various FIR structures?
> 
> Thanks.
> 
> Fred

Which FIR structures are you thinking of? Transversal and what else?
Frequency sampling?

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

"Fred Ma" <fma@doe.carleton.ca> wrote in message
news:40A98016.60A4AB70@doe.carleton.ca...
> I'm looking at two texts for basic info about why any one FIR
> structure would be preferable to another:
>
>    Discrete-Time Signal Processing (original edition)
>    Oppenheim & Schafer
>
>    Digital Signal Processing: Principles, Algorithms, and Appilcations
>    3rd edition
>    Proakis & Manolakis
>
> I also looked in the FIR FAQ at http://www.dspguru.com, the comp.dsp
> FAQ, and numerous web pages and online tutorial documents.  This was
> not discussed in a grad course I took, either.  Is there anywhere a
> simple summary of pros/cons for the various FIR structures?
>
> Thanks.
>
> Fred
> -- 
> Fred Ma, fma@doe.carleton.ca
> Dept. of Electronics, Carleton University, Ottawa, Ontario, Canada

One advantage to the transpose form, when implemented in FPGAs or ASICs, is
that you can change all the coeffs at the same time and transition nicely.
I think that may be useful for equalizers.  It also has a structure that you
can put into preplaced modules that can be replicated depending on filter
length.  But other than that it's pretty much the same as the transversal.
-Kevin

Jerry Avins wrote:
> 
> > I'm looking...for basic info about why any one FIR structure would
> > be preferable to another
> 
> Which FIR structures are you thinking of? Transversal and what else?
> Frequency sampling?


I was initially looking at the ones described under the FIR section:

   1. Direct form
   2. Cascade form
   3. Frequency sampling
   4. Lattice

Direct form is the transversal filter.  It folds, to halve the
multiplier requirement for a symmetric impulse response (IR).

Cascade form is for when the filter is specified via zeros in the
z-domain.  As for symmetric IRs, linear phase allows folding (cascaded
2nd order subsystems collapse into half as many 4th order subsystems),
thus halving the multipliers.  It seems to me like it's just a
transformation to convert z-domain information into IR taps, so I'm
not sure why one would prefer cascade form over direct form.

At first, I didn't see much reason to choose between cascade form and
frequency sampling, since the mapping between z-domain and w-domain
(omega domain) seemed pretty simple, at least at an intuitive level.
But in reviewing this many-year old material (for me), I see an
example showing the frequency sampling implementation taking fewer
resources.  I think it would be helpful for texts to state up front
the motivation for the different structures.  It sounds like a
complaint (and it is!) but the fact is, practitioners in the
profession are frequently called on to be to-the-point in
documentation.  I guess I appreciate that philosophy all the more when
put into the position of the reader.

The lattice structure is described as pervasive in speech processing
and adaptive filters.

I'm reading ahead and realize that the answer for my situation
(hardware) lies in the IIR section.  There seems to be a good reason
to favour one of those structures, at least at first glance.  The
transposed direct form II (TDFII) strucure is nice because of the
delays between additions, thus giving time for the additions to
finish.  I wonder if this "benefit" might be a misconception, though,
considering the existence of carry-save adders (CSAs, which I was just
reviewing on the web).  They remove the bottleneck of doing
multi-operand additions/per cycle (throughput, that is, not latency).
In fact, it seems better to avoid TDFII because using CSA to do all
the additions at once means that only one fast adder is needed to get
the final sum.

I've read that CSAs don't help much in FPGAs because of the built-in
fast addition circuitry, so the above speculation is probably more
about ASIC.

But this is a digression from the original question of reasons to
favour one FIR structure over another (aside from the lattice
structure, which is for speach processing and adaptive filtering).

Fred
-- 
Fred Ma, fma@doe.carleton.ca
Dept. of Electronics, Carleton University, Ottawa, Ontario, Canada
*|  If I don't reply to your email, please sent it again.  I may  |*
*|  have erased along with the deluge of post-filter spam.        |*

Kevin Neilson wrote:
> 
> > I'm looking at two texts for basic info about why any one FIR
> > structure would be preferable to another
> 
> One advantage to the transpose form, when implemented in FPGAs or ASICs, is
> that you can change all the coeffs at the same time and transition nicely.
> I think that may be useful for equalizers.  It also has a structure that you
> can put into preplaced modules that can be replicated depending on filter
> length.  But other than that it's pretty much the same as the transversal.

I was just mentioning in another response that the tranposed form has adders
that are separated by delays, whereas the tranversal based structures have
the adders forming (effectively) a tree.  Use of CSA for this would eliminate
the need for high-speed adders for all but the final summation.  This is
just speculation on my part, not based on any ASIC design experience.  I've
also read that concern about high-speed adders is not as big a concern for
FPGA implementations because of the built in circuitry (though of course, I
imagine that an adder tree still needs pipelining between levels in the tree).
Again, not based on design experience, just speculating based on
textbook/web readings.

Fred
-- 
Fred Ma, fma@doe.carleton.ca
Dept. of Electronics, Carleton University, Ottawa, Ontario, Canada
*|  If I don't reply to your email, please sent it again.  I may  |*
*|  have erased along with the deluge of post-filter spam.        |*

Fred Ma wrote:

> Jerry Avins wrote:
> 
>>>I'm looking...for basic info about why any one FIR structure would
>>>be preferable to another
>>
>>Which FIR structures are you thinking of? Transversal and what else?
>>Frequency sampling?
> 
> 
> 
> I was initially looking at the ones described under the FIR section:
> 
>    1. Direct form
>    2. Cascade form
>    3. Frequency sampling
>    4. Lattice
> 
> Direct form is the transversal filter.  It folds, to halve the
> multiplier requirement for a symmetric impulse response (IR).

With DSPs, folding saves nothing (the addition before the MAC uses as 
much time as the MAC that's saved, and the extra bookkeeping isn't 
trivial). If folding only doubles the execution time, I think you've 
coded well. It will certainly more than double the code size, but as 
that's small to start, no problem.

But it seems that your viewpoint is that of a hardware designer, so it 
may be none of that matters. Having figured out the preceding profound
thought, any more I might add would waste your reading time.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

On 18 May 2004 08:36:20 GMT, Fred Ma <fma@doe.carleton.ca> wrote:

>Jerry Avins wrote:
>> 
>> > I'm looking...for basic info about why any one FIR structure would
>> > be preferable to another
>> 
>> Which FIR structures are you thinking of? Transversal and what else?
>> Frequency sampling?
>
>
>I was initially looking at the ones described under the FIR section:
>
>   1. Direct form
>   2. Cascade form
>   3. Frequency sampling
>   4. Lattice
>
>Direct form is the transversal filter.  It folds, to halve the
>multiplier requirement for a symmetric impulse response (IR).
>
>Cascade form is for when the filter is specified via zeros in the
>z-domain.  As for symmetric IRs, linear phase allows folding (cascaded
>2nd order subsystems collapse into half as many 4th order subsystems),
>thus halving the multipliers.  It seems to me like it's just a
>transformation to convert z-domain information into IR taps, so I'm
>not sure why one would prefer cascade form over direct form.
>

Hi Fred,
  I had trouble following your decsripition of 
"Cascade form".  Will you tell me what pages of 
Opp & Schafer and Proakis & Manlakis 
cover this "cascade form".  That would help me.

>At first, I didn't see much reason to choose between cascade form and
>frequency sampling, since the mapping between z-domain and w-domain
>(omega domain) seemed pretty simple, at least at an intuitive level.
>But in reviewing this many-year old material (for me), I see an
>example showing the frequency sampling implementation taking fewer
>resources.  

Yes, you're right.  For some applications 
(depending on the desired filter's passband 
width, transition region width, and stopband 
attenuation) linear-phase Freq sampling filters 
can be more computationally efficient than 
Parks-McClellan-design nonrecursive FIR filters.
I spent many months studying that issue.
(That topic is in Chapter 7 of the 2nd edition 
of my DSP book.)

>I think it would be helpful for texts to state up front
>the motivation for the different structures.  It sounds like a
>complaint (and it is!) but the fact is, practitioners in the
>profession are frequently called on to be to-the-point in
>documentation.  I guess I appreciate that philosophy all the more when
>put into the position of the reader.
>

   (snipped)

I think you are right again.  You listed four schemes 
to reduce the computations needed by traditional 
nonrecursive (direct-convolution) FIR filters.
I've encountered more like ten different schemes 
in the DSP literature proposed for this kind of 
computational reduction.  To compare all of those 
different computational reduction methods would 
be a big (no, actually HUGE) job.

Fred, maybe you could tackle that job of 
making a computational comparison between all 
these various methods.
It would certainly be a meaningful contribution 
to the DSP literature of FIR filter design, and 
be (as you say) "to-the-point".

My guess is that you'd have to quit your job, 
leave your family, and live in a monastery 
for 1-2 years to finish the job.  :-)

[-Rick-]

 

Fred,

For FPGA application, I typically use a partially transposed form, which permits
you to put the adders in a linear chain rather than a tree.  The adders are all
registered that way, and the adder latency is absorbed by the filter delays.
Partially transposed means you put any remaining delay on the input side (this is
useful for filters where you have more than one clock per sample, and specifically
for distributed arithmetic implementations).  The advantage of having some delay
on the input side in an FPGA is that it pipelines the distibution of the data to
the filter taps so that you don't have large fanouts (which will also kill
performance).

Fred Ma wrote:

> Kevin Neilson wrote:
> >
> > > I'm looking at two texts for basic info about why any one FIR
> > > structure would be preferable to another
> >
> > One advantage to the transpose form, when implemented in FPGAs or ASICs, is
> > that you can change all the coeffs at the same time and transition nicely.
> > I think that may be useful for equalizers.  It also has a structure that you
> > can put into preplaced modules that can be replicated depending on filter
> > length.  But other than that it's pretty much the same as the transversal.
>
> I was just mentioning in another response that the tranposed form has adders
> that are separated by delays, whereas the tranversal based structures have
> the adders forming (effectively) a tree.  Use of CSA for this would eliminate
> the need for high-speed adders for all but the final summation.  This is
> just speculation on my part, not based on any ASIC design experience.  I've
> also read that concern about high-speed adders is not as big a concern for
> FPGA implementations because of the built in circuitry (though of course, I
> imagine that an adder tree still needs pipelining between levels in the tree).
> Again, not based on design experience, just speculating based on
> textbook/web readings.
>
> Fred
> --
> Fred Ma, fma@doe.carleton.ca
> Dept. of Electronics, Carleton University, Ottawa, Ontario, Canada
> *|  If I don't reply to your email, please sent it again.  I may  |*
> *|  have erased along with the deluge of post-filter spam.        |*

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930     Fax 401/884-7950
email ray@andraka.com
http://www.andraka.com

 "They that give up essential liberty to obtain a little
  temporary safety deserve neither liberty nor safety."
                                          -Benjamin Franklin, 1759

Jerry Avins wrote:
> 
> With DSPs, folding saves nothing (the addition before the MAC uses as
> much time as the MAC that's saved, and the extra bookkeeping isn't
> trivial). If folding only doubles the execution time, I think you've
> coded well. It will certainly more than double the code size, but as
> that's small to start, no problem.
> 
> But it seems that your viewpoint is that of a hardware designer, so it
> may be none of that matters. Having figured out the preceding profound
> thought, any more I might add would waste your reading time.


Actually, it's interesting to know just how different are the considerations
in targeting DSP vs. hardware.  Thanks.

Fred

Rick Lyons wrote:
> 
> 
> Hi Fred,
>   I had trouble following your decsripition of
> "Cascade form".  Will you tell me what pages of
> Opp & Schafer and Proakis & Manlakis
> cover this "cascade form".  That would help me.

Hi, Rick,

I'm responding from home right now, but I can check
when I get onto campus tomorrow.  All 4 forms should
come one after another, in the FIR section, just
preceding the IIR section (Proakis & Manolakis).
> 
> >At first, I didn't see much reason to choose between cascade form and
> >frequency sampling, since the mapping between z-domain and w-domain
> >(omega domain) seemed pretty simple, at least at an intuitive level.
> >But in reviewing this many-year old material (for me), I see an
> >example showing the frequency sampling implementation taking fewer
> >resources.
> 
> Yes, you're right.  For some applications
> (depending on the desired filter's passband
> width, transition region width, and stopband
> attenuation) linear-phase Freq sampling filters
> can be more computationally efficient than
> Parks-McClellan-design nonrecursive FIR filters.
> I spent many months studying that issue.
> (That topic is in Chapter 7 of the 2nd edition
> of my DSP book.)

What book is that?

> >I think it would be helpful for texts to state up front
> >the motivation for the different structures.  It sounds like a
> >complaint (and it is!) but the fact is, practitioners in the
> >profession are frequently called on to be to-the-point in
> >documentation.  I guess I appreciate that philosophy all the more when
> >put into the position of the reader.
> >
> 
>    (snipped)
> 
> I think you are right again.  You listed four schemes
> to reduce the computations needed by traditional
> nonrecursive (direct-convolution) FIR filters.
> I've encountered more like ten different schemes
> in the DSP literature proposed for this kind of
> computational reduction.  To compare all of those
> different computational reduction methods would
> be a big (no, actually HUGE) job.
> 
> Fred, maybe you could tackle that job of
> making a computational comparison between all
> these various methods.
> It would certainly be a meaningful contribution
> to the DSP literature of FIR filter design, and
> be (as you say) "to-the-point".
> 
> My guess is that you'd have to quit your job,
> leave your family, and live in a monastery
> for 1-2 years to finish the job.  :-)

The writing of books should be the task of experts in the field
(should they take up the challenge), which I am certainly not.  But
the same kind of criticism can rightfully be expected of any author,
regardless of whether the document is intended for a public audience.

"To-the-point" is how I described the manner in which we are called
upon to communicate professionally.  However, the specific comment I
had about this section of the textbook was a lack of general
motivation for the different structures.  It doesn't have to be a
detailed comparitive study of all possible structures.  It can be as
simple as the comment about the the suitability of lattice structure
for speech processing (though I personally would have preferred a few
more words about the specific attributes that make it so).
Engineering is about utility, and a minor addition of such context
would make the material more than just a catalogue of varied
mathematical representations.

I actually like the book by Proakis et al (I can understand it, which
is a big plus).  But the fact remains; it still lacks commentary on
the motivation for the different FIR structures.  That is a natural
question for readers who don't already know the area.  In fact, it is
a natural question for readers of any material that introduces new
methods, ideas, or representations, especially if they are given as a
series of alternatives.

Fred