# REMEZ computational complexity

Started by September 20, 2006
```Can any body tell me the complexity means number of operations required by
the
1. remezord algorithm to estimate the order of filter.
2. remez algorithm to calculate an N order filter's impulse response
(coefficients).

Thnaks in advance for the information.

```
```"renaudin" <alsaeed86@gmail.com> wrote in message
news:SfGdncEvNM8-mIzYnZ2dnUVZ_sydnZ2d@giganews.com...
> Can any body tell me the complexity means number of operations required by
> the
> 1. remezord algorithm to estimate the order of filter.
> 2. remez algorithm to calculate an N order filter's impulse response
> (coefficients).
>
> Thnaks in advance for the information.
>

Most of the estimates for filter order are simple expressions that take a
single evaluation.  Thus, the number of operations is very small compared to
computing a filter design.
It depends on the actual expression that's used.  I suppose you could figure
it out from a description of remezord.  It says it uses:
Rabiner, L.R., and O. Herrmann, "The Predictability of Certain Optimum
Finite Impulse Response Digital Filters," IEEE Trans. on Circuit Theory,
Vol. CT-20, No. 4 (July 1973), pp. 401-408.

Running a filter design requires an N+1 point interpolation or,
equivalently, the solution of a system of N+1 linear equations at each
iteration.  The number of iterations can range from 2-3 for a filter of
modest length *and* specifications to over 20 for longer filters with more
stringent specifications.  So, it's not only the length of the filter but
the specifications as well that drive the number of iterations.  I would say
that the number of operations is quite dependent on the particular code
because there are also searches and sorts to do at each iteration to decide
where the next N+1 points lie in frequency.

To expand this discussion:

My own code that runs on a PC is good for filter lengths up to maybe 128 or
so.  After that, numerical inaccuracies combine to thwart convergence.

Does anyone know of a readily available Remez program that will go to maybe
length 1000 or greater?  That would be interesting...  I'm also interested
in *how* it's done.

Fred

```
```"Fred Marshall" <fmarshallx@remove_the_x.acm.org> schrieb im Newsbeitrag
news:bpKdnS5FAP9PH4zYnZ2dnUVZ_sydnZ2d@centurytel.net...
>
> "renaudin" <alsaeed86@gmail.com> wrote in message
> news:SfGdncEvNM8-mIzYnZ2dnUVZ_sydnZ2d@giganews.com...
>> Can any body tell me the complexity means number of operations required
>> by
>> the
>> 1. remezord algorithm to estimate the order of filter.
>> 2. remez algorithm to calculate an N order filter's impulse response
>> (coefficients).
>>
>> Thnaks in advance for the information.
>>
>
> Most of the estimates for filter order are simple expressions that take a
> single evaluation.  Thus, the number of operations is very small compared
> to computing a filter design.
> It depends on the actual expression that's used.  I suppose you could
> figure it out from a description of remezord.  It says it uses:
> Rabiner, L.R., and O. Herrmann, "The Predictability of Certain Optimum
> Finite Impulse Response Digital Filters," IEEE Trans. on Circuit Theory,
> Vol. CT-20, No. 4 (July 1973), pp. 401-408.
>
> Running a filter design requires an N+1 point interpolation or,
> equivalently, the solution of a system of N+1 linear equations at each
> iteration.  The number of iterations can range from 2-3 for a filter of
> modest length *and* specifications to over 20 for longer filters with more
> stringent specifications.  So, it's not only the length of the filter but
> the specifications as well that drive the number of iterations.  I would
> say that the number of operations is quite dependent on the particular
> code because there are also searches and sorts to do at each iteration to
> decide where the next N+1 points lie in frequency.
>
> To expand this discussion:
>
> My own code that runs on a PC is good for filter lengths up to maybe 128
> or so.  After that, numerical inaccuracies combine to thwart convergence.
>
> Does anyone know of a readily available Remez program that will go to
> maybe length 1000 or greater?  That would be interesting...  I'm also
> interested in *how* it's done.
>
> Fred
>
Hello Fred,

I just increase the grid density, if the convergence of the remez is bad. It
works quite well,
but for higher tap counts it takes a while ;-).

Gerold

```