Navigation
-
Content Actions
-
Recently Viewed
Chebyshev or Equal Ripple Error Approximation Filters
If one poses the FIR filter design problem by requiring the maximum error
over certain bands of frequencies be minimized, we call the resulting
filter a Chebyshev filter or an equal ripple filter. The fact that the
minimization of the Chebyshev or
There are several ways one could pose the Chebyshev FIR filter design
problem. For a simple length-N linear phase, lowpass filter with a transition band, if
one considers the length N, the passband ripple
The Chebyshev error measure is often used for approximation in digital filter design. This is particularly true when the signals and/or noise are narrow band or single frequency or when one wants to minimize worst case possibilities. Theoretical justification for its use has been given by Weisburn, Parks, and Shenoy Entry 94. For FIR filter design, the Parks-McClellan formulation of the filter design problem and application of the Remez exchange algorithm is most commonly used Entry 48, Entry 50. It is a particularly interesting and powerful method that should be studied and understood to be fully utilized.
Linear programming was used earlier Entry 87, Entry 26, Entry 62 but dropped out of favor when the Parks-McClellan algorithm was introduced. It is now becoming more popular again because of more powerful computers, better algorithms Entry 83, Entry 5, and linear programming's ability to allow a variety of constraints Entry 80.
Still another approach to
achieving a Chebyshev approximation is to minimize the
The early work by Herrmann and Schüssler Entry 27, Entry 31 and the algorithm
by Hofstetter, Oppenheim, and Siegel Entry 28, Entry 29 posed and solved a
similar problem but they had only approximate control of
The Linear Phase FIR Filter Chebyshev Approximation Problem
The Chebyshev error is defined as the maximum difference between the actual and desired response over a band or several bands of frequencies. This is
where
One way to minimize
If the amplitude response for odd L is expressed as a sum of
or for even L
with
Theorem 1
If
The alternation theorem Entry 48, Entry 52 states that the minimum Chebyshev
error has at least
for
Chebyshev Approximation by Linear Programming
It is possible to pose the Chebyshev approximation problem in filter design as a linear programming optimization problem Entry 62, Entry 89, Entry 81, Entry 41. The error definition in (Equation 1) can be written as an inequality by
where the scalar
The inequalities in (Equation 5) can be written as
or
which can be combined into one matrix inequality using ((Reference)) by
If
which, together with the inequality of (Equation 10), is in the form of the dual problem in linear programming Entry 19, Entry 43, Entry 82.
This can be solved using the lp() command from the Optimization Toolbox with Matlab Entry 23, the Meteor software system Entry 80, CPlex Entry 7, or Karmarkar's algorithm Entry 5, Entry 35. The Matlab lp command is implemented in an m-file using a form of quadratic programming algorithm that is not well suited to our filter design problem. Meteor is a linear programming system using the simplex algorithm written in Pascal by Ken Steiglitz especially for filter design. It has been compiled on a variety of computers and efficiently designs filters over 100 in length. The Karmarkar program written by Lang is a relatively short m-file that is not particularly fast but is robust and can design filters on the order of length-100. CPlex is a proprietary program that can be used alone or called from Fortran programs and is particularly robust and fast.
A Matlab program that applies its linear programming function lp.m to (Equation 10,Equation 11) for linear phase FIR filter design is given by:
% lpdesign.m Design an FIR filter from L, f1, f2, and LF using LP.
% L is filter length, f1 and f2 are pass and stopband edges, LF is
% the number of freq samples. L is odd. Uses lp.m
% csb 5/22/91
L1 = fix(LF*f1/(.5-f2+f1)); L2 = LF - L1; %No. freq samples in PB, SB
Ad = [ones(L1,1); zeros(L2,1)]; %Samples of ideal response
f = [[0:L1-1]*f1/(L1-1), ([0:L2-1]*(.5-f2)/(L2-1) + f2)]'; %Freq samples
M = (L-1)/2;
C = cos(2*pi*(f*[0:M])); %Freq response matrix
CC = [C, -ones(LF,1); -C, -ones(LF,1)]; %LP matrix
AD = [Ad; -Ad];
c = [zeros(M+1,1);1]; %Cost function
x0 = [zeros(M+1,1);max(AD)+1]; %Starting values
x = lp(c,CC,AD,[],[],x0); %Call the LP
d = x(M+2); %delta or deviation
a = x(1:M+1); %Half impulse resp.
h = [a(M+1:-1:2);2*a(1);a(2:M+1)]./2; %Impulse response
This program has numerical problems for filters longer than 10 or 20 and is fairly slow. The lp() function uses an algorithm that seems not well suited to the equations required by filter design. It would be nice to have Meteor written in Matlab, both to show how the Simplex algorithm works, and to have an efficient LP filter design system in Matlab. The above program has been tested using Karmarkar's algorithm Entry 5, Entry 66, Entry 83 as implemented in Matlab by Lang Entry 35. It proved to be robust and reliable for lengths up to 100 or more. It was faster than the Matlab function but slower than Meteor or CPlex. Its use should be further investigated.
Direct use of quadratic programming and other optimization algorithms seem promising Entry 22, Entry 36, Entry 51, Entry 55, Entry 53, Entry 54, Entry 57, Entry 91, Entry 90, Entry 93
Chebyshev Approximations using the Exchange Algorithms
A very efficient algorithm which uses the results of the alternation theorem is called the Remez exchange algorithm. Remez Entry 63, Entry 16, Entry 52 showed that, under rather general conditions, an algorithm that takes a starting estimate of the location of the extremal frequencies and exchanges them with a new set calculated at each iteration will converge to the optimal Chebyshev approximation. The efficiency of this algorithm comes from finding the optimal solution by directly constructing a function that satisfies the alternation theorem rather than minimizing the Chebyshev error as done by the linear programming technique. The Remez exchange algorithm has proven to be well suited to the design of linear phase FIR filters Entry 44, Entry 47, Entry 32.
A particularly useful FIR filter design implementation of the Remez exchange is called the Parks-McClellan algorithm and is described in Entry 50, Entry 65, Entry 64, Entry 48. It has been implemented in Fortran in Entry 49, Entry 64, Entry 18, Entry 48 and in Matlab in a program at the end of this material. The Matlab program is particularly helpful in understanding how the algorithm works, however, because it does not use any special tricks, it is limited to lengths of 60 or so. Extensions and details can be found in Entry 45, Entry 13, Entry 21, Entry 67, Entry 33, Entry 24, Entry 25, Entry 68, Entry 70, Entry 69, Entry 4. This is a robust, efficient algorithm that significantly changed DSP when Parks and McClellan first described it in 1972 and has undergone important improvements. Examples are illustrated in Entry 64, Entry 46.
The Basic Parks-McClellan Formulation and Algorithm
Parks and McClellan formulated the basic Chebyshev FIR filter design
problem by specifying the desired amplitude response
|
Notice that if there is no transition band, i.e.
The alternation theorem states that the optimal approximation for this
problem will have an error function with
Parks and McClellan applied the Remez exchange algorithm Entry 50 to this
filter design problem by writing
These equations are solved for
The detailed steps of the Parks-McClellan algorithm are:
- Specify the ideal amplitude,
- Choose
- Calculate the cosine matrix at the current
- Using the
- Find
- If the largest error is the same as
- This iterative algorithm is guaranteed to converge to the unique optimal solution using almost any starting points in step 2.
This iterative procedure is called a multiple exchange algorithm because all of the extremal frequencies are up-dated each iteration. If only the frequency of the largest error is up-dated each iteration, it is called a single exchange algorithm which also converges but much more slowly. Some modification of the Parks-McClellan method or the Remez exchange algorithm will not converge as a multiple exchange, but will as a single exchange.
The Alternation theorem states that there will be a minimum of
It is interesting to note that at each iteration, the approximation is
optimal over that set of extremal frequencies and
At each iteration, the exchange of a proper set of extremal frequencies with alternating signs of the errors is always possible. One can show there will never be too few and if there are too many, one uses those corresponding to the largest errors.
In step 4 it is suggested that the amplitude response
In step 2 it is suggested that the simultaneous equation of (Equation 12) be
solved. Parks and McClellan Entry 49 use a more efficient and
numerically robust method of evaluating
For the low pass filter, this formulation always has an extremal frequency
at both pass and stop band edges,
The Parks-McClellan algorithm starts with fixed pass and stop band edges then minimizes a weighted form of the pass and stop band error ripple. In some cases it may be more appropriate to fix one of the ripples and minimize the other or to fix both ripples and minimize the transition band width. Indeed Schüssler, Hofstetter, Tufts, and others Entry 31, Entry 27, Entry 28, Entry 29 formulated some of these ideas before Parks and McClellan developed their algorithm. The DSP group at Rice has developed some modifications to these methods and they are presented below.
Examples of the Parks-McClellan Algorithm
Here we look at several examples of filters designed by the Parks-McClellan algorithm.
The examples here are length-15 with that shown in Figure 2a having a passband
|
It is possible to have ripples that do not touch the maximum value and, therefore, are not considered extremal points. That is illustrated in Figure 3a. The effects of a narrow transitionband are illustrated in Figure 3c. Note the zero locations for these filters and how they relate to the amplitude response.
|
To illustrate some of the unexpected behavior that optimal filter designs can have,
consider the bandpass filter amplitude response shown in Figure 4. Here
we have a length-31 Chebyshev bandpass filter with a stopband
|
The Modified Parks-McClellan Algorithm
If one wants to fix the pass band ripple and minimize the stop band ripple
Entry 70, equation (Equation 12) is changed so that the pass band ripple is
added to the appropriate top part of the vector