Parks-McClellan Algorithm

Hello,

   Can anyone tell me why when designing a low pass filter using
Parks-McClellan algorithm, the approximation must decrease
monotonically in the "don't care" region between the passband and
stopband?

Hello FTChan,
It is monotonic there since there are no extrema of the interpolating
polynomial in that region. The algo puts them in the bands (pass and stop)
and not in the gaps in between.

IHTH.
-- 
Clay S. Turner, V.P.
Wireless Systems Engineering, Inc.
Satellite Beach, Florida 32937
(321) 777-7889
www.wse.biz
csturner@wse.biz



"FTChan" <foongtek@yahoo.com> wrote in message
news:b2c1978e.0403040410.45923767@posting.google.com...
> Hello,
>
>    Can anyone tell me why when designing a low pass filter using
> Parks-McClellan algorithm, the approximation must decrease
> monotonically in the "don't care" region between the passband and
> stopband?

"FTChan" <foongtek@yahoo.com> wrote in message
news:b2c1978e.0403040410.45923767@posting.google.com...
> Hello,
>
>    Can anyone tell me why when designing a low pass filter using
> Parks-McClellan algorithm, the approximation must decrease
> monotonically in the "don't care" region between the passband and
> stopband?

FT,

Good question!  If you take a look at Rabiner and Gold "Theory and
Application of Digital Signal Processing" in the vicinity of page 149, I
think you'll find a treatment of why this can be the case.  I've not tried
wading through this in a while.

Anyway, Parks and McClellan - along the lines of Rabiner and Gold, took full
advantage of the characteristics of the error functions in setting up their
program.

Without taking the characteristics into consideration, just using a Remez
exchange algorithm and a set of basis functions, then you might lightly
weight the "don't care" region.  In this case it would be  possible to see
peaks in that region.  For example, if you push really hard on the passband
and stopband ripples, then you might allow peaks to grow in the lightly
weighted transition region.  It's akin to "supergaining".  Parks and
McClellan just don't allow peaks to occur there at all.  Maybe the
explanation for how this is done is really simple but I'm not able to
provide better than this for now.

Oh!  Well, part of the trick is that the don't care region is not even
looked at when the error is considered.  This forces all of the peaks to be
in the disjoint space of the passband and stopband with peaks occurring at
the band edges most of the time.  It just works out that way.  That's the
arm-waving answer.

My halfband filter program uses the Remez algorithm.  It used to look at the
error in the transition band and lightly weight it - until I understood this
"trick".  Until then, I had to worry about peaks occurring in the transition
band at the expense of passband ripple.  Now it just ignores the transition
band and all the ripple peaks are in the passband (and its reflected
stopband).

Fred

foongtek@yahoo.com (FTChan) writes:

>    Can anyone tell me why when designing a low pass filter using
> Parks-McClellan algorithm, the approximation must decrease
> monotonically in the "don't care" region between the passband and
> stopband?

HW question?

Think about the order of the filter, and what this means about the
number of extrema the function can have.

Ciao,

Peter K.

-- 
Peter J. Kootsookos

"I will ignore all ideas for new works [..], the invention of which
 has reached its limits and for whose improvement I see no further
 hope."

- Julius Frontinus, c. AD 84

"Peter J. Kootsookos" <p.kootsookos@remove.ieee.org> wrote in message
news:s68znawxlz9.fsf@mango.itee.uq.edu.au...
> foongtek@yahoo.com (FTChan) writes:
>
> >    Can anyone tell me why when designing a low pass filter using
> > Parks-McClellan algorithm, the approximation must decrease
> > monotonically in the "don't care" region between the passband and
> > stopband?
>
> HW question?
>
> Think about the order of the filter, and what this means about the
> number of extrema the function can have.

Peter,

FYI.  That doesn't quite answer the question.  The answer lies in where the
region of approximation is defined and where it is not defined.  Happily, in
this case, if the region of approximation does not include the transition
region (presumably if it were included it would be with low weighting), then
all of the peaks will definitely occur in the "bands" and there will be none
in the transition region.

So, you can think about the number of extrema all right but that doesn't
necessarily say where they occur.  Where they occur depends on the
application details of the Remez exchange algorithm.  Rabiner et al and
Parks and McClellan handled that nicely at the possible expense of not being
able to "work with" the (well-behaved anyway) transition regions.

Fred

>
> FT,
>
> Good question!  If you take a look at Rabiner and Gold "Theory and
> Application of Digital Signal Processing" in the vicinity of page 149, I
> think you'll find a treatment of why this can be the case.  I've not tried
> wading through this in a while.
>
> Anyway, Parks and McClellan - along the lines of Rabiner and Gold, took
full
> advantage of the characteristics of the error functions in setting up
their
> program.
>
> Without taking the characteristics into consideration, just using a Remez
> exchange algorithm and a set of basis functions, then you might lightly
> weight the "don't care" region.  In this case it would be  possible to see
> peaks in that region.  For example, if you push really hard on the
passband
> and stopband ripples, then you might allow peaks to grow in the lightly
> weighted transition region.  It's akin to "supergaining".  Parks and
> McClellan just don't allow peaks to occur there at all.  Maybe the
> explanation for how this is done is really simple but I'm not able to
> provide better than this for now.
>
> Oh!  Well, part of the trick is that the don't care region is not even
> looked at when the error is considered.  This forces all of the peaks to
be
> in the disjoint space of the passband and stopband with peaks occurring at
> the band edges most of the time.  It just works out that way.  That's the
> arm-waving answer.
>
> My halfband filter program uses the Remez algorithm.  It used to look at
the
> error in the transition band and lightly weight it - until I understood
this
> "trick".  Until then, I had to worry about peaks occurring in the
transition
> band at the expense of passband ripple.  Now it just ignores the
transition
> band and all the ripple peaks are in the passband (and its reflected
> stopband).
>
> Fred
>

I needed to optimize RRC filters which have a specific transition band and
therefore really don't have a "don't care" region.  I had to modify my
Parks-McClellan program so that the transition band is actually part of the
passband, and then I just set the desired response to the shape of the
passband/transition band.  (Normally the desired response for each band is
either all 1 or all 0.)

If you want any arbitrary shape in the transition band, or peaks or
whatever, one could use the same technique.  I'm not sure if that's the goal
here.

-Kevin

"Kevin Neilson" <kevin_neilson@removethiscomcast.net> wrote in message
news:Opb2c.470804$I06.5294489@attbi_s01...
>
>
> I needed to optimize RRC filters which have a specific transition band and
> therefore really don't have a "don't care" region.  I had to modify my
> Parks-McClellan program so that the transition band is actually part of
the
> passband, and then I just set the desired response to the shape of the
> passband/transition band.  (Normally the desired response for each band is
> either all 1 or all 0.)
>
> If you want any arbitrary shape in the transition band, or peaks or
> whatever, one could use the same technique.  I'm not sure if that's the
goal
> here.

Kevin,

No, that wasn't the topic the OP posed.  But the answer revolves around
where is the region of approximation.  As you encountered, the PM program
uses a disjoint region of approximation.  It also only uses flat response
specifications for each band and flat weighting as you've alluded to.  Well
.... you can always define a multiband filter with a variety of response
values - the 1 and 0 are choices that you make.

Can you get good RRC filters using a minimax criterion?  I've thought about
working on a better design program for them.

Fred

>
> Kevin,
>
> No, that wasn't the topic the OP posed.  But the answer revolves around
> where is the region of approximation.  As you encountered, the PM program
> uses a disjoint region of approximation.  It also only uses flat response
> specifications for each band and flat weighting as you've alluded to.
Well
> .... you can always define a multiband filter with a variety of response
> values - the 1 and 0 are choices that you make.
>
> Can you get good RRC filters using a minimax criterion?  I've thought
about
> working on a better design program for them.
>
> Fred
>
My (modified) program seems to work really well.  I got tired of the really
long filters required to make RRCs when using filter design programs that
just use the textbook formula, which yields a very flat passband but a
really big first sidelobe.  I get that sidelobe down by adding some passband
ripple.  The result has a little more ISI than the ideal, but often it's
worth it because the textbook filter isn't even realizeable in a
reasonably-sized FPGA.  The ISI is something you have the option of
tinkering with whereas the mask is usually regulatory and allows no
infractions.

-Kevin

"Kevin Neilson" <kevin_neilson@removethiscomcast.net> wrote in message
news:Qdo2c.60762$PR3.1069031@attbi_s03...
> > Can you get good RRC filters using a minimax criterion?  I've thought
> about
> > working on a better design program for them.
> >
> > Fred
> >
> My (modified) program seems to work really well.  I got tired of the
really
> long filters required to make RRCs when using filter design programs that
> just use the textbook formula, which yields a very flat passband but a
> really big first sidelobe.  I get that sidelobe down by adding some
passband
> ripple.  The result has a little more ISI than the ideal, but often it's
> worth it because the textbook filter isn't even realizeable in a
> reasonably-sized FPGA.  The ISI is something you have the option of
> tinkering with whereas the mask is usually regulatory and allows no
> infractions.

Well, the idea of course is to satisfy the Gibby-Smith criterion so that the
filters end up with antisymmetric deviation from a brick-wall filter.  This
allows the periodic zeros that are like a sinc and desired for ISI.  You
know all this.

Years ago I worked on the periodic zero character by working in the time
domain and keeping the band limitation intact.  The results would meet the
Gibby-Smith (continuous / bandlimtied) frequency criterion while meeting
minimax error in the (continuous) time domain.  Yes, these were theoretical
in that the filters were strictly bandlimiting lowpass filters with
infinitely long impulse responses.

I've also done some work on minimax half-band FIR filter design - which has
an antisymmetric frequency response as well.  One might view it as a member
of a set of such filters that includes a raised cosine filter.

If your RRC filters had large sidelobes then that implies that they had
similar passband ripple doesn't it?

Fred

>
> Well, the idea of course is to satisfy the Gibby-Smith criterion so that
the
> filters end up with antisymmetric deviation from a brick-wall filter.
This
> allows the periodic zeros that are like a sinc and desired for ISI.  You
> know all this.
>
> Years ago I worked on the periodic zero character by working in the time
> domain and keeping the band limitation intact.  The results would meet the
> Gibby-Smith (continuous / bandlimtied) frequency criterion while meeting
> minimax error in the (continuous) time domain.  Yes, these were
theoretical
> in that the filters were strictly bandlimiting lowpass filters with
> infinitely long impulse responses.
>
> I've also done some work on minimax half-band FIR filter design - which
has
> an antisymmetric frequency response as well.  One might view it as a
member
> of a set of such filters that includes a raised cosine filter.
>
> If your RRC filters had large sidelobes then that implies that they had
> similar passband ripple doesn't it?
>
> Fred
>

Here is an example.  If I make a 32-symbol, 2X interpolating, 15% rolloff,
SRRC FIR with my filter design program I get a filter which isn't equiripple
and has a max passband ripple of about .04dB and the first sidelobe at
about -39dB.  Lame!  The stopband isn't equiripple and the successive
sidelobes are much smaller.  I think this is the same result you'd get using
Matlab.  I'm not sure how it works, but I think it just samples the ideal
impulse response which is the transform (that can be found without numerical
integration) of an ideal raised cosine shape.

Now if I use my program, and decide I want to allow up to .25dB of ripple, I
get an equiripple stopband of about -57dB.  This ripple is acceptable; the
allowed passband ripple in the DVB-C spec, for example, is 0.4dB.  Let's say
my stopband requirement is -57dB.  To get my filter designer to meet this
requirement and get the first sidelobe at -57dB, I need to make a filter
that is about 256 symbols long!  I think too often designers are meeting
their requirements by having an inadequate shaping filter and using an
extra-tight, extra-high-insertion-loss SAW.

I haven't quantified the increase in ISI but I think you can by convolving
two of the SRRC impulse responses together and then looking at the magnitude
sum of the samples that are supposed to be zero (but aren't in the optimized
filter).  This sum would be the amount by which I or Q could be off, so it
would be sqrt(2)/2 of the max error vector magnitude caused by ISI.  I
suppose I ought to add this to my program so I could get an idea of what the
symbol spread increase will be by adding passband ripple.

Hey, did I tell you I liked your paper on Farrow filters?  I used that as a
basis for some irrational interpolators I made for FPGAs.

-Kevin