Clarification of Rivlin-Shapiro theorem for FIR filters

Started by December 28, 2004
```Hi,

I have problems applying Rivlin Shapiro's theorem for design of FIR filters.

It says in  that :

H(z) is best Chebyshev approximation to D(z) if and only if there are r
points z1,z2,....zr and r positive numbers lambda1, lambda2, ...
lambdas sum to 1 ... for which :

sum(k=1 to r)   lambdak [D(zk)-H(zk)] fi(zk) = 0   for i=1,2,....,N

.....

Main question is what are functions fi (i=1,....,N)?   Theorem is general
and refers to them as "fixed, given functions in C(Z)" ...    I guess if I
apply theorem to design of FIR filters, then functions fi get explicit
definition  - do they ?

regards,

Rob.

 ...X. Chen and T. W. Parks, "Design of FIR filters in the Complex
Domain," IEEE Trans. on Signal Processing, vol. ASSP-35, no. 2, pp. 144-153,
February 1987.

```
```"Robert Rozman" <rozman@fri.uni-lj.si> wrote in message
> Hi,
>
> I have problems applying Rivlin Shapiro's theorem for design of FIR
> filters.
>
> It says in  that :
>
> H(z) is best Chebyshev approximation to D(z) if and only if there are r
> points z1,z2,....zr and r positive numbers lambda1, lambda2, ...
> lambdas sum to 1 ... for which :
>
> sum(k=1 to r)   lambdak [D(zk)-H(zk)] fi(zk) = 0   for i=1,2,....,N
>
> .....
>
> Main question is what are functions fi (i=1,....,N)?   Theorem is general
> and refers to them as "fixed, given functions in C(Z)" ...    I guess if I
> apply theorem to design of FIR filters, then functions fi get explicit
> definition  - do they ?
>
>
>
> regards,
>
> Rob.
>
>
>  ...X. Chen and T. W. Parks, "Design of FIR filters in the Complex
> Domain," IEEE Trans. on Signal Processing, vol. ASSP-35, no. 2, pp.
> 144-153,
> February 1987.

Equation 1.4 in  seems to state it pretty clearly.  The fi are the basis
functions - that set of functions that you will use to build the
approximating function as a linear combination or sum.

So, they could be sinusoids or something else.  Most usually sinusoids.
Sometimes sincs.

The expression you give from Rivlin and Shapiro is addressing the zeros in
the error or difference between the desired function D and the approximating
function H.

Also see Karan & McClellan:
www.eas.asu.edu/~karam/papers/itcas95.ps

Fred

```
```Hi,

thanks for informations. Please see below...
"Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message
news:7NydnZNXiajmek_cRVn-tA@centurytel.net...
>
> "Robert Rozman" <rozman@fri.uni-lj.si> wrote in message
> > Hi,
> >
> > I have problems applying Rivlin Shapiro's theorem for design of FIR
> > filters.
> >
> > It says in  that :
> >
> > H(z) is best Chebyshev approximation to D(z) if and only if there are r
> > points z1,z2,....zr and r positive numbers lambda1, lambda2, ...
> > lambdas sum to 1 ... for which :
> >
> > sum(k=1 to r)   lambdak [D(zk)-H(zk)] fi(zk) = 0   for i=1,2,....,N
> >
> > .....
> >
> > Main question is what are functions fi (i=1,....,N)?   Theorem is
general
> > and refers to them as "fixed, given functions in C(Z)" ...    I guess if
I
> > apply theorem to design of FIR filters, then functions fi get explicit
> > definition  - do they ?
> >
> >
> >
> > regards,
> >
> > Rob.
> >
> >
> >  ...X. Chen and T. W. Parks, "Design of FIR filters in the Complex
> > Domain," IEEE Trans. on Signal Processing, vol. ASSP-35, no. 2, pp.
> > 144-153,
> > February 1987.
>
> Equation 1.4 in  seems to state it pretty clearly.  The fi are the
basis
> functions - that set of functions that you will use to build the
> approximating function as a linear combination or sum.

So. does this mean that in case of FIR filters those basis functions come
from frequency response definition of FIR filter ?

H(ejw)=sum h(n) exp(-jwn)   and latter exponentials are basis functions ?

>
> So, they could be sinusoids or something else.  Most usually sinusoids.
> Sometimes sincs.
>
> The expression you give from Rivlin and Shapiro is addressing the zeros in
> the error or difference between the desired function D and the
approximating
> function H.

What would be basic, two sentence meaning explanation for Equation 2.2 in
 ?
Are those points zeros of error function ?

regards,

Robert.

>
> Also see Karan & McClellan:
> www.eas.asu.edu/~karam/papers/itcas95.ps
>
> Fred
>
>

```
```Sorry meant equation 2.3  or basic equation for Rivlin Shapiro theorem...

Regards,

Robert.

"Robert Rozman" <rozman@fri.uni-lj.si> wrote in message
news:zLHBd.7675\$F6.1333293@news.siol.net...
> Hi,
>
> thanks for informations. Please see below...
> "Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message
> news:7NydnZNXiajmek_cRVn-tA@centurytel.net...
> >
> > "Robert Rozman" <rozman@fri.uni-lj.si> wrote in message
> > > Hi,
> > >
> > > I have problems applying Rivlin Shapiro's theorem for design of FIR
> > > filters.
> > >
> > > It says in  that :
> > >
> > > H(z) is best Chebyshev approximation to D(z) if and only if there are
r
> > > points z1,z2,....zr and r positive numbers lambda1, lambda2, ...
> > > lambdas sum to 1 ... for which :
> > >
> > > sum(k=1 to r)   lambdak [D(zk)-H(zk)] fi(zk) = 0   for i=1,2,....,N
> > >
> > > .....
> > >
> > > Main question is what are functions fi (i=1,....,N)?   Theorem is
> general
> > > and refers to them as "fixed, given functions in C(Z)" ...    I guess
if
> I
> > > apply theorem to design of FIR filters, then functions fi get explicit
> > > definition  - do they ?
> > >
> > >
> > > Thanks in advance,
> > >
> > > regards,
> > >
> > > Rob.
> > >
> > >
> > >  ...X. Chen and T. W. Parks, "Design of FIR filters in the Complex
> > > Domain," IEEE Trans. on Signal Processing, vol. ASSP-35, no. 2, pp.
> > > 144-153,
> > > February 1987.
> >
> > Equation 1.4 in  seems to state it pretty clearly.  The fi are the
> basis
> > functions - that set of functions that you will use to build the
> > approximating function as a linear combination or sum.
>
> So. does this mean that in case of FIR filters those basis functions come
> from frequency response definition of FIR filter ?
>
>    H(ejw)=sum h(n) exp(-jwn)   and latter exponentials are basis functions
?
>
> >
> > So, they could be sinusoids or something else.  Most usually sinusoids.
> > Sometimes sincs.
> >
> > The expression you give from Rivlin and Shapiro is addressing the zeros
in
> > the error or difference between the desired function D and the
> approximating
> > function H.
>
> What would be basic, two sentence meaning explanation for Equation 2.2 in
>  ?
> Are those points zeros of error function ?
>
>
> regards,
>
> Robert.
>
>
> >
> > Also see Karan & McClellan:
> > www.eas.asu.edu/~karam/papers/itcas95.ps
> >
> > Fred
> >
> >
>
>

```
```"Robert Rozman" <rozman@fri.uni-lj.si> wrote in message
news:QMHBd.7676\$F6.1333236@news.siol.net...
> Sorry meant equation 2.3  or basic equation for Rivlin Shapiro theorem...
>
>> > >
>> > > sum(k=1 to r)   lambdak [D(zk)-H(zk)] fi(zk) = 0   for i=1,2,....,N
>> > >
>> > > .....
>> > >
Fred said:
>> >
>> > Equation 1.4 in  seems to state it pretty clearly.  The fi are the
>> basis
>> > functions - that set of functions that you will use to build the
>> > approximating function as a linear combination or sum.
>>
Rob said:
>> So. does this mean that in case of FIR filters those basis functions come
>> from frequency response definition of FIR filter ?
>>
>>    H(ejw)=sum h(n) exp(-jwn)   and latter exponentials are basis
>> functions

***Yes

>> >
>> > So, they could be sinusoids or something else.  Most usually sinusoids.
>> > Sometimes sincs.
>> >
>> > The expression you give from Rivlin and Shapiro is addressing the zeros
> in
>> > the error or difference between the desired function D and the
>> approximating
>> > function H.
>>
Rob said:

>> What would be basic, two sentence meaning explanation for Equation 2.3 in
>>  ?
>> Are those points zeros of error function ?

Well, it appears I erred saying that it was about the zeros of the error -
which is often of interest.  I'm now thinking that the expression is a
generalization of the familiar sign alternation property for real FIR
filters: "the signs of the peak errors have to alternate" and, a modified
form, "the signs fo the peak errors alternate unless there are equality
constraints on the approimant - in which case each equality "uses up" one of
the alternating signs" e.g.
+1, -1, +1, -1 etc.  or +1, -1, 0, -1, +1 etc. ....

I don't know that a sentence of words is better than an expression in
algebra.  It is likely not as precise.  But one can sometimes "expand" an
algebraic expression into words.  So, here is Equation 2.3 in words to the
best of my ability:

Frome above note:
sum(k=1 to r)   lambdak [D(zk)-H(zk)] fi(zk) = 0   for i=1,2,....,N

Also note that sum(k=1 to r)   lambdak = 1.0
Also note that r<=2N+1
Also note that the zk are the *extremal frequencies* - where the peaks of
the error, (D-H) occur.

OK, here goes.....
We establish an approximant H to the desired function D.
H is a linear sum of a selected set of N basis functions:
H(z)=sum(n=0,N-1) h(n)z^-n
where the h(n) are the constant coefficients making up the approximant out
of the z^-n basis functions.

Generally, D(z) is defined on the unit circle.
The error of approximation is computed:

Error=D(z)-H(z) ... so if D(z) is defined on the unit circle, the Error is
defined on the unit circle.

The objective criterion for a Chebyshev approximation is to:
minimize the maximum of the Error
(I will leave out the use of a weighting function W just to keep things
simple here.  An unweighted approximation will have all of the errors of
equal magnitude).

When one reaches the best, unique approximation, it will have certain
properties:
If the filter is real, then there is a property:
"the signs of the error peaks must alternate"
and this property is generally used in constructing iterative algorithms
that find the solution.
Note that a filter with odd N will have at least N+1 peaks in the error.
If there are N+1 (an even number) peaks in the error of alternating sign,
then it can be said:
sum(n=0,N=1) Error(n)=0
or
sum(n=0,N+1) g(n)*Error(n)=0 ; g(n)=1 for all n
because the peaks are equal and of alternating sign.
If there are N+2 (an odd number) peaks in the error of alternating sign,
then it's more complicated:
sum(n=0,N+2) g(n)*Error(n)=0.
Because the peak errors are equal and alternating in sign, with an odd
number of peaks, the peaks at the ends of the sequence of peaks have the
same sign.  So, we could have:
g(0)=0.5, g(N+2)=0.5 and g(1:N+1)=1.
We note that the g(n) are all positive and add up to N+2 in the first case
and add up to N+2 in the second case also.  A small matter of scaling the
g(n) by dividing by N+2 would make sum(n=0,N+1or2)=1.0
Look familiar?

If the filter isn't real, then what is an analogous property?  I think it is
Equation 2.3.  Take a look at it:
sum(k=1 to r)   lambdak [D(zk)-H(zk)] fi(zk) = 0   for i=1,2,....,N

using the notation above:

sum(n=1 to r)   g(n) [D(zn)-H(zn)] fi(zn) = 0   for i=1,2,....,N
where, in a simple case perhaps, g(n)=1/r

Here the sum is over all the extremal points - so that is the same.
Assuming that D-Z is complex (and defined on the unit circle) then it
appears that either the errors will match up in complex conjugate pairs or
the basis functions will do something similar to get a zero sum.

I am a bit confused by the appearance of fi(zn) in 2.3.  I hate to suggest
there could be an error in the paper!  But it seems out of place.  Consider:
H(z)= sum(k=1:N) h(k)fk(z)
so
H(zn)= sum(k=1:N) h(k)fk(zn)
so
sum(n=1 to r)   g(n) [D(zn)-sum(k=1:N) h(k)fk(zn)] fi(zn) = 0   for
i=1,2,....,N
sum(n=1 to r)   g(n) [fi(zn)D(zn)-fi(zn)sum(k=1:N) h(k)fk(zn)]  = 0   for
i=1,2,....,N
sum(n=1 to r)   g(n) [fi(zn)D(zn)-sum(k=1:N) h(k)*fk(zn)*fi(zn)]  = 0   for
i=1,2,....,N
and that makes little sense to me due to the product of basis functions in
there....

I hope this helps a little.

Fred

```