Optimal Chebyshev FIR Filters

As we've seen above, the defining characteristic of FIR filters
optimal in the Chebyshev sense is that they minimize the *maximum
frequency-response error-magnitude* over the frequency axis. In
other terms, an optimal Chebyshev FIR filter is optimal in the
*minimax sense*: The filter coefficients are chosen to minimize
the *worst-case error* (maximum weighted error-magnitude ripple)
over all frequencies. This also means it is optimal in the
sense because, as noted above, the
norm of a weighted
frequency-response error
is the maximum magnitude over all frequencies:

(5.32) |

Thus, we can say that an optimal Chebyshev filter minimizes the norm of the (possibly weighted) frequency-response error. The norm is also called the

The optimal Chebyshev FIR filter can often be found effectively using
the *Remez multiple exchange algorithm* (typically called the
*Parks-McClellan algorithm* when applied to FIR filter design)
[176,224,66]. This was illustrated in
§4.6.4 above. The Parks-McClellan/Remez algorithm also
appears to be the *most efficient* known method for designing
optimal Chebyshev FIR filters (as compared with, say linear
programming methods using matlab's `linprog` as in
§3.13). This algorithm is available in Matlab's Signal
Processing Toolbox as `firpm()` (`remez()` in (Linux)
Octave).^{5.13}There is also a version of the Remez exchange algorithm for
*complex* FIR filters. See §4.10.7 below for a few
details.

The Remez multiple exchange algorithm has its limitations, however. In
particular, convergence of the FIR filter coefficients is
*unlikely* for FIR filters longer than a few hundred taps or so.

Optimal Chebyshev FIR filters are normally designed to be *linear
phase* [263] so that the desired frequency response
can be taken to be real (*i.e.*, first a *zero-phase*
FIR filter is designed). The design of linear-phase FIR filters in
the frequency domain can therefore be characterized as *real
polynomial approximation* on the unit circle [229,258].

In optimal Chebyshev filter designs, the error exhibits an
*equiripple* characteristic--that is, if the desired
response is
and the ripple magnitude is
, then
the frequency response of the optimal FIR filter (in the unweighted
case, *i.e.*,
for all
) will oscillate between
and
as
increases.
The powerful *alternation theorem* characterizes optimal
Chebyshev solutions in terms of the alternating error peaks.
Essentially, if one finds sufficiently many for the given FIR filter
order, then you have found the unique optimal Chebyshev solution
[224]. Another remarkable result is that the Remez
multiple exchange converges *monotonically* to the unique optimal
Chebyshev solution (in the absence of numerical round-off errors).

Fine online introductions to the theory and practice of Chebyshev-optimal FIR filter design are given in [32,283].

The window method (§4.5) and Remez-exchange method together span many practical FIR filter design needs, from ``quick and dirty'' to essentially ideal FIR filters (in terms of conventional specifications).

[How to cite this work] [Order a printed hardcopy] [Comment on this page via email]

[Watch the Video] [Work some Exercises] [Examination]

Copyright ©

Center for Computer Research in Music and Acoustics (CCRMA), Stanford University