Clarification of Rivlin-Shapiro theorem for FIR filters

Started by Robert Rozman December 28, 2004
Hi,

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

It says in [1] 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.


[1] ...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 
news:mBnAd.7525$F6.1303658@news.siol.net...
> Hi, > > I have problems applying Rivlin Shapiro's theorem for design of FIR > filters. > > It says in [1] 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. > > > [1] ...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 [1] 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 > news:mBnAd.7525$F6.1303658@news.siol.net... > > Hi, > > > > I have problems applying Rivlin Shapiro's theorem for design of FIR > > filters. > > > > It says in [1] 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. > > > > > > [1] ...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 [1] 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 [1] ? Are those points zeros of error function ? Thanks in advance, 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 > > news:mBnAd.7525$F6.1303658@news.siol.net... > > > Hi, > > > > > > I have problems applying Rivlin Shapiro's theorem for design of FIR > > > filters. > > > > > > It says in [1] 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. > > > > > > > > > [1] ...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 [1] 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 > [1] ? > Are those points zeros of error function ? > > Thanks in advance, > > 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 [1] 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 >> [1] ? >> 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