Hi, friends!

  Is there any good method for "Polynomial Decomposition" being used in 
Filter Design?
For example, if I use Park-McClellan algorithm designing a 10-order FIR 
filter,then want to decompose the polynomial into five 2-order filters, and 
keep the overall magnitude response.
  Does anyone has good suggestion or known some papers about this issue, 
please tell me.

On 30 Mai, 10:47, "Shen Zhi" <markk...@hotmail.com> wrote:
> Hi, friends!
>
> =A0 Is there any good method for "Polynomial Decomposition" being used in
> Filter Design?
> For example, if I use Park-McClellan algorithm designing a 10-order FIR
> filter,then want to decompose the polynomial into five 2-order filters, a=
nd
> keep the overall magnitude response.
> =A0 Does anyone has good suggestion or known some papers about this issue=
,
> please tell me.

Any reason, other than numerical accuracy issues [*], why you
can't try polynomial rooting?

Rune

[*] Numerical accuracy issues might well be severe enough to
    destroy your results, if the polynomial order is too high.

On 5/30/2010 4:47 AM, Shen Zhi wrote:
> Hi, friends!
>
>    Is there any good method for "Polynomial Decomposition" being used in
> Filter Design?
> For example, if I use Park-McClellan algorithm designing a 10-order FIR
> filter,then want to decompose the polynomial into five 2-order filters, and
> keep the overall magnitude response.
>    Does anyone has good suggestion or known some papers about this issue,
> please tell me.

Question: why do you want the roots? Aren't the coefficients that P-M 
gives you all you really need? (Some FIR filters can reasonably have 100 
taps. Would you still want to find the roots?)

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

Haha, Rune!
  I forget the roots of polynomial.
By the way, do you think any high order FIR filter could be decomposed into 
many low order filters by the roots?
If yes, is that means we doesn't need to implement a high order FIR filter 
but use many low order filters?

"Rune Allnor" <allnor@tele.ntnu.no> 
??????:d512d56c-f38d-40b0-948b-b95fd7cce808@32g2000prq.googlegroups.com...
On 30 Mai, 10:47, "Shen Zhi" <markk...@hotmail.com> wrote:
> Hi, friends!
>
> Is there any good method for "Polynomial Decomposition" being used in
> Filter Design?
> For example, if I use Park-McClellan algorithm designing a 10-order FIR
> filter,then want to decompose the polynomial into five 2-order filters, 
> and
> keep the overall magnitude response.
> Does anyone has good suggestion or known some papers about this issue,
> please tell me.

Any reason, other than numerical accuracy issues [*], why you
can't try polynomial rooting?

Rune

[*] Numerical accuracy issues might well be severe enough to
    destroy your results, if the polynomial order is too high. 

Hi, Jerry.
   I'm thinking of differents effections or different magnitude response 
errors, which comes from the limited wordlength quantiziton, between the 
single high-order FIR filter and several its decomposed lower FIR filters.

"Jerry Avins" <jya@ieee.org> ??????:EYpMn.82856$gv4.41042@newsfe09.iad...
> On 5/30/2010 4:47 AM, Shen Zhi wrote:
>> Hi, friends!
>>
>>    Is there any good method for "Polynomial Decomposition" being used in
>> Filter Design?
>> For example, if I use Park-McClellan algorithm designing a 10-order FIR
>> filter,then want to decompose the polynomial into five 2-order filters, 
>> and
>> keep the overall magnitude response.
>>    Does anyone has good suggestion or known some papers about this issue,
>> please tell me.
>
> Question: why do you want the roots? Aren't the coefficients that P-M 
> gives you all you really need? (Some FIR filters can reasonably have 100 
> taps. Would you still want to find the roots?)
>
> Jerry
> -- 
> Engineering is the art of making what you want from things you can get.
> ����������������������������������������������������������������������� 

On 5/30/2010 5:21 AM, Shen Zhi wrote:
> Haha, Rune!
>    I forget the roots of polynomial.
> By the way, do you think any high order FIR filter could be decomposed into
> many low order filters by the roots?
> If yes, is that means we doesn't need to implement a high order FIR filter
> but use many low order filters?

You could do that, but it would take longer to compute and probably be 
less accurate than a single tapped delay line.

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

I think only few real roots could be decomposed from the original polynomial 
to implement a low-order filters, and most of the rest are complex roots.

"Shen Zhi" <markkknd@hotmail.com> д����Ϣ����:httanl$k43$1@www.shinco.com...
> Haha, Rune!
>  I forget the roots of polynomial.
> By the way, do you think any high order FIR filter could be decomposed 
> into many low order filters by the roots?
> If yes, is that means we doesn't need to implement a high order FIR filter 
> but use many low order filters?
>
> "Rune Allnor" <allnor@tele.ntnu.no> 
> ??????:d512d56c-f38d-40b0-948b-b95fd7cce808@32g2000prq.googlegroups.com...
> On 30 Mai, 10:47, "Shen Zhi" <markk...@hotmail.com> wrote:
>> Hi, friends!
>>
>> Is there any good method for "Polynomial Decomposition" being used in
>> Filter Design?
>> For example, if I use Park-McClellan algorithm designing a 10-order FIR
>> filter,then want to decompose the polynomial into five 2-order filters, 
>> and
>> keep the overall magnitude response.
>> Does anyone has good suggestion or known some papers about this issue,
>> please tell me.
>
> Any reason, other than numerical accuracy issues [*], why you
> can't try polynomial rooting?
>
> Rune
>
> [*] Numerical accuracy issues might well be severe enough to
>    destroy your results, if the polynomial order is too high.
> 

On 5/30/2010 5:29 AM, Shen Zhi wrote:
> Hi, Jerry.
>     I'm thinking of differents effections or different magnitude response
> errors, which comes from the limited wordlength quantiziton, between the
> single high-order FIR filter and several its decomposed lower FIR filters.

I don't see the improvement in accuracy or stability that factoring 
gives in IIRs. In a single tapped delay line, each element is multiplied 
by a coefficient and added to an accumulator. The outputs of cascaded 
smaller filters need to be multiplied together. Why do you believe that 
the product of many terms, each of which needs to ve calculated 
separately, might be more accurate than a sum of terms closer to the raw 
data?

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

On 5/30/2010 5:43 AM, Shen Zhi wrote:
> I think only few real roots could be decomposed from the original polynomial
> to implement a low-order filters, and most of the rest are complex roots.

Of course.

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

A factor that the high-order FIR filter coefficients dynamic range is quite 
large.
For example, its center coefficient may be 0.5~1, but the most outside (or 
the smallest) coefficient may be 0.00...001. That means in fix-point system, 
the wordlength to be used must be long, or the small coefficient will be 
quantized to zero.
So I'm thinking whether the discussion in 'coefficient dynamic range' also 
has contribution to improve the FIR filter design.


"Jerry Avins" <jya@ieee.org> ??????:BtqMn.82969$gv4.62139@newsfe09.iad...
> On 5/30/2010 5:29 AM, Shen Zhi wrote:
>> Hi, Jerry.
>>     I'm thinking of differents effections or different magnitude response
>> errors, which comes from the limited wordlength quantiziton, between the
>> single high-order FIR filter and several its decomposed lower FIR 
>> filters.
>
> I don't see the improvement in accuracy or stability that factoring gives 
> in IIRs. In a single tapped delay line, each element is multiplied by a 
> coefficient and added to an accumulator. The outputs of cascaded smaller 
> filters need to be multiplied together. Why do you believe that the 
> product of many terms, each of which needs to ve calculated separately, 
> might be more accurate than a sum of terms closer to the raw data?
>
> Jerry
> -- 
> Engineering is the art of making what you want from things you can get.
> ����������������������������������������������������������������������� 

On 5/30/2010 5:57 AM, Shen Zhi wrote:
> A factor that the high-order FIR filter coefficients dynamic range is quite
> large.
> For example, its center coefficient may be 0.5~1, but the most outside (or
> the smallest) coefficient may be 0.00...001. That means in fix-point system,
> the wordlength to be used must be long, or the small coefficient will be
> quantized to zero.
> So I'm thinking whether the discussion in 'coefficient dynamic range' also
> has contribution to improve the FIR filter design.

I don't see it, but I don't want to discourage you from seeking an 
improvement. If you find a way that is faster than the standard way with 
double precision, look into getting a patent. Keep in mind that very 
small coefficients have (individually) very small influence on the 
filter's output.

Here's a quick first-look suggestion: run two computations side by side. 
One with the larger coefficients and the smaller ones set to zero. The 
other with the smaller coefficients scaled up by some power of two and 
the larger ones set to zero. The accumulation of all the smaller 
coefficients together might carry useful information. Scale it back (by 
shifting) and add it to result of the first calculation. This might be 
faster than one double-precision pass because it is done with the native 
MAC instruction.

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

On 5/30/2010 10:54 AM, Jerry Avins wrote:

   ...

> Here's a quick first-look suggestion:

What followed is a bit unclear. This is a revision:

Run two computations side by side. One, with the smaller coefficients 
set to zero. The other, with the smaller coefficients scaled up by some 
power of two and the larger ones set to zero. The accumulation of all 
the smaller coefficients together might carry useful information. Scale 
it back (by shifting) and add it to result of the first calculation. 
This might be faster than one double-precision pass because it is done 
with the native MAC instruction.

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

Shen Zhi <markkknd@hotmail.com> wrote:

> A factor that the high-order FIR filter coefficients dynamic
> range is quite large.  For example, its center coefficient may
> be 0.5~1, but the most outside (or the smallest) coefficient may
> be 0.00...001. That means in fix-point system, the wordlength to
> be used must be long, or the small coefficient will be quantized
> to zero.

This is true but long word-widths are no longer the headache
they once were.  It is reasonable these days to have ~40 bits
of accuracy in an accumulator.  At the end of the computation,
it can be rounded/saturated down to a smaller width.

> So I'm thinking whether the discussion in 'coefficient dynamic 
> range' also has contribution to improve the FIR filter design.

To reduce the neccessary coefficient precision, consider using a 
lattice architecture, not a cascaded architecture (because a few of
the cascades tend to still require a lot coefficient precision).


Steve

On 30 Mai, 17:38, spop...@speedymail.org (Steve Pope) wrote:

> > So I'm thinking whether the discussion in 'coefficient dynamic
> > range' also has contribution to improve the FIR filter design.
>
> To reduce the neccessary coefficient precision, consider using a
> lattice architecture,

Does that work unconditionally? I know it works for FIRs
with all its zeros inside the unit circle, but the general
case FIR might also have zeros outside. Will the lattice
be stable for that case?

Rune

Rune Allnor  <allnor@tele.ntnu.no> wrote:

>On 30 Mai, 17:38, spop...@speedymail.org (Steve Pope) wrote:

>> To reduce the neccessary coefficient precision, consider using a
>> lattice architecture,

>Does that work unconditionally? I know it works for FIRs
>with all its zeros inside the unit circle, but the general
>case FIR might also have zeros outside. Will the lattice
>be stable for that case?

Good question.  If an FIR is the inverse filter of a stable IIR,
then the lattice coefficients will all have absolute value 
less than one, and will generally be less sensitive to precision
errors than other filter forms.

If it is an arbitrary FIR, it will still be stable but I am
unsure if the coefficient precision advantages still hold.
I have never used such a filter.

Steve

On May 30, 2:57=A0am, "Shen Zhi" <markk...@hotmail.com> wrote:
> A factor that the high-order FIR filter coefficients dynamic range is qui=
te
> large.
> For example, its center coefficient may be 0.5~1, but the most outside (o=
r
> the smallest) coefficient may be 0.00...001. That means in fix-point syst=
em,
> the wordlength to be used must be long, or the small coefficient will be
> quantized to zero.
> So I'm thinking whether the discussion in 'coefficient dynamic range' als=
o
> has contribution to improve the FIR filter design.
> ...

The sensitivity of the output of a direct form-I FIR filter to
quantization errors in the coefficients is the same for all
coefficients. This sensitivity is not a function of the coefficient
nominal value. The same word length is appropriate for all
coefficients.

Dale B. Dalrymple

On 5/30/2010 2:09 PM, dbd wrote:
> On May 30, 2:57 am, "Shen Zhi"<markk...@hotmail.com>  wrote:
>> A factor that the high-order FIR filter coefficients dynamic range is quite
>> large.
>> For example, its center coefficient may be 0.5~1, but the most outside (or
>> the smallest) coefficient may be 0.00...001. That means in fix-point system,
>> the wordlength to be used must be long, or the small coefficient will be
>> quantized to zero.
>> So I'm thinking whether the discussion in 'coefficient dynamic range' also
>> has contribution to improve the FIR filter design.
>> ...
>
> The sensitivity of the output of a direct form-I FIR filter to
> quantization errors in the coefficients is the same for all
> coefficients. This sensitivity is not a function of the coefficient
> nominal value. The same word length is appropriate for all
> coefficients.

A remarkable result, all the more for its being obvious once stated.

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

Hi, Steve
    I just read some materials about Lattice architecture.
What its benefit is,compared to direct form?
I found it doubles the Multipliers and the Adders, but what we get?

"Steve Pope" <spope33@speedymail.org> д����Ϣ����:htu0q1$98o$2@blue.rahul.net...
> Shen Zhi <markkknd@hotmail.com> wrote:
>
>> A factor that the high-order FIR filter coefficients dynamic
>> range is quite large.  For example, its center coefficient may
>> be 0.5~1, but the most outside (or the smallest) coefficient may
>> be 0.00...001. That means in fix-point system, the wordlength to
>> be used must be long, or the small coefficient will be quantized
>> to zero.
>
> This is true but long word-widths are no longer the headache
> they once were.  It is reasonable these days to have ~40 bits
> of accuracy in an accumulator.  At the end of the computation,
> it can be rounded/saturated down to a smaller width.
>
>> So I'm thinking whether the discussion in 'coefficient dynamic
>> range' also has contribution to improve the FIR filter design.
>
> To reduce the neccessary coefficient precision, consider using a
> lattice architecture, not a cascaded architecture (because a few of
> the cascades tend to still require a lot coefficient precision).
>
>
> Steve 

Zhi.Shen <zhi.m.shen@gmail.com> wrote:

>I just read some materials about Lattice architecture.
>What its benefit is,compared to direct form?
>I found it doubles the Multipliers and the Adders, but what we get?

It doubles the number of multiply/adds but often the coefficients
can be lower precision.

Also, unrelated to your question, it can lead to a more stable
IIR filter.

It may not be appropriate for all filters, but if you're
having problems with coefficient precision it may be worth
checking into.

Steve

Hi, Steve

In some DSP books, it always be described to be used in Nonlinear phase FIR 
filter,
why few of them are about linear phase FIR filter?

"Steve Pope" <spope33@speedymail.org> д����Ϣ����:htvd61$o5v$1@blue.rahul.net...
> Zhi.Shen <zhi.m.shen@gmail.com> wrote:
>
>>I just read some materials about Lattice architecture.
>>What its benefit is,compared to direct form?
>>I found it doubles the Multipliers and the Adders, but what we get?
>
> It doubles the number of multiply/adds but often the coefficients
> can be lower precision.
>
> Also, unrelated to your question, it can lead to a more stable
> IIR filter.
>
> It may not be appropriate for all filters, but if you're
> having problems with coefficient precision it may be worth
> checking into.
>
> Steve 

Zhi.Shen <zhi.m.shen@gmail.com> writes,

>Hi, Steve

>In some DSP books, it always be described to be used in Nonlinear phase FIR 
>filter,
>why few of them are about linear phase FIR filter?

>"Steve Pope" <spope33@speedymail.org>

>> Zhi.Shen <zhi.m.shen@gmail.com> wrote:

>>>I just read some materials about Lattice architecture.
>>>What its benefit is,compared to direct form?

>> It doubles the number of multiply/adds but often the coefficients
>> can be lower precision.
>>
>> Also, unrelated to your question, it can lead to a more stable
>> IIR filter.

>> It may not be appropriate for all filters, but if you're
>> having problems with coefficient precision it may be worth
>> checking into.

Excellent question.  

I would tend to say this is because the types of real-world
systems for which an all-pole lattice filter naturally
falls out as an appropriate model (such as, the human
vocal tract) do not have linear-phase inverse filter functions.

That's about all the insight I can add here.


Steve

Thank you, Steve
  I have just found a paper about linear lattice FIR filter:

Title: Linear phase FIR-filter in lattice structure
Author: Schwarz, K.
Source: Circuits and Systems, 1993., ISCAS '93, 1993 IEEE International 
Symposium on, 1993, 347-350

   But I have no idea why so few papers about this issue.


"Steve Pope" <spope33@speedymail.org> д����Ϣ����:htvm4k$vi3$1@blue.rahul.net...
> Zhi.Shen <zhi.m.shen@gmail.com> writes,
>
>>Hi, Steve
>
>>In some DSP books, it always be described to be used in Nonlinear phase 
>>FIR
>>filter,
>>why few of them are about linear phase FIR filter?
>
>>"Steve Pope" <spope33@speedymail.org>
>
>>> Zhi.Shen <zhi.m.shen@gmail.com> wrote:
>
>>>>I just read some materials about Lattice architecture.
>>>>What its benefit is,compared to direct form?
>
>>> It doubles the number of multiply/adds but often the coefficients
>>> can be lower precision.
>>>
>>> Also, unrelated to your question, it can lead to a more stable
>>> IIR filter.
>
>>> It may not be appropriate for all filters, but if you're
>>> having problems with coefficient precision it may be worth
>>> checking into.
>
> Excellent question.
>
> I would tend to say this is because the types of real-world
> systems for which an all-pole lattice filter naturally
> falls out as an appropriate model (such as, the human
> vocal tract) do not have linear-phase inverse filter functions.
>
> That's about all the insight I can add here.
>
>
> Steve 

On May 31, 12:41=A0am, "Zhi.Shen" <zhi.m.s...@gmail.com> wrote:
> ...
> =A0 I have just found a paper about linear lattice FIR filter:
>
> Title: Linear phase FIR-filter in lattice structure
> Author: Schwarz, K.
> Source: Circuits and Systems, 1993., ISCAS '93, 1993 IEEE International
> Symposium on, 1993, 347-350
>
> =A0 =A0But I have no idea why so few papers about this issue.
> ...

Google on:
fir coefficient sensitivity
gives 594,000 hits

Google on:
linear phase fir filter lattice
gives 19,000 hits

Even if there is only 1 paper per 1000 Google hits, there are plenty
of papers. The problem is to specify a narrower view of what you are
seeking,and to be willing to scan the first hundred hits rather than
just the first page.

Dale B. Dalrymple

In article <d512d56c-f38d-40b0-948b-b95fd7cce808@32g2000prq.googlegroups.com>, 
allnor@tele.ntnu.no says...
>
>
>On 30 Mai, 10:47, "Shen Zhi" <markk...@hotmail.com> wrote:
>> Hi, friends!
>>
>> � Is there any good method for "Polynomial Decomposition" being used in
>> Filter Design?
>> For example, if I use Park-McClellan algorithm designing a 10-order FIR
>> filter,then want to decompose the polynomial into five 2-order filters, and
>> keep the overall magnitude response.
>> � Does anyone has good suggestion or known some papers about this issue,
>> please tell me.
>
>Any reason, other than numerical accuracy issues [*], why you
>can't try polynomial rooting?

There are ways to get the roots of the very high-order polynomials (orders 
higher than 100) applicable to this specific problem. This might help:

Stathaki, T.  Fotinopoulos, I., "Equiripple minimum phase FIR filter design 
from linear phase systems using root moments" 

http://www.ee.bilkent.edu.tr/~signal/Nsip99/papers/20.pdf

See also

http://cnx.org/content/m15573/latest/

for the Lindsey-Fox algorithm for factoring polynomials