Chebyshev or Equal Ripple Error Approximation Filters 1.1 2008/06/09 13:27:26.300 GMT-5 2008/06/24 00:08:30.569 GMT-5 C. Sidney Burrus csb@rice.edu Daniel Collins Williamson dwilliamson1285@gmail.com C. Sidney Burrus csb@rice.edu 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 L∞ error results in an equal ripple error comes from the alternation theorem. This very powerful theorem allows one to minimize the Chebyshev error by directly constructing an equal ripple approximation with the proper number of ripples. That is the basis of several very effective algorithms, including the Remez exchange algorithm. 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 δp, the stopband ripple δs, and the transition bandwidth Δ=ωs-ωp, then one can fix or constrain any three of them and minimize the fourth. Or, as Parks and McClellan do, fix the band edges, ωp and ωs, and the ratio of δp and δs and minimize one of them. 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 . For FIR filter design, the Parks-McClellan formulation of the filter design problem and application of the Remez exchange algorithm is most commonly used , . It is a particularly interesting and powerful method that should be studied and understood to be fully utilized. Linear programming was used earlier , , 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 , , and linear programming's ability to allow a variety of constraints . Still another approach to achieving a Chebyshev approximation is to minimize the pth power of the error using a large value of p or to use an iterative scheme that solves a weighted least squared error with the weights at each stage determined by the error of the previous stage . Still another design method that produces an equal ripple error approximation uses a constrained least squared error criterion , which results in a Chebyshev solution if tight constraints are imposed. The early work by Herrmann and Schüssler , and the algorithm by Hofstetter, Oppenheim, and Siegel , posed and solved a similar problem but they had only approximate control of ωo (or ωp or ωs) and always achieved the “extra ripple" design. Given the proper specifications, the Parks-McClellan algorithm could design any filter that the Hofstetter-Oppenheim-Siegel algorithm could, but the opposite is not true. This seems to be one of the reasons the Hofstetter-Oppenheim-Siegel algorithm is not commonly used.

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 ε = max ω ∈ Ω | A ( ω ) - A d ( ω ) | where Ω is the union of the bands of frequencies that the approximation is over , . The approximation problem in filter design is to choose the filter coefficients to minimize ε. One way to minimize ε is to set up the frequency response in four equations for the four types of linear phase FIR filters as done in (), (), and the corresponding sine expressions. An alternative approach uses the fact that all four can be obtained from the odd-length, even-symmetry type 1 and uses only (). From one of these frequency response representations together with powerful Alternation Theorem several optimization schemes can be developed. If the amplitude response for odd L is expressed as a sum of R cosine terms A ( ω ) = ∑ n = 0 R - 1 a ( n ) cos ( ω n ) or for even L A ( ω ) = ∑ n = 1 R a ( n ) cos ( ω ( n - 1 / 2 ) ) with R=M+1=L+12 for odd length-L and R=L/2 for even length-L, as derived in () and (), then Theorem 1 If A(ω) is the linear combination of R cosine functions given in () or (), the necessary and sufficient conditions for A(ω) to be the least Chebyshev error approximation to Ad(ω) over ω∈Ω are: The error function, ϵ(ω)=A(ω)-Ad(ω) have at leastR+1 extremal frequencies in Ω. The extremal frequencies are ordered points ω1<ω2<⋯<ωR+1 such that ϵ(ωk)=-ϵ(ωk+1) and maxω∈Ω|ϵ(ω)|=|ϵ(ωk)| for k=1,2,⋯,R+1. The alternation theorem , states that the minimum Chebyshev error has at least R+1 extremal frequencies. This is stated mathematically by A ( ω k ) = A d ( ω k ) + ( - 1 ) k δ for k=0,1,2,⋯,R, where the ωk are the ordered extremal frequencies where the equal ripple error has maximum value. In other words, the optimal solution to the linear phase FIR filter design problem will have an equal ripple error function with a required number of ripples. How all of these characteristics relate can be rather complicated and good designs require experience . When applied to other approximation problems, care must be taken to ensure the approximating functions satisfy the “Haar conditions" or other restrictions , , , .

Chebyshev Approximation by Linear Programming It is possible to pose the Chebyshev approximation problem in filter design as a linear programming optimization problem , , , . The error definition in () can be written as an inequality by A d ( ω ) - δ ≤ A ( ω ) ≤ A d ( ω ) + δ where the scalar δ is minimized. The inequalities in () can be written as A ≤ A d + δ - A ≤ - A d + δ or A - δ ≤ A d - A - δ ≤ - A d which can be combined into one matrix inequality using () by C - 1 - C - 1 a δ ≤ A d - A d . If δ is minimized, the optimal Chebyshev approximation is achieved. This is done by minimizing ε = 0 0 ⋯ 1 a δ which, together with the inequality of (), is in the form of the dual problem in linear programming , , . This can be solved using the lp() command from the Optimization Toolbox with Matlab , the Meteor software system , CPlex , or Karmarkar's algorithm , . 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 (,) 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 , , as implemented in Matlab by Lang . 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 , , , , , , , , ,

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 , , 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 , , . A particularly useful FIR filter design implementation of the Remez exchange is called the Parks-McClellan algorithm and is described in , , , . It has been implemented in Fortran in , , , 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 , , , , , , , , , , . 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 , .

The Basic Parks-McClellan Formulation and Algorithm Parks and McClellan formulated the basic Chebyshev FIR filter design problem by specifying the desired amplitude response A(ω) and the transition band edges, then minimizing the weighted Chebyshev error over the pass and stop bands. For the basic lowpass filter illustrated in , the pass band edge ωp and the stop band edge ωs are specified, the maximum passband error is related to the maximum stop band error by δp=Kδs and they are minimized.

Amplitude Response of a Length-15 Optimal Chebyshev Filter

Notice that if there is no transition band, i.e. ωp=ωs, that δp+δs=1 and no minimization is possible. While not the case for a least squares approximation, a transition band is necessary for the Chebyshev approximation problem to be well-posed. The effects of a small transition band are large pass and stopband ripple as illustrated in b. The alternation theorem states that the optimal approximation for this problem will have an error function with R+1 extremal points with alternating signs. The theorem also states that there exists R+1 frequencies such that, if the Chebyshev error at those frequencies are equal and alternate in sign, it will be minimized over the pass band and stop band. Note that there are nine extremal points in the length-15 example shown in , counting those at the band edges in addition to those that are interior to the pass and stopbands. For this case, R=(L+1)/2 which agree with the example. Parks and McClellan applied the Remez exchange algorithm to this filter design problem by writing R+1 equations using () and () evaluated at the R+1 extremal frequencies with R unknown cosine parameters a(n) and the unknown ripple value, δ. In matrix form this becomes A d ( ω 0 ) A d ( ω 1 ) A d ( ω 2 ) A d ( ω 3 ) ⋮ A d ( ω R ) = cos ( ω 0 0 ) cos ( ω 0 1 ) ⋯ cos ( ω 0 ( R - 1 ) ) 1 cos ( ω 1 0 ) cos ( ω 1 1 ) ⋯ cos ( ω 1 ( R - 1 ) ) - 1 cos ( ω 2 0 ) cos ( ω 2 1 ) ⋯ cos ( ω 2 ( R - 1 ) ) 1 cos ( ω 3 0 ) cos ( ω 3 1 ) ⋯ cos ( ω 3 ( R - 1 ) ) - 1 ⋮ ⋮ cos ( ω R 0 ) cos ( ω R 1 ) ⋯ cos ( ω R M ) ± 1 a ( 0 ) a ( 1 ) a ( 2 ) ⋮ a ( R - 1 ) δ . These equations are solved for a(n) and δ using an initial guess as to the location of the extremal frequencies ωi. This design is optimal but only over the guessed frequencies, and we want optimality over all of the pass and stopbands. Therefore, the amplitude response of the filter is calculated over a dense set of frequency samples using () and a new set of estimates of the extremal frequencies is found from the local minima and maxima and these are used to replace the initial guesses (they are exchanged). This process is iteratively performed until the guaranteed convergence is achieved and the optimal filter is designed. The detailed steps of the Parks-McClellan algorithm are: Specify the ideal amplitude, Ad(ω), the stop and pass band edges, ωp and ωs, the error weight K where δp=Kδs, and the length L. Choose R+1 initial guesses for the extremal frequencies, ωi, in the bands of approximation, Ω. This is often done uniformly over the pass and stop bands, including ω=0,ωp,ωs, and π. Calculate the cosine matrix at the current ωi and solve () for a(n) and δ which are optimal over these current extremal frequencies, ωi. Using the a(n) or the equivalent h(n) from step 3, evaluate A(ω) over a dense set of frequencies. This amplitude response will interpolate A(ωi)=Ad(ωi)±δ at the extremal frequencies. Find R+1 new extremal frequencies where the error has a local maximum or minimum and has alternating sign. This includes the band edges. If the largest error is the same as δ found in step 3, then convergence has occured and the optimal filter has been designed, otherwise, exchange the old extremal frequencies ωi used in step 2 and return to step 3 for the next iteration. 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 R+1 extremal frequencies, even for multiband designs with arbitrary Ad(ω). If Ad(ω) is piece-wise constant with T transition bands, one can derive the maximum possible number of extremal frequencies and it is R+2T. This comes from the maximum number of maxima and minima that a function of the form () or () can have plus two at the edges of each transition band. For a simple lowpass filter with one passband, one transition band, and one stopband, there will be a minimum of R+1 extremal frequencies and a maximum of R+2. For a bandpass filter, the maximum is R+4. If a design has more than the minimum number of extremal frequencies, it is called an extra ripple design. If it has the maximum number, it is called a maximum ripple design. It is interesting to note that at each iteration, the approximation is optimal over that set of extremal frequencies and δ increased over the previous iteration. At convergence, δ has increased to the maximum error over Ω and that is the minimum Chebyshev error. 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 A(ω) be calculated over a dense grid in the pass and stopbands and in step 5 the local extremes are found by searching over this dense grid. There are more accurate methods that use bisection methods and/or Newton's method to find the extremal points. In step 2 it is suggested that the simultaneous equation of () be solved. Parks and McClellan use a more efficient and numerically robust method of evaluating δ using a form of Cramer's rule. With that δ, an interpolation method can be used to find a(n). This is faster and allows longer filters to be designed than with the linear algebra based approach described here. For the low pass filter, this formulation always has an extremal frequency at both pass and stop band edges, ωp and ωs, and at ω=0 and/or at ω=π. The extra ripple filter has R+2 extremal frequencies including both zero and pi. If this algorithm is started with an incorrect number of extremal frequencies in the stop or pass band, the iterations will correct this. It is interesting and informative to plot the frequency response of the filters designed at each iteration of this algorithm and observe how the correction takes place. 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 , , , 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 a having a passband 0<f<0.3, a transition band 0.3<f<0.5, and a stopband 0.5<f<1. The number of cosine terms in the frequency response formula is R=8, therefore, the alternation theorem says we must have at least R+1 extremal points. There are four in the passband, counting the one at zero frequency, the minimum, the maximum, and the minimum at the bandedge. There are five in the stopband, counting the ones at the bandedge and at f=1. So, the number is nine which is at least R+1. However, in c, there are ten extremal points but that is also at least 9, so it also is optimal. For a low pass filter, the maximum number of extremal points is R+2 and that is what this filter has. This special case is called the “maximum ripple" case.

Amplitude Response of Length-15 Optimal Chebyshev Filters

It is possible to have ripples that do not touch the maximum value and, therefore, are not considered extremal points. That is illustrated in a. The effects of a narrow transitionband are illustrated in c. Note the zero locations for these filters and how they relate to the amplitude response.

Amplitude Response of Length-15 Optimal Chebyshev Filters

To illustrate some of the unexpected behavior that optimal filter designs can have, consider the bandpass filter amplitude response shown in . Here we have a length-31 Chebyshev bandpass filter with a stopband 0<f<0.2, a transition band 0.2<f<0.25, a passband 0.25<f<0.5, another transitionband 0.5<f<0.68, and a stopband 0.68<f<1. The asymmetric transition bands cause large response in the transition band around f=0.6. However, this filter is optimal since the deviation occurs in part of the frequency band that is not included in the optimization criterion. If you think you don't care what happens in the transition bands, you may change your mind with this kind of behavior.

Amplitude Response of Length-31 Optimal Chebyshev Bandpass Filter

The Modified Parks-McClellan Algorithm If one wants to fix the pass band ripple and minimize the stop band ripple , equation () is changed so that the pass band ripple is added to the appropriate top part of the vector Ad of the desired response and the unknown stop band is kept in the lower part of the last column of the cosine matrix C. A d ( ω 0 ) A d ( ω 1 ) ⋮ A d ( ω p ) A d ( ω s ) ⋮ A d ( ω R ) + δ p - δ p ⋮ ± δ p 0 ⋮ 0 = cos ( ω 0 0 ) cos ( ω 0 1 ) ⋯ cos ( ω 0 ( R - 1 ) ) 0 cos ( ω 1 0 ) cos ( ω 1 1 ) ⋯ cos ( ω 1 ( R - 1 ) ) 0 ⋮ ⋮ cos ( ω p 0 ) cos ( ω p 1 ) ⋯ cos ( ω p ( R - 1 ) ) 0 cos ( ω s 0 ) cos ( ω s 1 ) ⋯ cos ( ω s ( R - 1 ) ) 1 ⋮ ⋮ cos ( ω R 0 ) cos ( ω R 1 ) ⋯ cos ( ω R ( R - 1 ) ) ± 1 a ( 0 ) a ( 1 ) a ( 2 ) ⋮ a ( R - 1 ) δ s . Iteration of this equation will keep the pass band ripple δp fixed and minimize the stop band ripple δs. A problem with convergence occurs if one of the δ's becomes negative during the iterations. A modification to the basic exchange has been developed to give reliable convergence .

The Hofstetter, Oppenheim, and Siegel Algorithm This algorithm , , came into existence in order to design the filters posed by Herrmann and Schüssler , where both the pass and stop band ripple sizes, δp and δs, are fixed and the location of the transition band is not directly controlled. This problem results in a maximum ripple design which, for the lowpass filter, requires extremal frequencies at both ω=0 and ω=π but does not use either pass or stop band frequencies ωp or ωs. This results in R extremal frequencies giving R equations to find the R values of a(n). A d ( ω 0 ) A d ( ω 1 ) ⋮ A d ( ω p - 1 ) A d ( ω s + 1 ) ⋮ A d ( ω R - 1 ) + δ p - δ p ⋮ ± δ p δ s ⋮ ± δ s = cos ( ω 0 0 ) cos ( ω 0 1 ) ⋯ cos ( ω 0 ( R - 1 ) ) cos ( ω 1 0 ) cos ( ω 1 1 ) ⋯ cos ( ω 1 ( R - 1 ) ) ⋮ ⋮ cos ( ω p - 1 0 ) cos ( ω p - 1 1 ) ⋯ cos ( ω p - 1 ( R - 1 ) ) cos ( ω s + 1 0 ) cos ( ω s + 1 1 ) ⋯ cos ( ω s + 1 ( R - 1 ) ) ⋮ ⋮ cos ( ω R - 1 0 ) cos ( ω R - 1 1 ) ⋯ cos ( ω R - 1 ( R - 1 ) ) a ( 0 ) a ( 1 ) a ( 2 ) ⋮ a ( R - 1 ) . This algorithm is iterated as a multiple exchange, keeping the number of ripples in the pass and stop band constant, to give an optimal extra ripple filter. The location and width of the transition band is controlled only by the choice of how the number of initial ripples are divided between the pass and stop band. The final filter may not have the transition located where you want it. Indeed, no solution may exist with the desired location of the transition band. The designs produced by the HOS algorithm are always maximum ripple but this comes with a loss of accurate control over the location of the transition band. The algorithm is not, strictly speaking, an optimization algorithm. It is an interpolation algorithm. The Chebyshev error is not minimized, the designed amplitude interpolates the specified error ripples. However, although not directly minimized, the transition band width of these designs seems to be minimized , , . Extra or maximum ripple designs seem to be efficient in using all the zeros to produce small ripple size and narrow transition bands, however, the loss of accurate control over the location of the transition bands becomes even more problematic with multiple transition band designs. Perhaps some compromise methods can be devised that use some of the efficiency of the maximum ripple approximations with some of the control of other methods. The next two design methods are of that type.

The Shpak and Antoniou Algorithm Shpak and Antoniou propose decoupling the size of the pass and stopband ripple sizes in order to have control over the pass and stop band edges and have an extra ripple design. The Parks-McClellan design has the ripple sizes related with a fixed weight δp=Kδs, the modified Parks-McClellan design fixes one ripple size and minimizes the other, the Hoffstetter, Oppenheim, and Siegel design fixes both ripple sizes but cannot set the transition band edges. The Shpak-Antoniou design fixes the transition band edges and gives a maximum ripple design with minimum ripple but the relationship of the pass and stopband ripple is uncontrolled. This method has two ripple sizes, δp and δs, appended to the a(n) vector similar to the single δ used in () or (). This allows controlling an additional extremal frequency and results in an extra ripple approximation. This can become somewhat complicated for multiple transition bands but seems very flexible .

The New Equal Ripple Design Formulation and Exchange Algorithm Because the arguments in the Weisburn, Parks, and Shenoy paper require the assumption of no signal or noise energy in the transition band, it is now more obvious that a narrow transition band is very desirable. For this reason it may be better to fix the pass and stop band peak error, δp and δs and the transition band center frequency ωo then minimize the transition band width rather than fixing the pass and stop band edges, ωp and ωs, then minimizing δp and δs. Two methods have been recently developed to address this point of view. The first is a new exchange algorithm that is in some ways a combination of the Parks-McClellan and Hofstetter-Oppenheim-Segiel algorithms and the second is a limiting case for a constrained least squares method based on Lagrange multipliers , , , using tight constraints. For problems where the signal and noise spectra are such that a specific frequency ωo that separates the desired passband from the desired stopband can be specified but specific separate transition band edges, ωp<ωs, cannot, we formulate a design method where the pass and stop band ripple sizes, δp and δs are specified along with the separation frequency, ωo. The algorithm described below will interpolate the specified ripple sizes exactly (as the HOS algorithm does) but will allow exact control over the location of ωo by not requiring maximum ripple. Although not set up to be an optimization procedure, it seems to minimize the transition band width. This formulation suits problems where there is no obvious transition band (“don't care band") having no signal or noise energy to be passed or rejected. The optimal Chebyshev filter designed with this new algorithm is generally not extra ripple and, therefore, will have an extremal frequency at ω=0 or ω=π as the Parks-McClellan formulation does. Because we are trying to minimizing the transition band width, we do not specify both the edges, ωp and ωs, but only one of them or, perhaps, the center of the transition band, ωo. This results in R equations which are used to find the R coefficients a(n). The equations are formulated by adding the alternating peak pass and stop band ripples to the Ad in () and not having the special last column of C nor the unknown δ appended to a as was done by Parks and McClellan in (). The resulting equation to be iterated in our new exchange algorithm has the form A d ( ω 0 ) A d ( ω 1 ) ⋮ A d ( ω o ) A d ( ω s + 1 ) ⋮ A d ( ω R - 1 ) + δ p - δ p ⋮ 0 δ s ⋮ ± δ s = cos ( ω 0 0 ) cos ( ω 0 1 ) ⋯ cos ( ω 0 ( R - 1 ) ) cos ( ω 1 0 ) cos ( ω 1 1 ) ⋯ cos ( ω 1 ( R - 1 ) ) ⋮ ⋮ cos ( ω o ) cos ( ω o 1 ) ⋯ cos ( ω o ( R - 1 ) ) cos ( ω s + 1 0 ) cos ( ω s + 1 1 ) ⋯ cos ( ω s + 1 ( R - 1 ) ) ⋮ ⋮ cos ( ω R - 1 0 ) cos ( ω R - 1 1 ) ⋯ cos ( ω R - 1 ( R - 1 ) ) a ( 0 ) a ( 1 ) a ( 2 ) ⋮ a ( ( R - 1 ) ) . The exchange algorithm is done as by Parks and McClellan finding new extremal frequencies at each iteration, but with fixed ripple sizes in both pass and stop bands. This new algorithm reduces the transition band width as done by the Hofstetter, Oppenheim, and Siegel method but with the transition band location controlled and without requiring the extra ripple solution. Note that any transition band frequency could be fixed. It could be Ad(ωo)=1/2 to fix the half-power point. It could be Ad(ωp)=1-δp to fix the pass band edge. Or it could be A<