COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### Polynomial Decomposition in Filter Design

• Follow

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

```
 0

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

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

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

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.
�����������������������������������������������������������������������
```
 0

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

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.

```
 0

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

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

```
 0

```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.
�����������������������������������������������������������������������
```
 0

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

```
 0

```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.
�����������������������������������������������������������������������
```
 0

```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.
�����������������������������������������������������������������������
```
 0

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

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

```
 0

```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.
�����������������������������������������������������������������������
```
 0

```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.
�����������������������������������������������������������������������
```
 0

```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
```
 0

```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
```
 0

```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
```
 0

```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
```
 0

```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.
�����������������������������������������������������������������������
```
 0

```Hi, Steve
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

```
 0

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

>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
```
 0

```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:
>
>>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

```
 0

```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:

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

Steve
```
 0

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

"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:
>
>>>>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.
>
>
>
> Steve

```
 0

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

fir coefficient sensitivity
gives 594,000 hits

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
```
 0

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

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

for the Lindsey-Fox algorithm for factoring polynomials

```
 0
Reply spambucket2413 (15) 6/17/2010 2:30:52 AM

23 Replies
197 Views