FIR design with zeroes

I have a problem. I need to design a FIR with a certain fraction of
the taps being zero. Can anyone point me to references that are
generalizations to PArks-McLellan or others that do this?

Thank-you

Randy

"R Potter" <rpotter1@socal.rr.com> wrote in message 
news:35cu221dkcb5rof07ro2a4o6rmj687ggkr@4ax.com...
>I have a problem. I need to design a FIR with a certain fraction of
> the taps being zero. Can anyone point me to references that are
> generalizations to PArks-McLellan or others that do this?
>
> Thank-you
>
> Randy

Since I don't really know what you want to accomplish it's not so easy to 
answer the question but here are some ideas:

A symmetrical FIR filter is by far the easiest to deal with - so the zeros 
are symmetrical.
Now, if you arbitrarily center a FIR filter at zero time then a symmetrical 
FIR filter's frequency response is made up entirely of cosines in frequency 
because the frequency response is real and even and/or because there are 
pairs of coefficients equally distanced above and below zero that are equal. 
Such a pair of coefficients transforms to a cosine in frequency.

So, to get a pair of zeros in the filter temporal response all you need to 
do is leave out one of the cosines in the optimization program that 
calculates the best filter (in frequency).  Either that or fix the 
coefficient of the cosine to zero - same thing.

A halfband filter is a special case of this where all the even ordered 
cosines are zero - so every even-ordered pair of coefficients is zero 
(except the zeroeth one).

There are a number of tricks developed for halfband filters.  They are 
special lowpass filters with odd length and with those zero coefficients.
Notice that if you remove the zeroeth coefficient then you have an 
even-length filter with double the sampling interval.
One trick is to design a filter with half the sampling interval / double the 
sample rate / that is 0.5 at dc, 0 at fs/2 (it will be -0.5 at fs.  The 
filter response looks like a "square wave" in frequency - repeating in 
amplitude at fs and repeating in amplitude and sign at 2fs.
Then, increase the sample rate by a factor of 2 and add a coefficient = 0.5 
at time zero.
Adding this coefficient adds a "dc shift" to the frequency response so it's 
1.0 at f=0 and zero at the new fs/2 (the old fs).
You can do the whole thing with Parks-McClellan with the following specs:

2 bands
edges: 0,0.4,0.5,0.5
responses 1.0, 0.
weights 1,1
note that the stopband has zero width!

Some programs, maybe Meteor, will do time/frequency optimization at the same 
time.  So, perhaps you could force zeros in time while getting the best 
frequency response otherwise.

If you have a general requirement that's different, then I might use a Remez 
algorithm with some of the sinousoidal basis functions removed.  Obviously 
it reduces the number of degrees of freedom over what you'd have if none of 
the coefficients were going to be zero.

Fred

"Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message 
news:iL6dnfyj68H8qrLZRVn-ug@centurytel.net...
>
> "R Potter" <rpotter1@socal.rr.com> wrote in message 
> news:35cu221dkcb5rof07ro2a4o6rmj687ggkr@4ax.com...
>>I have a problem. I need to design a FIR with a certain fraction of
>> the taps being zero. Can anyone point me to references that are
>> generalizations to PArks-McLellan or others that do this?
>>
>> Thank-you
>>
>> Randy
>
> Since I don't really know what you want to accomplish it's not so easy to 
> answer the question but here are some ideas:
>
> A symmetrical FIR filter is by far the easiest to deal with - so the zeros 
> are symmetrical.
> Now, if you arbitrarily center a FIR filter at zero time then a 
> symmetrical FIR filter's frequency response is made up entirely of cosines 
> in frequency because the frequency response is real and even and/or 
> because there are pairs of coefficients equally distanced above and below 
> zero that are equal. Such a pair of coefficients transforms to a cosine in 
> frequency.
>
> So, to get a pair of zeros in the filter temporal response all you need to 
> do is leave out one of the cosines in the optimization program that 
> calculates the best filter (in frequency).  Either that or fix the 
> coefficient of the cosine to zero - same thing.
>
> A halfband filter is a special case of this where all the even ordered 
> cosines are zero - so every even-ordered pair of coefficients is zero 
> (except the zeroeth one).
>
> There are a number of tricks developed for halfband filters.  They are 
> special lowpass filters with odd length and with those zero coefficients.
> Notice that if you remove the zeroeth coefficient then you have an 
> even-length filter with double the sampling interval.
> One trick is to design a filter with half the sampling interval / double 
> the sample rate / that is 0.5 at dc, 0 at fs/2 (it will be -0.5 at fs. 
> The filter response looks like a "square wave" in frequency - repeating in 
> amplitude at fs and repeating in amplitude and sign at 2fs.
> Then, increase the sample rate by a factor of 2 and add a coefficient = 
> 0.5 at time zero.
> Adding this coefficient adds a "dc shift" to the frequency response so 
> it's 1.0 at f=0 and zero at the new fs/2 (the old fs).
> You can do the whole thing with Parks-McClellan with the following specs:
>
> 2 bands
> edges: 0,0.4,0.5,0.5
> responses 1.0, 0.
> weights 1,1
> note that the stopband has zero width!
>
> Some programs, maybe Meteor, will do time/frequency optimization at the 
> same time.  So, perhaps you could force zeros in time while getting the 
> best frequency response otherwise.
>
> If you have a general requirement that's different, then I might use a 
> Remez algorithm with some of the sinousoidal basis functions removed. 
> Obviously it reduces the number of degrees of freedom over what you'd have 
> if none of the coefficients were going to be zero.
>
> Fred

Here is a way that may be easier in terms of the tools you use:

1) Design a filter with the frequency response that you want.

2) Decide on one pair of the coefficients to remove - I suppose preferably a 
pair with small values.

3) Generate a new filter response criterion that has the corresponding 
cosine removed.  This should guarantee that the next solution will have a 
zero coefficient for that cosine.
(I guess you need a general Remez algorithm to do this so you have control 
over the entire objective function and not just "band" gain criteria).

The new filter will be optimum but with a pair of zero coefficients.  It 
will surely be different in terms of where the frequency error peaks occur 
because the number of degrees of freedom have effectively been reduced.  The 
ripple will go up.

4) Go to step 2 and repeat until you're satisfied.

You're not really limited to removing the cosines one at a time.  You could 
remove them all at once but this method seems to me to give you a better 
handle on what the changes do to the results.

Fred 

Fred Marshall wrote:
> "Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message
> news:iL6dnfyj68H8qrLZRVn-ug@centurytel.net...
> >
> > "R Potter" <rpotter1@socal.rr.com> wrote in message
> > news:35cu221dkcb5rof07ro2a4o6rmj687ggkr@4ax.com...
> >>I have a problem. I need to design a FIR with a certain fraction of
> >> the taps being zero. Can anyone point me to references that are
> >> generalizations to PArks-McLellan or others that do this?

...

> > So, to get a pair of zeros in the filter temporal response all you need to
> > do is leave out one of the cosines in the optimization program that
> > calculates the best filter (in frequency).  Either that or fix the
> > coefficient of the cosine to zero - same thing.
> >
...
> > If you have a general requirement that's different, then I might use a
> > Remez algorithm with some of the sinousoidal basis functions removed.
> > Obviously it reduces the number of degrees of freedom over what you'd have
> > if none of the coefficients were going to be zero.
...
>
> Here is a way that may be easier in terms of the tools you use:
>
> 1) Design a filter with the frequency response that you want.
>
> 2) Decide on one pair of the coefficients to remove - I suppose preferably a
> pair with small values.
>
> 3) Generate a new filter response criterion that has the corresponding
> cosine removed.  This should guarantee that the next solution will have a
> zero coefficient for that cosine.
> (I guess you need a general Remez algorithm to do this so you have control
> over the entire objective function and not just "band" gain criteria).

i understand how some particular coefficients of the Remez basis
functions can be set to zero and then just let Remez work on optimizing
with that.  but for Parks-McClellan, there is an additional problem:

for some numerical reason that i have never completely understood, the
P-McC algorithm does not use the cosines (that naturally map to the
linear-phase FIR coefficient pairs) as the basis functions but instead
maps the frequency variable (inc. the bandedge parameters and all of
the extrema) to x = cos(w) and then uses the basic remez exchange
algorithm to fit polynomials to that warped target definition, and when
it gets a result there, it uses expands the polynomial result into a
linear combination of Tchebyshev polynomials which can be readily
mapped back to the cosines and the FIR coef pairs.  i thought one
reason was that using Lagrange polynomial interpolation was, for some
reason, numerically superior than just solving a large set of linear
equations (using gaussian elimination) to get the coefficients to the
x^n terms and likewise better than fitting the cosines directly to the
target spec.  i still do not get why that is a problem when you have
double-precision, but for a large matrix, i guess it is.  ask Clay
Turner about it.

but the reason i am bringing it up is that i don't see how your kicking
out one of the cosines will give you a straight-forward constraint on
the polynomials.  if one was fitting the cosines to the target
directly, then, yes i can see how to do it.  but for a large number of
tap pairs, since the P-McC will be mapping that to power functions, i
don't see how to.  at least not offhand.

you know, i'll bet someone did an IEEE paper in Circuits and Systems or
ASSP (or the latter SP) transactions on this.

r b-j

robert bristow-johnson wrote:
>  if one was fitting the cosines to the target
> directly, then, yes i can see how to do it.  but for a large number of
> tap pairs, since the P-McC will be mapping that to power functions, i
> don't see how to.  at least not offhand.
>
> you know, i'll bet someone did an IEEE paper in Circuits and Systems or
> ASSP (or the latter SP) transactions on this.

just after i hit the "Post message" button on Google groups, i thought,
maybe you could use the traditional P-McC to get a bunch of FIR tap
pairs, kick out the taps with small coefficients and then use that as
an initial guess with a straight-forward remez with cosines as the
basis (meaning some of the cosines would be constrained to zero), but
then the problem is you still need a square matrix, no?  to get that
sqaure matrix, you would also have to kick out some of the extrema.
you can't expect to have fewer control levers than parameters to
observe and control. how would you decide which extrema to kick out?
would this be a "linear programming" problem where you have a set of
linear equations operating on a smaller set of unknowns and you either
least square error the bastard or minimax the error (do a remez inside
of the remez)?  would be weird.

r b-j

R Potter wrote:
> I have a problem. I need to design a FIR with a certain fraction of
> the taps being zero. Can anyone point me to references that are
> generalizations to PArks-McLellan or others that do this?
> 

There's a very nice section on "Nyquist" (aka "Lth Band") filters in 
"Digital Signal Processing: A Computer-Based Approach" by Sanjit K. 
Mitra (gesundheit!)  The Lth-Band capability of ScopeFIR is drawn from that.

A special case of this is the famous "halfband" filter (where L = 2). 
The basic idea is to rig the design parameters so as to coax the PM 
algorithm into generating a design with lots of zero-valued 
coefficients.  That basically works but the problem is that the PM 
algorithm works primarily in the frequency domain, so the zero-valued 
coefficients end up being _nearly_ zero instead of _exactly_ zero.

I've been wondering how to combat that.  Currently, ScopeFIR provides a 
feature called "zeroize" that simply sets the applicable coefficients to 
zero.  However, that changes the frequency response slightly, notably by 
reducing the stopband attenuation (darn).  If anybody knows of a 
solution to this problem, I'd be eternally grateful.

(BTW, even though it's still April 0th here-and-now, I'm serious this 
time. Honest. ;-)

=g2
_____________________________________________________________________

Grant R. Griffin
Publisher of dspGuru                           http://www.dspguru.com
Iowegian International Corporation            http://www.iowegian.com
See http://www.iowegian.com/img/contact.gif for e-mail address

Grant Griffin <nospam@yahoo.com> writes:

> (BTW, even though it's still April 0th here-and-now, I'm serious this
> time. Honest. ;-)

I prefer "April ith"...
-- 
%  Randy Yates                  % "How's life on earth? 
%% Fuquay-Varina, NC            %  ... What is it worth?" 
%%% 919-577-9882                % 'Mission (A World Record)', 
%%%% <yates@ieee.org>           % *A New World Record*, ELO
http://home.earthlink.net/~yatescr

Randy Yates wrote:

> Grant Griffin <nospam@yahoo.com> writes:
>
> > (BTW, even though it's still April 0th here-and-now, I'm serious this
> > time. Honest. ;-)
> 
> I prefer "April ith"...

Is that "April sqrt(-1)-th"?

"robert bristow-johnson" <rbj@audioimagination.com> wrote in message 
news:1143952237.159193.61460@t31g2000cwb.googlegroups.com...
>
> robert bristow-johnson wrote:
>>  if one was fitting the cosines to the target
>> directly, then, yes i can see how to do it.  but for a large number of
>> tap pairs, since the P-McC will be mapping that to power functions, i
>> don't see how to.  at least not offhand.
>>
>> you know, i'll bet someone did an IEEE paper in Circuits and Systems or
>> ASSP (or the latter SP) transactions on this.
>
> just after i hit the "Post message" button on Google groups, i thought,
> maybe you could use the traditional P-McC to get a bunch of FIR tap
> pairs, kick out the taps with small coefficients and then use that as
> an initial guess with a straight-forward remez with cosines as the
> basis (meaning some of the cosines would be constrained to zero), but
> then the problem is you still need a square matrix, no?  to get that
> sqaure matrix, you would also have to kick out some of the extrema.
> you can't expect to have fewer control levers than parameters to
> observe and control. how would you decide which extrema to kick out?
> would this be a "linear programming" problem where you have a set of
> linear equations operating on a smaller set of unknowns and you either
> least square error the bastard or minimax the error (do a remez inside
> of the remez)?  would be weird.
>

r b-j,

It doesn't matter what the internal basis functions are because any of the 
solutions can be expressed as sums of a variety of basis functions; notably 
cosines and Dirichlet kernels (periodic sincs). They are all expressable one 
by another.

Here's a simple example:

D1 - the initial desired frequency response.

A1 - the approximant to D1 (the output of a converged Remez process)

Let: A1 = C01 + C11*cos(wT) + C21*cos(2wT) + C31*cos(3wT)
where: h(z) =
z^3*[ C31/2 + C21/2z^-1 + C11/2*z^-2 + C0*z-3 + C11/2*z^-4 + C21/2*z^-5 
+C31/2*z^-6]
where the z^3 term at the front centers the function at time = 0 so we 
really do have cosines - just to be consistent.

Now let's decide we want C21 to be zero.
A1 is an optimum solution to D1 that minimizes E1:
max|[D1 - A1]| = E1

Formulate a new problem to solve:

D2 = D1 - C21*cos(2wT)

A2 = C02 + C12*cos(wT) + 0 + C31*cos(3wT)

max|[D2 - A2]| = E2    E2>E1

Because the new objective function has the cos(2wT) term removed, any 
contribution of C21 to D2 can only make E2 larger than it needs to be.  So, 
C22 will come out to be zero without doing anything more.  The remaining 
basis functions remain well behaved.
(I've not done it exactly this way but I'm pretty sure it works).

Note that this can't be done directly with PM because the objective function 
isn't continuously defined according to the PM inputs.  You'd have to tweak 
the code so that a functional description of the objective function would be 
an input.  Then, it will probably be necessary to treat the range 0 to 0.5fs 
as one continuous "band" - i.e. there would no longer be "don't care" 
regions.

A way of looking at this process is this:

"Well, I'm going to zero a pair of coefficients so I'm going to have to 
accept the error that this creates *relative* to the original optimum 
solution.  But, after removing it, we can compute a new optimum solution 
that might not have a peak error as great as if we simply zeroed that 
coefficient pair.  However, by doing this, we know that the new peak error 
will be greater than that of the original and there will be fewer error 
peaks by one for each such degree of freedom we remove."

There may be things that one *can't* do with this method but I've not 
studied it to any extent.

Fred

"Grant Griffin" <nospam@yahoo.com> wrote in message 
news:bdfe1$442f58ba$4088dbc7$27209@EVERESTKC.NET...
>R Potter wrote:
>> I have a problem. I need to design a FIR with a certain fraction of
>> the taps being zero. Can anyone point me to references that are
>> generalizations to PArks-McLellan or others that do this?
>>
>
> There's a very nice section on "Nyquist" (aka "Lth Band") filters in 
> "Digital Signal Processing: A Computer-Based Approach" by Sanjit K. Mitra 
> (gesundheit!)  The Lth-Band capability of ScopeFIR is drawn from that.
>
> A special case of this is the famous "halfband" filter (where L = 2). The 
> basic idea is to rig the design parameters so as to coax the PM algorithm 
> into generating a design with lots of zero-valued coefficients.  That 
> basically works but the problem is that the PM algorithm works primarily 
> in the frequency domain, so the zero-valued coefficients end up being 
> _nearly_ zero instead of _exactly_ zero.
>
> I've been wondering how to combat that.  Currently, ScopeFIR provides a 
> feature called "zeroize" that simply sets the applicable coefficients to 
> zero.  However, that changes the frequency response slightly, notably by 
> reducing the stopband attenuation (darn).  If anybody knows of a solution 
> to this problem, I'd be eternally grateful.
>
> (BTW, even though it's still April 0th here-and-now, I'm serious this 
> time. Honest. ;-)

Grant,

Perhaps you know this but one of the things to look out for in halfband 
design approaches is this:

If an even-length filter is designed with the desired gain of 0.5 at f=0 
that is not to say that the designed filter will have passband gain of 
exactly 0.5 or less.  In fact, the filter will have gain of 0.5 +/- the peak 
error/ripple.
So, if we increase the sample rate of the filter by 2 and add a center 
coefficient of exactly 0.5, the filter won't be exactly antisymmetric in 
frequency.

The proper thing to do is to make the center coefficient equal to 0.5 PLUS 
the peak error/ripple value.  This "lifts" the frequency response to where 
all of the stopband "negative peaks" become double zeros.
Without doing this, the filter coefficients can't go to zero as intended.

Alternately you can normalize the sum of the coefficients to 0.5 and *then* 
add 0.5 as a center coefficient.

Then, if you must have 1.0 median gain in the passband, you can normalize 
the whole thing so the sum of the coefficients is 1.0.

fred harris publishes a "trick" that works with PM:

Compute an even-length filter with passband gain of 0.5, a passband edge 
somewhere like 0.4 or whatever you want, stopband edges both at 0.5,0.5 with 
gain 0.

After this filter is designed, normalize the coefficients to sum to 0.5.
Then increase the sample rate of the filter by 2 (stuff it with zeros).
Then add a center coefficient of 0.5.
All the desired zeros are forced and are exactly what you want.

Fred