"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