Stan Pawlukiewicz <spam@spam.mitre.org> wrote in message news:<chpv16$fd9$1@newslocal.mitre.org>...
> Rune Allnor wrote:
> > Stan Pawlukiewicz <spam@spam.mitre.org> wrote in message news:<chn69n$2qs$1@newslocal.mitre.org>...
>  (snip)
> > This is really interesting. I certainly agree with you that LP is a more
> > general method than the Remez thing, and once you mention it, there is 
> > probably a reason why the matlab function that implements the  
> > Parks/McClellan algorithm is called REMEZ. Still (or unfortunately), 
> > the Remez version appears to be the de facto standard and what everybody 
> > use, and what everything else is compared to. 
> 
> That's what the old window method guys said about remez when it came out.
> 
> A sure sign of getting old and crotchety ;)

Well... perhaps... better than the alternative of getting crotchety in 
a young age... The fact that such things have been said before, is merely 
a sign that development is a continuous process. That one remembers 
such things having been said before... yep, I've been there just enough 
times to understand the effects.  

> I meet Tom Parks back around 1987 or 88.  Matlab at that time was at 
> version 3.5 and the signal processing toolbox was included, not an 
> extra.  Remez was a mex file and the reason, according to Tom, was that 
> the Mathworks couldn't figure out how to convert it to an m file.

Rune

Hi Jim-  I still pop in every now and again.  Perhaps I should visit
more often, but the dreams of z's, s's, sincs, and butterflies have
just started to go away.

Rune- My version hasn't been updated in a long time.  I've received a
couple emails regarding certain cases that fail in my version, but not
in the Matlab version.  I think there is some extra 'meat' in the
Matlab version now days to handle some of these cases.

Regardless, it's a decent start to a pretty algorithm.

   Cheers,
   Jake

Jim Thomas <jthomas@bittware.com> wrote in message news:<10ju1gv4ajdqa81@corp.supernews.com>...
> Rune Allnor wrote:
> > To make the above story short, my question is if anyone knows of a 
> > readable and accesible account of the Remez exchange algorithm.
> 
> The canonical comp.dsp reference for Remez would be Jake Janovetz's 
> implementation:
> 
> http://www.janovetz.com/jake/
> 
> Jake used to be a regular here, and his work on Remez has received 
> plenty of comp.dsp accolades.  I think his "account" of Remez is written 
> in C.

"Stan Pawlukiewicz" <spam@spam.mitre.org> wrote in message
news:chpv16$fd9$1@newslocal.mitre.org...
>>
> I meet Tom Parks back around 1987 or 88.  Matlab at that time was at
> version 3.5 and the signal processing toolbox was included, not an
> extra.  Remez was a mex file and the reason, according to Tom, was that
> the Mathworks couldn't figure out how to convert it to an m file.
>
Hello Stan,

When I ventured to understand and program the Remez algo, I looked at the
Fortran version that PM used and of course it has a bunch of "goto"
statements which of course don't fit in well with structured code. While
aptly described as spaghetti code, I once heard a description of macaroni
code given since the continuous threads of code are all short.  Certainly
one of the 1st things I did was to change the Remez structure around enough
to get rid of those "gotos". Even though "c" supports goto statements,
computer programming teachers at the time would go to great lengths to not
tell their students that the language supports this so the students wouldn't
be tempted to use them.

Clay

p.s. I think many of us are getting old and crotchety, but I think that is
better than the alternative of not getting old at all.

Rune Allnor wrote:
> Stan Pawlukiewicz <spam@spam.mitre.org> wrote in message news:<chn69n$2qs$1@newslocal.mitre.org>...
(snip)
> This is really interesting. I certainly agree with you that LP is a more
> general method than the Remez thing, and once you mention it, there is 
> probably a reason why the matlab function that implements the  
> Parks/McClellan algorithm is called REMEZ. Still (or unfortunately), 
> the Remez version appears to be the de facto standard and what everybody 
> use, and what everything else is compared to. 

That's what the old window method guys said about remez when it came out.

A sure sign of getting old and crotchety ;)

I meet Tom Parks back around 1987 or 88.  Matlab at that time was at 
version 3.5 and the signal processing toolbox was included, not an 
extra.  Remez was a mex file and the reason, according to Tom, was that 
the Mathworks couldn't figure out how to convert it to an m file.

>  
> 
>>There are also a number of LP solvers available on the web in various 
>>languages and in various shades of object orientation.
> 
> 
> I believe you. But that's a completely different project...
> 
> Rune

"Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message news:<2cGdnYK8c67p36LcRVn-hA@centurytel.net>...

> I hope this helps.
> 
> Fred

It sure does. I have to ponder both your paper and your post a bit 
more, but what you say here is exactly the type of hints and tips I 
was hoping somebody would provide. 

Thanks.

Rune

"Clay Turner" <physics@bellsouth.net> wrote in message news:<BeF%c.111121$_h.68316@bignews3.bellsouth.net>...
> "Rune Allnor" <allnor@tele.ntnu.no> wrote in message
> news:f56893ae.0409080215.48eff776@posting.google.com...
> > Hi All.
> >
> > To make a short story long, my little FIR filter project is happily
> > trodding along. I am starting to get the various window functions in
> > place for LP prototypes, and with some luck, it's not a big deal to
> > generate HP or BP versions from the LP prototypes. Band-stop filters
> > are a bit more cumbersome, I have to thing about how to implement them.
> >
> > All the FIR window design stuff appears to be going on well. So, I thougt
> > (infinitely naive as I am) why not have a go with the Parks-McClellan
> > algorithm as well.
> >
> > I searched at IEEExplore and found four or five papers from the early
> > 1970ies authored by the venerable Parks & McClellan and found flow
> > charts and FORTRAN code (spaghetti version) galore. I am not very fond of
> > untangling spaghetti code, but the flow charts are clear enough for me to
> > implement my own version of the algorithm.
> >
> > Except for the Remez exchange step that apparently is so crucial. So I
> > consulted "Numerical Recipies" to see what they had to say about the
> > Remez algorithm. They basically said "we don't like the Remez thing,
> > we prefer to do things by brute force", and then they went on by
> > explaining how to do things by brute force.
> >
> > To make the above story short, my question is if anyone knows of a
> > readable and accesible account of the Remez exchange algorithm.
> >
> > Rune
> 
> Hello Rune,
> 
> Here is "c" version of the Remez algo from the PM papers. Most of the
> variable names are the same so deciphering it shouldn't be too hard.
> 
> The function Ak() calculates the Barycentric weights.
> 
> The functions BF() and BFc() evaluate the current LaGrange polynomial. BF()
> is past an index to the grid which refers to the x value. Whereas BFc() is
> simply passed an x value.
> 
> rhofun() calculates the chebyshev deviation factor.
> 
> I'm sorry the documentation is nonexistant. I haven't done anything with
> this code in nearly 20 years. I did put together a complete PM algo. And I
> can make that code available if desired.
> 
> Clay

Thanks, Clay, for posting the code. When I see your code, I understand 
what Press & al. mean when they write about the Remez algorithm [1, p 205]

   "Up to this point, our discussion has been textbook-standard. We now
    reveal ourselves as heretics. We don't much like the elegant 
    Remes [sic!] algorithm. Its two nested iterations (...) are finicky
    and require a lot of special logic for degenerate cases."

Rune

[1] Press & al: "Numerical Recipes in C"
                 Cambridge, 1992.

Stan Pawlukiewicz <spam@spam.mitre.org> wrote in message news:<chn69n$2qs$1@newslocal.mitre.org>...
> Rune Allnor wrote:
> > Hi All. 
> > 
> > To make a short story long, my little FIR filter project is happily 
> > trodding along. I am starting to get the various window functions in 
> > place for LP prototypes, and with some luck, it's not a big deal to 
> > generate HP or BP versions from the LP prototypes. Band-stop filters 
> > are a bit more cumbersome, I have to thing about how to implement them. 
> > 
> > All the FIR window design stuff appears to be going on well. So, I thougt
> > (infinitely naive as I am) why not have a go with the Parks-McClellan 
> > algorithm as well. 
> > 
> > I searched at IEEExplore and found four or five papers from the early 
> > 1970ies authored by the venerable Parks & McClellan and found flow 
> > charts and FORTRAN code (spaghetti version) galore. I am not very fond of 
> > untangling spaghetti code, but the flow charts are clear enough for me to 
> > implement my own version of the algorithm. 
> > 
> > Except for the Remez exchange step that apparently is so crucial. So I 
> > consulted "Numerical Recipies" to see what they had to say about the 
> > Remez algorithm. They basically said "we don't like the Remez thing, 
> > we prefer to do things by brute force", and then they went on by 
> > explaining how to do things by brute force. 
> > 
> > To make the above story short, my question is if anyone knows of a 
> > readable and accesible account of the Remez exchange algorithm.
> > 
> > Rune
> 
> An alternative is to use a general linear program (LP) solver.  There is 
> a section in Rabiner and Gold that shows how, for Chebychev min max 
> designs equivalent to Remez.  They, Rabiner and Gold, also make the 
> statement that an advantage of the LP approach is being able to also 
> include time domain constraints in the filter design. 

Somebody (Rick?) made a comment to that effect not long ago. He had 
apparently taken a Remez design, and tweaked the coefficients in the 
"don't care" coefficients in the transition band to manipulate the time 
response.

> The Remez 
> approach is more efficient but since we don't think of of a VAX with 64K 
> of memory as being a particularly representative workstation anymore, 
> the differences in efficiency are not likely to be as critical as they 
> once were.

Well... in the fall of 1990 I got an "offer I couldn't refuse" while 
at engineering school. A new computer shop opened in town, and presented
an introduction offer to engineering students: An Intel 386, 25 MHz CPU, 
prepared to accept the 387 maths unit (I didn't buy the 387 until the 
year after) with 2 MB RAM and 20 MB hard disk. To the genrous asking 
price of NOK 20000 (USD 3000 by current exchange rates). 

A couple of months ago, I got my new laptop, 1.5 GHz CPU, 512 MB RAM
(prepared for 2 GB) and 40 GB hard disk. The thing cost way less than 
NOK 20000.

In the 15 years since my first PC, the CPU goes a factor 100 faster 
while memory has increased by a factor 1000. Efficiency isn't really an 
issue for these kinds of toy projects.

> Remez is a specialized algorithm. I don't know of any application of it 
>   other than to Parks-Maclelan. Linear programming is considerably more 
> general and INMHO more interesting and useful. Time spent understanding 
> LP is well spent.  I'm not inclined to say the same of Remez.

This is really interesting. I certainly agree with you that LP is a more
general method than the Remez thing, and once you mention it, there is 
probably a reason why the matlab function that implements the  
Parks/McClellan algorithm is called REMEZ. Still (or unfortunately), 
the Remez version appears to be the de facto standard and what everybody 
use, and what everything else is compared to. 

> There are also a number of LP solvers available on the web in various 
> languages and in various shades of object orientation.

I believe you. But that's a completely different project...

Rune

Jerry Avins <jya@ieee.org> wrote in message news:<413f0c04$0$6931$61fed72c@news.rcn.com>...
> Rune Allnor wrote:
> 
> > Hi All. 
> > 
> > To make a short story long, my little FIR filter project is happily 
> > trodding along. I am starting to get the various window functions in 
> > place for LP prototypes, and with some luck, it's not a big deal to 
> > generate HP or BP versions from the LP prototypes. Band-stop filters 
> > are a bit more cumbersome, I have to thing about how to implement them. 
> > 
> > All the FIR window design stuff appears to be going on well. So, I thougt
> > (infinitely naive as I am) why not have a go with the Parks-McClellan 
> > algorithm as well. 
> > 
> > I searched at IEEExplore and found four or five papers from the early 
> > 1970ies authored by the venerable Parks & McClellan and found flow 
> > charts and FORTRAN code (spaghetti version) galore. I am not very fond of 
> > untangling spaghetti code, but the flow charts are clear enough for me to 
> > implement my own version of the algorithm. 
> > 
> > Except for the Remez exchange step that apparently is so crucial. So I 
> > consulted "Numerical Recipies" to see what they had to say about the 
> > Remez algorithm. They basically said "we don't like the Remez thing, 
> > we prefer to do things by brute force", and then they went on by 
> > explaining how to do things by brute force. 
> > 
> > To make the above story short, my question is if anyone knows of a 
> > readable and accesible account of the Remez exchange algorithm.
> > 
> > Rune
> 
> "An Introduction to the Approximation of Functions" by Theodore J.
> Rivlin. My Dover reprint cost $3.50, but the price has risen now to
> $8.95. http://store.yahoo.com/doverpublications/0486640698.html
> 
> It's rather abstruse (Rick will look that up), maybe too hard for me,
> but duck soup for you. What other book can be has for about the same
> price as the postage?

Dover is a brilliant publishing house. Where else can you find stuff 
published in 187& (and earlier, for all I know)? I just wish they would 
include the classical Rabiner & Gold in their catalogue...

Rune