Skip to content Skip to navigation

OpenStax_CNX

You are here: Home » Content » Chebyshev or Equal Ripple Error Approximation Filters

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • NSF Partnership display tagshide tags

    This module is included inLens: NSF Partnership in Signal Processing
    By: Sidney BurrusAs a part of collection: "Digital Signal Processing and Digital Filter Design (Draft)"

    Click the "NSF Partnership" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

  • Featured Content

    This module is included inLens: Connexions Featured Content
    By: ConnexionsAs a part of collection: "Digital Signal Processing and Digital Filter Design (Draft)"

    Click the "Featured Content" link to see all content affiliated with them.

Also in these lenses

  • UniqU content

    This module is included inLens: UniqU's lens
    By: UniqU, LLCAs a part of collection: "Digital Signal Processing and Digital Filter Design (Draft)"

    Click the "UniqU content" link to see all content selected in this lens.

  • Lens for Engineering

    This module is included inLens: Lens for Engineering
    By: Sidney Burrus

    Click the "Lens for Engineering" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

Chebyshev or Equal Ripple Error Approximation Filters

Module by: C. Sidney Burrus. E-mail the author

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 LL 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δp, the stopband ripple δsδs, and the transition bandwidth Δ=ωs-ωpΔ=ω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ωp and ωsωs, and the ratio of δpδp and δsδ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 [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 [48], [50]. It is a particularly interesting and powerful method that should be studied and understood to be fully utilized.

Linear programming was used earlier [87], [26], [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 [83], [5], and linear programming's ability to allow a variety of constraints [80].

Still another approach to achieving a Chebyshev approximation is to minimize the pthpth power of the error using a large value of pp 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 [11]. Still another design method that produces an equal ripple error approximation uses a constrained least squared error criterion [78], [76] which results in a Chebyshev solution if tight constraints are imposed.

The early work by Herrmann and Schüssler [27], [31] and the algorithm by Hofstetter, Oppenheim, and Siegel [28], [29] posed and solved a similar problem but they had only approximate control of ωoωo (or ωpωp or ωsω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 ( ω ) | ε = max ω Ω | A ( ω ) - A d ( ω ) |
(1)

where ΩΩ is the union of the bands of frequencies that the approximation is over [16], [20]. 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 Equation 34 from FIR Digital Filters, Equation 40 from FIR Digital Filters, and the corresponding sine expressions. An alternative approach [48] uses the fact that all four can be obtained from the odd-length, even-symmetry type 1 and uses only Equation 34 from FIR Digital Filters. 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 RR cosine terms

A ( ω ) = n = 0 R - 1 a ( n ) cos ( ω n ) A ( ω ) = n = 0 R - 1 a ( n ) cos ( ω n )
(2)

or for even L

A ( ω ) = n = 1 R a ( n ) cos ( ω ( n - 1 / 2 ) ) A ( ω ) = n = 1 R a ( n ) cos ( ω ( n - 1 / 2 ) )
(3)

with R=M+1=L+12R=M+1=L+12 for odd length-LL and R=L/2R=L/2 for even length-LL, as derived in Equation 34 from FIR Digital Filters and Equation 40 FIR Digital Filters, then

Theorem 1

If A(ω)A(ω) is the linear combination of RR cosine functions given in Equation 2 or Equation 3, the necessary and sufficient conditions for A(ω)A(ω) to be the least Chebyshev error approximation to Ad(ω)Ad(ω) over ωΩωΩ are: The error function, ϵ(ω)=A(ω)-Ad(ω)ϵ(ω)=A(ω)-Ad(ω) have at leastR+1R+1 extremal frequencies in ΩΩ. The extremal frequencies are ordered points ω1<ω2<<ωR+1ω1<ω2<<ωR+1 such that ϵ(ωk)=-ϵ(ωk+1)ϵ(ωk)=-ϵ(ωk+1) and maxωΩ|ϵ(ω)|=|ϵ(ωk)|maxωΩ|ϵ(ω)|=|ϵ(ωk)| for k=1,2,,R+1k=1,2,,R+1.

The alternation theorem [48], [52] states that the minimum Chebyshev error has at least R+1R+1 extremal frequencies. This is stated mathematically by

A ( ω k ) = A d ( ω k ) + ( - 1 ) k δ A ( ω k ) = A d ( ω k ) + ( - 1 ) k δ
(4)

for k=0,1,2,,Rk=0,1,2,,R, where the ωkω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 [30]. When applied to other approximation problems, care must be taken to ensure the approximating functions satisfy the “Haar conditions" or other restrictions [16], [50], [20], [52].

Chebyshev Approximation by Linear Programming

It is possible to pose the Chebyshev approximation problem in filter design as a linear programming optimization problem [62], [89], [81], [41]. The error definition in Equation 1 can be written as an inequality by

A d ( ω ) - δ A ( ω ) A d ( ω ) + δ A d ( ω ) - δ A ( ω ) A d ( ω ) + δ
(5)

where the scalar δδ is minimized.

The inequalities in Equation 5 can be written as

A A d + δ A A d + δ
(6)
- A - A d + δ - A - A d + δ
(7)

or

A - δ A d A - δ A d
(8)
- A - δ - A d - A - δ - A d
(9)

which can be combined into one matrix inequality using Equation 48 from FIR Digital Filters by

C - 1 - C - 1 a δ A d - A d . C - 1 - C - 1 a δ A d - A d .
(10)

If δδ is minimized, the optimal Chebyshev approximation is achieved. This is done by minimizing

ε = 0 0 1 a δ ε = 0 0 1 a δ
(11)

which, together with the inequality of Equation 10, is in the form of the dual problem in linear programming [19], [43], [82].

This can be solved using the lp() command from the Optimization Toolbox with Matlab [23], the Meteor software system [80], CPlex [7], or Karmarkar's algorithm [5], [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 [5], [66], [83] as implemented in Matlab by Lang [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 [22], [36], [51], [55], [53], [54], [57], [91], [90], [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 [63], [16], [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 [44], [47], [32].

A particularly useful FIR filter design implementation of the Remez exchange is called the Parks-McClellan algorithm and is described in [50], [65], [64], [48]. It has been implemented in Fortran in [49], [64], [18], [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 [45], [13], [21], [67], [33], [24], [25], [68], [70], [69], [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 [64], [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 A(ω)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 Figure 1, the pass band edge ωpωp and the stop band edge ωsωs are specified, the maximum passband error is related to the maximum stop band error by δp=Kδsδp=Kδs and they are minimized.

Figure 1: Amplitude Response of a Length-15 Optimal Chebyshev Filter
Figure 1 is a graph titled Length-15 Optimal Chebyshev FIR Filter. The horizontal axis is labeled Normalized Frequency and ranges in value from 0 to 1 in increments of 0.2. The vertical axis is labeled Amplitude Response, A and ranges in value from 0 to 1 in increments of 0.2. The curve on the graph is broken up into three segments. The first, which is a sinusoidal section around vertical value 1 and from 0 to 0.3 horizontally. The horizontal width of this segment is labeled passband. After this segment, from 0.3 to 0.5 is a segment with a large, smooth continuation of the curve with negative slope bringing the curve from (0.3, 1) to (0.5, 0). The width of this section is labeled transitionband. The final section is another sinusoidal segment of the same amplitude as the passband section and a slightly longer wavelength. This section continues to the right edge of the figure along the horizontal axis, and it is labeled stopband.

Notice that if there is no transition band, i.e. ωp=ωsωp=ωs, that δp+δs=1δ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 Figure 3b.

The alternation theorem states that the optimal approximation for this problem will have an error function with R+1R+1 extremal points with alternating signs. The theorem also states that there exists R+1R+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 Figure 1, counting those at the band edges in addition to those that are interior to the pass and stopbands. For this case, R=(L+1)/2R=(L+1)/2 which agree with the example.

Parks and McClellan applied the Remez exchange algorithm [50] to this filter design problem by writing R+1R+1 equations using Equation 37 from FIR Digital Filters and Equation 1 from Design of IIR Filters by Frequency Transformations evaluated at the R+1R+1 extremal frequencies with RR unknown cosine parameters a(n)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 ) δ . 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 ) δ .
(12)

These equations are solved for a(n)a(n) and δδ using an initial guess as to the location of the extremal frequencies ωiω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 Equation 34 from FIR Digital Filters 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:

  1. Specify the ideal amplitude, Ad(ω)Ad(ω), the stop and pass band edges, ωpωp and ωsωs, the error weight KK where δp=Kδsδp=Kδs, and the length LL.
  2. Choose R+1R+1 initial guesses for the extremal frequencies, ωiωi, in the bands of approximation, ΩΩ. This is often done uniformly over the pass and stop bands, including ω=0,ωp,ωs,ω=0,ωp,ωs, and ππ.
  3. Calculate the cosine matrix at the current ωiωi and solve Equation 12 for a(n)a(n) and δδ which are optimal over these current extremal frequencies, ωiωi.
  4. Using the a(n)a(n) or the equivalent h(n)h(n) from step 3, evaluate A(ω)A(ω) over a dense set of frequencies. This amplitude response will interpolate A(ωi)=Ad(ωi)±δA(ωi)=Ad(ωi)±δ at the extremal frequencies.
  5. Find R+1R+1 new extremal frequencies where the error has a local maximum or minimum and has alternating sign. This includes the band edges.
  6. 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ωi used in step 2 and return to step 3 for the next iteration.
  7. 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+1R+1 extremal frequencies, even for multiband designs with arbitrary Ad(ω)Ad(ω). If Ad(ω)Ad(ω) is piece-wise constant with TT transition bands, one can derive the maximum possible number of extremal frequencies and it is R+2TR+2T. This comes from the maximum number of maxima and minima that a function of the form Equation 2 or Equation 3 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+1R+1 extremal frequencies and a maximum of R+2R+2. For a bandpass filter, the maximum is R+4R+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(ω)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 Equation 12 be solved. Parks and McClellan [49] 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)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ωp and ωsωs, and at ω=0ω=0 and/or at ω=πω=π. The extra ripple filter has R+2R+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 [31], [27], [28], [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 0<f<0.30<f<0.3, a transition band 0.3<f<0.50.3<f<0.5, and a stopband 0.5<f<10.5<f<1. The number of cosine terms in the frequency response formula is R=8R=8, therefore, the alternation theorem says we must have at least R+1R+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=1f=1. So, the number is nine which is at least R+1R+1. However, in Figure 2c, 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+2R+2 and that is what this filter has. This special case is called the “maximum ripple" case.

Figure 2: Amplitude Response of Length-15 Optimal Chebyshev Filters
Figure two contains four graphs. The two graphs on the left side contain horizontal axes labeled Normalized frequency, numbered from 0 to 1 in increments of 0.5, and vertical axes labeled Amplitude Response, A, numbered from 0 to 1 in increments of 0.2. The top graph on the left is labeled optimal chebyshev FIR filter. The bottom graph on the left is labeled Maximum ripple chebyshev filter. Both graphs contain a curve that consists of three sections. The first section is a sinusoidal section of one complete wave centered along the vertical value of 1. These waves continue to a horizontal value of approximately 0.3. The bottom-left graph's waves have a greater amplitude than those of the top-left graph. The next section is downward sloping portion of the curve after the final peak of the first section, where it moves from approximately (0.3, 1.1) to (0.5, 0). The third section continues smoothly from the end of the second with another sinusoidal segment  with two complete waves centered about the horizontal axis. Again, the bottom-left graph's waves are larger in amplitude than the waves of the graph above. On the right, the two graphs have horizontal axes labeled real part of z, ranging in value from -2 to 2, and vertical axes labeled imaginary part of z, ranging in value from -1.5 to 1.5. Both graphs on the right consist of a circle of radius 1 centered about the origin, and various small circles at points in, on, and around the circle. The top-right graph is labeled Zero Location. On the big circle, there are eight unevenly-spaced small circles on the left half.  Beginning inside the circle, and extending outside the circle, there are five small circles that form a V-shape opening to the right. The bottom-right graph is also labeled zero location. This graph has small circles in roughly the same spots as the graph above, except that it has two extra small cirlces on the big circle, and does not contain the vertex of the v-shaped array of circles.

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.

Figure 3: Amplitude Response of Length-15 Optimal Chebyshev Filters
Figure three contains four graphs. The two graphs on the left side contain horizontal axes labeled Normalized frequency, numbered from 0 to 1 in increments of 0.5, and vertical axes labeled Amplitude Response, A, numbered from 0 to 1 in increments of 0.2. The top graph on the left is labeled optimal chebyshev FIR filter. The bottom graph on the left is labeled Chebyshev Filter with Narrow TB. Both graphs contain a curve that consists of three sections. The first section is a sinusoidal section of one complete wave centered along the vertical value of 1. These waves continue to a horizontal value of approximately 0.3. The bottom-left graph's waves have a much greater amplitude than those of the top-left graph, and only completes one-half of a wave. The next section is downward sloping portion of the curve after the final peak of the first section, where it moves from approximately (0.3, 1.1) to (0.5, 0). The third section continues smoothly from the end of the second with another sinusoidal segment  with two complete waves centered about the horizontal axis. Again, the bottom-left graph's waves are larger in amplitude than the waves of the graph above. On the right, the two graphs have horizontal axes labeled real part of z, ranging in value from -2 to 2, and vertical axes labeled imaginary part of z, ranging in value from -1.5 to 1.5. Both graphs on the right consist of a circle of radius 1 centered about the origin, and various small circles at points in, on, and around the circle. The top-right graph is labeled Zero Location. On the big circle, there are ten unevenly-spaced small circles on the left half.  Beginning inside the circle, and extending outside the circle, there are four small circles that form a V-shape opening to the right. The bottom-right graph is also labeled zero location. This graph has small circles in roughly the same spots as the graph above, except that its ten circles on the big circle are spread out over the left two-thirds. Also, instead of a v-shaped array, the graph has two small overlapping circles inside the right half of the big circle, and two small circles tangent to each other along the horizontal axis of the graph outside the big circle to the right.

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 0<f<0.20<f<0.2, a transition band 0.2<f<0.250.2<f<0.25, a passband 0.25<f<0.50.25<f<0.5, another transitionband 0.5<f<0.680.5<f<0.68, and a stopband 0.68<f<10.68<f<1. The asymmetric transition bands cause large response in the transition band around f=0.6f=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.

Figure 4: Amplitude Response of Length-31 Optimal Chebyshev Bandpass Filter
Figure four contains two graphs. Graph a is titled Optimal Chebyshev Bandpass Filter. The horizontal axis is labeled Normalized Frequency and ranges in value from 0 to 1 in increments of 0.2. The vertical axis is labeled Amplitude Response, A, and ranges in value from -1.5 to 1 in increments of 0.5. The curve begins just below the horizontal axis, first slightly downward to a small trough at approximately (0.05, -0.1). A small peak at (0.1, 0.1) follows, along with another trough at approximately (0.2, -0.1). The curve then moves sharply upward to a series of three peaks and two troughs around the vertical value 1, and horizontally from 0.2 to 0.5. After the third peak, the curve moves sharply downward to the bottom of the graph, with a trough at (0.6, -1.6). After the trough, the graph moves towards the horizontal axis and finishes with three peaks and curves of an amplitude of 0.1, then finally terminating along this pattern at the right edge of the graph. Graph b is titled Zero location. The horizontal axis is labeled Real Part of Z and ranges in value from -2 to 2 in increments of 1. The vertical axis is labeled Imaginary part of Z, and ranges in value from -1.5 to 1.5 in increments of 0.5. The graph consists of a large circle of radius 1 centered at the origin, with 30 small circles mostly falling on or around the edge of the circle. The leftmost third of the circle contains 12 of the small circles. They are closely fitted together, although not uniformly spaced, and they all are positioned on the edge of the circle. Around (0, 1) and (0, -1) are two groups of five circles, with one in each group positioned on the edge of the circle, two positioned inside the circle, and two positioned on the outside. On the rightmost third of the big circle are the remaining small circles, with all but two positioned on the edge of the big circle, and the remaining two positioned tangent to the big circle on the inside and outside around point (1, 0).

The Modified Parks-McClellan Algorithm

If one wants to fix the pass band ripple and minimize the stop band ripple [70], equation Equation 12 is changed so that the pass band ripple is added to the appropriate top part of the vector AdAd of the desired response and the unknown stop band is kept in the lower part of the last column of the cosine matrix CC.

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 . 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 .
(13)

Iteration of this equation will keep the pass band ripple δpδp fixed and minimize the stop band ripple δsδ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 [70].

The Hofstetter, Oppenheim, and Siegel Algorithm

This algorithm [28], [29], [70] came into existence in order to design the filters posed by Herrmann and Schüssler [31], [27] where both the pass and stop band ripple sizes, δpδp and δsδ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ω=0 and ω=πω=π but does not use either pass or stop band frequencies ωpωp or ωsωs. This results in RR extremal frequencies giving RR equations to find the RR values of a(n)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 ) . 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 ) .
(14)

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 [65], [61], [64]. 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 [67] 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δ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δp and δsδs, appended to the a(n)a(n) vector similar to the single δδ used in Equation 12 or Equation 13. 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 [4].

The New Equal Ripple Design Formulation and Exchange Algorithm

Because the arguments in the Weisburn, Parks, and Shenoy paper [94] 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δp and δsδs and the transition band center frequency ωoωo then minimize the transition band width rather than fixing the pass and stop band edges, ωpωp and ωsωs, then minimizing δpδp and δsδ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 [63] and the second is a limiting case for a constrained least squares method based on Lagrange multipliers [15], [77], [78], [76] using tight constraints.

For problems where the signal and noise spectra are such that a specific frequency ωoωo that separates the desired passband from the desired stopband can be specified but specific separate transition band edges, ωp<ωsωp<ωs, cannot, we formulate [70] a design method where the pass and stop band ripple sizes, δpδp and δsδs are specified along with the separation frequency, ωoω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ω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ω=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ωp and ωsωs, but only one of them or, perhaps, the center of the transition band, ωoωo. This results in RR equations which are used to find the RR coefficients a(n)a(n). The equations are formulated by adding the alternating peak pass and stop band ripples to the AdAd in Equation 12 and not having the special last column of CC nor the unknown δδ appended to aa as was done by Parks and McClellan in Equation 12. 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 ) ) . 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 ) ) .
(15)

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/2Ad(ωo)=1/2 to fix the half-power point. It could be Ad(ωp)=1-δpAd(ωp)=1-δp to fix the pass band edge. Or it could be Ad(ωs)=δsAd(ωs)=δs to fix the stop band edge.

Extending this formulation and algorithm to the multiple transition band case complicates the problem as the solution may not be unique or may have anomalous behavior in one of the transition bands. Details of the solution to this problem are given in [70].

Estimations of , the Length of Optimal Chebyshev FIR Filters

All of the design methods discussed so far have assumed that NN,the length of the filter, is given as part of the secifications. In many cases, perhaps even most, NN is a parameter that we would like to minimize. Often specifications are to meet certain pass and stopband ripple specifications with given pass and stopband edges and with the shortest possible filter. None of our methods will do that. Indeed, it is not clear how to do that kind of optimization other than by some sort of search. In other words, design a set of filters of different lengths and choose the one that meet the specifications with minimum length.

Fortunately, emperical formulas have been derived that give a good estimate of the relationship of the length of an optimal Chebyshev FIR filter for given pass and stopband ripple and transition band edges [64], [65]. Kaiser's formula is

N = - 20 log 10 ( δ p δ s ) - 13 14 . 6 ( f s - f p ) + 1 N = - 20 log 10 ( δ p δ s ) - 13 14 . 6 ( f s - f p ) + 1
(16)

and it is fairly accurate for average filter specifications (neither wide nor narrow bands).

Examples of Optimal Chebyshev Filters

In order to better understand the nature of an optimal Chebyshev and to see the power of the Parks-McClellan algorithm, we present the design of a length-21 linear phase FIR bandpass filter. To see the effects of the design specifications, we will fix the two pass band edges and the upper stop band edge, then look at the effects of varying the lower stop band edge. The Matlab program that generated the designs is:

 
% ChebyPlot9.m generates Chebyshev figures.
% Change in opt frequency response as band edge is changed, csb 1/26/07
N = 20;
M = [0 0 1 1 0 0];
W = [7.5 10 7.5];
ff = [0:512]/512; k=0;
%for fk = .10:.02:.34
%    k = k+1;
clf;
for k = 1:6
    fk = .1 + .02*(k-1);
    F = [0 fk .35 .8 .85 1];
    b = firpm(N,F,M,W);
    %clf;
    axis([0 1 0 1.2]);
    AA = abs(fft(b,1024)); AA = AA(1:513);
    dd = max(AA(1:50));
    ddd = dd*(W(1)/W(2));
    subplot(3,2,k); plot(ff,AA,'r'); hold;
    plot([0 F(2) F(2) F(5) F(5) 1],[dd dd 0 0 dd dd],'b');
    plot([0 F(3) F(3) F(4) F(4) 1],[0 0 1-ddd 1-ddd 0 0],'b');
    plot([0 F(3) F(3) F(4) F(4) 1],[0 0 1+ddd 1+ddd 0 0],'b');
    title('L-21 Chebyshev Filter, f_s = 0.1');
    ylabel('Magnitude |H(\omega)|');
    pause;
end; hold off;
 

The results are shown in Figures Figure 5 and Figure 6.

Figure 5: Amplitude Response of Length-21 Optimal Chebyshev Bandpass Filter with various Stop Band Edges
Figure five contains six graphs. the horizontal axes are labeled Normalized frequency: f, and the vertical axes are labeled Magnitude |H(ω)|. The horizontal axes range in value from 0 to 1 in increments of 0.5, and the vertical axes range in value from 0 to 1 in increments of 0.5. All six graphs follow a similar fashion, beginning in the bottom-left section with small sinusoidal waves, then continuing with a larger wave to a second consistent sinusoidal section in the middle, centered around a vertical value of 1, and a third section after a decrease in the curve back down to a sinusoidal section in the bottom-right section of the graph with two more waves. The graph in the top-right is titled L-21 Chebyshev Filter, f_s = 0.1. The amplitude of the first and third sections are approximately 0.1, and the amplitude of the middle section  is approximately 0.2. The wave in between the first and second sections is so large that its peak is above the visible section of the graph. The next graph is titled L-21 Chebyshev Filter, f_s = 0.12. In every visible respect, this graph is identical to the aforementioned graph titled L-21 Chebyshev Filter. The next graph is titled L-21 Chebyshev Filter, f_s = 0.14. This graph has the same amplitudes of the sections mentioned in the previous graphs in this figure, but the wave between the first and second sections is much smaller, with its peak at a vertical value of 1. The next graph is titled L-21 Chebyshev Filter, f_s = 0.16. This graph has the same amplitudes of the sections mentioned in the previous graphs in this figure, but the wave between the first and second sections is much smaller, with its peak at a vertical value of 0.5. The next graph is titled L-21 Chebyshev Filter, f_s = 0.18. This graph has the same amplitudes of the sections mentioned in the previous graphs in this figure, but the wave between the first and second sections is much smaller, with its peak at a vertical value of approximately 0.25. The next graph is titled L-21 Chebyshev Filter, f_s = 0.2. This graph has the same amplitudes of the sections mentioned in the previous graphs in this figure, but the wave between the first and second sections is much smaller, with its peak at a vertical value of approximately 0.2.
Figure 6: Amplitude Response of Length-21 Optimal Chebyshev Bandpass Filter with various Stop Band Edges
Figure six contains six graphs. the horizontal axes are labeled Normalized frequency: f, and the vertical axes are labeled Magnitude |H(ω)|. The horizontal axes range in value from 0 to 1 in increments of 0.5, and the vertical axes range in value from 0 to 1 in increments of 0.5. All six graphs follow a similar fashion, beginning in the bottom-left section with small sinusoidal waves, then continuing to a second consistent sinusoidal section in the middle, centered around a vertical value of 1, and a third section after a decrease in the curve back down to a sinusoidal section in the bottom-right section of the graph with two more waves. The graph in the top-right is titled L-21 Chebyshev Filter, f_s = 0.22. The amplitude of the first and third sections are approximately 0.1, and the amplitude of the middle section  is approximately 0.2. The next graph is titled L-21 Chebyshev Filter, f_s = 0.24. In every visible respect, this graph is identical to the aforementioned graph titled L-21 Chebyshev Filter, f_s = 0.22. The next graph is titled L-21 Chebyshev Filter, f_s = 0.26.  In every visible respect, this graph is identical to the aforementioned graph titled L-21 Chebyshev Filter, f_s = 0.22. The next graph is titled L-21 Chebyshev Filter, f_s = 0.28. This graph has the same amplitudes of the sections mentioned in the previous graphs in this figure, but the first peak of the second section is smaller, only reaching a vertical value of approximately 0.9. The next graph is titled L-21 Chebyshev Filter, f_s = 0.32. This graph's sinusoidal sections have significantly larger amplitudes, an increase of approximately 50 percent for each section. The next graph is titled L-21 Chebyshev Filter, f_s = 0.34.  This graph's sinusoidal sections have significantly larger amplitudes, an increase of approximately 60 percent for each section.

Note the large transmission peaks in the transition band of Figures Figure 5a, b, and c that result from the two transition bands being very different in width. As the lower transition band narrows, this peak grows smaller and eventually disappears in Figure 5f. Note that there are two extremal points in the lower stop band of Figure 5b and seven in the pass band, while there are three in the lower stop band of Figures Figure 5c and d and six in the pass band. But, there are always twelve total (thirteen for a case between Figures Figure 5b and c). In Figure 6d, there are only five extremal points in the pass band but twelve total. The same filter is optimal for the conditions given in Figures Figure 6a, b, and c. Much can be learned about optimal filters by running experiments in Matlab. Remember, all of these are optimal for the specifications given.

Chebyshev Approximation using Approximation

It is possible to approximate the effects of Chebyshev approximation by minimizing the pthpth power of the error. For large pp this is close to the results of a true Chebyshev approximation. This is a variation on a method called Lawson's method. This approach is described in [8], [10], [11] using the iterative reweighted least squared (IRLS) error method and looks attractive in that it can use different pp in different frequency bands. This would allow, for example, a least squared error approximation in the passband and a Chebyshev approximation in the stopband. The IRLS method can also be used for complex Chebyshev approximations [88].

Characteristics of Optimal Chebyshev Filters

Examples of expected and unexpected results of optimality. Rabiner's work will be used here. The non-unique designs for certain multiband designs will be illustrated.

Complex Chebyshev Approximation

Algorithms that directly use the alternation theorem, such as the standard Remez multiple exchange algorithm, are difficult to apply to the complex approximation or 2-D approximation problem because the concept of “alternation" is difficult to define and the number of ripples in an optimal solution is more difficult to determine [92], [79], [84], [12], [40], [39], [85]. Work has been done on the complex approximation problem at Rice by Parks and Chen [17] and by Burrus, Barreto, and Selesnick [11], [9], at Erlangen by Schuessler, Preuss, Schulist, and Lang [59], [60], [71], [73], [74], [72], at MIT by Alkhairy et al [1], [2], at USC by Tseng and Griffiths [88], [86], at Georgia Tech by Karam and McClellan [34], at Cornell by Burnside and Parks [14], and by Potchinkov and Reemtsen at Cottbus [53], [54], [57], [58], [56]. The work done by Adams which uses an implementation of a constrained quadratic programming algorithm might be useful here [3], [6]. Lang has extended and further developed this constrained approach [37], [38], [42] and Selesnick is applying it to IIR filter design [75]. Tseng gives a good summary of complex approximation in [86].

Conclusions and Discussions of Chebyshev Design

By adding the Chebyshev filter design methods described above to the Parks-McClellan algorithm, one has a rather complete set of approaches to equal ripple filter designs that allows a wide variety of specifications. The new exchange algorithm which minimizes the transition band width while allowing the specification of the center or either edge of the transition band edge may fit many design environments better than the traditional Parks-McClellan. An alternative approach which specifies the pass and stop band peak error yet has no zero weighted transition band will be presented in Constrained Least Squares Design[77], [78]. Matlab programs are available for the Parks-McClellan algorithm, the modified Parks-McClellan algorithm, the Hofstetter-Oppenheim-Siegel algorithm, the new minimum transition band design algorithm, and the constrained least squares algorithm. They are written with a common format and notation to easily see how they are programmed and how they are related. This book generally presents the lowpass case. The bandpass and multi-band cases use the same ideas but are a bit more complicated and are discussed in more detail in the references.

References

  1. Alkhairy, Ashraf and Christian, Kevin and Lim, Jae. (1991, May). Design of FIR Filters by Complex Chebyshev Approximation. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. (p. 1985–1988). Toronto, Canada
  2. Alkhairy, Ashraf and Christian, Kevin and Lim, Jae. (1993, February). Design and Characterization of Optimal FIR Filters with Arbitrary Phase. IEEE Transactions on Signal Processing, 41(2), 559–572.
  3. Adams, John W. (1991, April). FIR Digital Filters with Least–Squares Stopbands Subject to Peak–Gain Constraints. IEEE Transactions on Circuits and Systems, 39(4), 376–388.
  4. Antoniou, A. (1995). Equiripple FIR Filters. In Chen, Wai-Kai (Ed.), The Circuits and Filters Handbook. (p. 2541–2562). Boca Raton: CRC Press and IEEE Press.
  5. Arbel, Ami. (1993). Exploring Interior-Point Linear Programming. Cambridge: MIT Press.
  6. Adams, John W. and Sullivan, James L. (1998, February). Peak-Constrained Least-Squares Optimization. IEEE Transactions on Signal Processing, 46(2), 306–321.
  7. Bixby, Robert E. and Boyd, Andrew. (1988). Using the CPlex Linear Optimizer. CPlex Optimization, Inc. Houston, TX
  8. Burrus, C. S. and Barreto, J. A. (1992, May). Least -Power Error Design of FIR Filters. In Proceedings of the IEEE International Symposium on Circuits and Systems. (Vol. 2, p. 545–548). ISCAS-92, San Diego, CA
  9. Barreto, J. A. and Burrus, C. S. (1994, April 19–22). Complex Approximation using Iterative Reweighted Least Squares for FIR Digital Filters. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. (p. III:545–548). IEEE ICASSP-94, Adelaide, Australia
  10. Burrus, C. S. and Barreto, J. A. and Selesnick, I. W. (1992, September 13–16). Reweighted Least Squares Design of FIR Filters. In Paper Summaries for the IEEE Signal Processing Society's Fifth DSP Workshop. (p. 3.1.1). Starved Rock Lodge, Utica, IL
  11. Burrus, C. S. and Barreto, J. A. and Selesnick, I. W. (1994, November). Iterative Reweighted Least Squares Design of FIR Filters. IEEE Transactions on Signal Processing, 42(11), 2926–2936.
  12. Blatt, H. P. (1984). On Strong Uniqueness in Linear Complex Chebyshev Approximation. Journal of Approximation Theory, 41(2), 159–169.
  13. Bonzanigo, F. (1982). Some Improvements to the Design Programs for Equiripple FIR Filters. In Proceedings of the IEEE ICASSP. (p. 274–277).
  14. Burnside, Daniel and Parks, T. W. (1995, March). Optimal Design of FIR Filters with the Complex Chebyshev Criteria. IEEE Transaction on Signal Processing, 43(3), 605–616.
  15. Burrus, C. S. (1994, October). Multiband FIR Filter Design. In Proceedings of the IEEE Digital Signal Processing Workshop. (p. 215–218). Yosemite
  16. Cheney, E. W. (1966). Introduction to Approximation Theory. New York: McGraw-Hill.
  17. Chen, X. and Parks, T. W. (1987, February). Design of FIR Filters in the Complex Domain. IEEE Transactions on Acoustics, Speech and Signal Processing, 35, 144–153.
  18. DSP Committee, (Ed.). (1979). Programs for Digital Signal Processing. New York: IEEE Press.
  19. Darst, Richard B. (1991). Introduction to Linear Programming. New York: Marcel Dekker.
  20. Dem'yanov, V. F. and Malozemov, V. N. (1974). Introduction to Minimax. New York: Dover, 1990.
  21. Ebert, S. and Heute, U. (1983). Accelerated Design of Linear or Minimum-Phase FIR Filters with a Chebyshev Magnitude Response. Proc. IEE, part-G, 130, 267–270.
  22. Er, M. H. and Siew, C. K. (1995, March). Design of FIR Filters Using Quadratic Programming Approach. IEEE Transaction on Circuits and Systems – II, 42(3), 217–220.
  23. Grace, Andrew. (1990). Matlab Optimization Toolbox. Natick, MA: The MathWorks, Inc.
  24. Grenez, F. (1983). Constrained Chebyshev Approximation for FIR Filters. In Proceedings of the IEEE ICASSP-83. (pp. 194-196). Boston, MA
  25. Grenez, F. (1983, July). Design of Linear or Minimum-Phase FIR Filters by Constrained Chebyshev Approximation. Signal Processing, 5(4), 325–332.
  26. Helms, H. D. (1971, March). Digital Filters with Equiripple or Minimax Responses. [Reprinted in IEEE Press DSP Reprint Book]. IEEE Trans. Audio and Electroacoustics, AU–19, 87–94.
  27. Herrmann, O. (1970, May). Design of Nonrecursive Digital Filters with Linear Phase. [Reprinted in DSP reprints, IEEE Press, 1972, page 182]. Electronics Letters, 6(11), 328–329.
  28. Hofstetter, E. M. and Oppenheim, A. V. and Siegel, J. (1971, March). A New Technique For The Design of Non-recursive Digital Filters. In Proc. Fifth Annual Princeton Conference on Information Sciences and Systems. (p. 64–72). [Reprinted in IEEE Press DSP Reprints, 1972, page 187.].
  29. Hofstetter, E. M. and Oppenheim, A. V. and Siegel, J. (1971, October). On Optimum Nonrecursive Digital Filters. In Proc. Ninth Annual Allerton Conference on Circuit and System Theory. (p. 789–798). [Reprinted in IEEE Press DSP Reprints, 1972, page 195.].
  30. Herrmann, O. and Rabiner, L. R. and Chan, D. S. K. (1973, July). Practical Design Rules for Optimum Finite Impulse Response Lowpass Digital Filters. Bell System Technical Journal, 52, 769–799.
  31. Herrmann, O. and Schüssler, H. W. (1970, January). On the Design of Selective Nonrecursive Digital Filters. [presented at the IEEE Arden House Workshop on Digital Filtering].
  32. Hersey, H. S. and Tufts, D. W. and Lewis, J. T. (1972, June). Interactive Minimax Design of Linear Phase Nonrecursive Digital Filters Subject to Upper and Lower Function Constraints. IEEE Transactions Audio and Electroacoustics, AU-20, 171–173.
  33. Jackson, L. B. and Lemay, G. J. (1990, April). A Simple Remez Exchange Algorithm for Design IIR Filters with Zeros on the Unit Circle. In Proceedings of the ICASSP-90. (p. 13.D3.15). Albuquerque, NM
  34. Karam, Lina J. and McClellan, James H. (1995, March). Complex Chebyshev Approximation for FIR Filter Design. IEEE Transaction on Circuits and Systems – II, 42(3), 207–216.
  35. Lang, Markus. (1991). Matlab programs for Karmarkar's method.
  36. Lang, Mathias C. (1997, April). Design of Nonlinear Phase FIR Digital Filters using Quadratic Programming. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. Munich
  37. Lang, Markus and Bamberger, Joachim. (1993, April). Nonlinear Phase FIR Filter Design with Minimum LS Error and Additional Constraints. In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing. (p. III:57–60). Minneapolis, ICASSP-93
  38. Lang, Markus and Bamberger, Joachim. (1994, March). Nonlinear Phase FIR Filter Design According to the Norm with Constraints for the Complex Error. [Paper reprinted in July issue to correct typesetting errors]. Signal Processing, 36(1), 31–40.
  39. Liang, J. K. and deFigueiredo, R. J. P. (1985). A Design Algorithm for Optimal Low–Pass Nonlinear Phase FIR Digital Filters. Signal Processing, 8, 3–21.
  40. Leeb, F. and Henk, T. (to appear). Simultaneous Amplitude and Phase Approximation for FIR Filters. International Journal of Circuit Theory and Application.
  41. Lim, Y. C. (1995). Linear Programming (LP) and Mixed Integer Linear Programming (MILP) Design of FIR Filters. In Chen, Wai-Kai (Ed.), The Circuits and Filters Handbook. (p. 2573–2578). Boca Raton: CRC Press and IEEE Press.
  42. Lang, Markus and Selesnick, Ivan W. and Burrus, C. Sidney. (1996, May). Constrained Least Squares Design of 2D FIR Filters. IEEE Transactions on Signal Processing, 44(5), 1234–1241.
  43. Luenberger, D. G. (1984). Introduction to Linear and Nonlinear Programming. (Second). Reading, MA: Addison-Wesley.
  44. McClellan, James H. (1971, December). Chebyshev Approximation for Non-Recursive Digital Filters. Technical report. Rice University, Houston, TX.
  45. McClellan, James H. (1991, April 1,). Internals of Remez Interpolation. [Unpublished Note].
  46. Oppenheim, A. V. and Schafer, R. W. (1989). Discrete-Time Signal Processing. Englewood Cliffs, NJ: Prentice-Hall.
  47. Parks, T. W. (1972, January). Extensions of Chebyshev Approximation for Finite Impulse Response Filters. [presented at the IEEE Arden House Workshop on Digital Filtering].
  48. Parks, T. W. and Burrus, C. S. (1987). Digital Filter Design. New York: John Wiley & Sons.
  49. Parks, T. W. and McClellan, J. H. (1972, August). A Program for the Design of Linear Phase Finite Impulse Response Digital Filters. IEEE Transactions on Audio and Electroacoustics, AU-20, 195–199.
  50. Parks, T. W. and McClellan, J. H. (1972, March). Chebyshev Approximation for Nonrecursive Digital Filters with Linear Phase. IEEE Transactions on Circuit Theory, 19, 189–194.
  51. Potchinkov, Alexander W. (1997). Design of Optimal Linear Phase FIR Filters by a Semi-Infinite Programming Technique. Signal Processing, 58, 165–180.
  52. Powell, M. J. D. (1981). Approximation Theory and Methods. Cambridge, England: Cambridge University Press.
  53. Potchinkov, Alexander W. and Reemtsen, Rembert M. (1994). FIR Filter Design in the Complex Plane by a Semi-Infinite Programming Technique I, the Method. AEÜ, 48(3), 135–144.
  54. Potchinkov, Alexander W. and Reemtsen, Rembert M. (1994). FIR Filter Design in the Complex Plane by a Semi-Infinite Programming Technique II, Examples. AEÜ, 48(4), 200–209.
  55. Potchinkov, Alexander W. and Reemtsen, Rembert M. (1995). Design of FIR Filters in the Complex Plane by Convex Optimization. Signal Processing, 46, 127–146.
  56. Potchinkov, Alexander W. and Reemtsen, Rembert M. (1996, June). FIR Filters Design in Regard to Frequency Response, Magnitude, and Phase by Semi-Infinite Programming. In Proceedings of the International Conference on Parametric Optimization and Related Topics IV. Enschede (NL)
  57. Potchinkov, Alexander W. and Reemtsen, Rembert M. (1997). The Simultaneous Approximation of Magnitude and Phase by FIR Digital Filters I, A New Approach. International Journal on Circuit Theory and Application, 25, 167–177.
  58. Potchinkov, Alexander W. and Reemtsen, Rembert M. (1997). The Simultaneous Approximation of Magnitude and Phase by FIR Digital Filters II, Methods and Examples. International Journal on Circuit Theory and Application, 25, 179–197.
  59. Preuss, Klaus. (1987, April). A Novel Approach for Complex Chebyshev Approximation with FIR Filters using the Remez Exchange Algorithm. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. (Vol. 2, p. 872–875). Dallas, Tx
  60. Preuss, Klaus. (1989, May). On the Design of FIR Filters by Complex Approximation. IEEE Transactions on Acoustics, Speech, and Signal Processing, 37(5), 702–712.
  61. Parks, T. W. and Rabiner, L. R. and McClellan, J. H. (1973, February). On the Transition Width of Finite Impulse-Response Digital Filters. IEEE Transactions on Audio and Electroacoustics, 21(1), 1–4.
  62. Rabiner, Lawrence R. (1972, October). Linear Program Design of Finite Impulse Response (FIR) Digital Filters. IEEE Trans. on Audio and Electroacoustics, AU-20(4), 280–288.
  63. Remes, E. Yz. (1957). General Computational Methods of Tchebycheff Approximations. [Atomic Energy Commission Translation 4491]. Kiev
  64. Rabiner, L. R. and Gold, B. (1975). Theory and Application of Digital Signal Processing. Englewood Cliffs, NJ: Prentice-Hall.
  65. Rabiner, L. R. and McClellan, J. H. and Parks, T. W. (1975, April). FIR Digital Filter Design Techniques using Weighted Chebyshev Approximation. Proceedings of the IEEE, 63(4), 595–610.
  66. Ruzinsky, S. A. and Olsen, E. T. (1989, February). and Minimization Via a Variant of Karmarkar's Algorithm. IEEE Transactions on ASSP, 37(2), 245–253.
  67. Shpak, D. J. and Antoniou, A. (1990, February). A Gereralized Remez Method for the Design of FIR Digital Filters. IEEE Trans. on Circuits and Systems, 37(2), 161–174.
  68. Selesnick, I. W. and Burrus, C. S. (1995, June 26–28). Some Exchange Algorithms Complementing the Parks-McClellan Program for Filter Design. In Proceedings of the International Conference on Digital Signal Processing. (p. 804–809). Limassol, Cyprus
  69. Selesnick, Ivan W. and Burrus, C. Sidney. (1996, September). Exchange Algorithms for the Design of Linear Phase FIR Filters and Differentiators Having Flat Monotonic Passbands and Equiripple Stopbands. IEEE Transactions on Circuits and Systems II, 43(9), 671–675.
  70. Selesnick, Ivan W. and Burrus, C. Sidney. (1997, February). Exchange Algorithms that Complement the Parks-McClellan Algorithm for Linear Phase FIR Filter Design. IEEE Transactions on Circuits and Systems II, 44(2), 137–143.
  71. Schulist, Matthias. (1990). Improvements of a Complex FIR Filter Design Algorithm. Signal Processing, 20, 81–90.
  72. Schulist, Matthias. (1992). A Complex Remez Algorithm with Good Initial Solutions. preprint.
  73. Schulist, Matthias. (1992, April). Complex Approximation with Additional Constraints. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. (Vol. 5, p. 101–104).
  74. Schulist, Matthias. (1992). FIR Filter Design with Additional Constraints using Complex Chebyshev Approximation. preprint.
  75. Selesnick, Ivan W. and Lang, Markus and Burrus, C. Sidney. (1994, March). Design of Recursive Filters to Approximate a Square Magnitude Frequency Response in the Chebyshev Sense. Technical report. ECE Dept. Rice University.
  76. Selesnick, Ivan W. and Lang, Markus and Burrus, C. Sidney. (1995, Nov.). A Simple Algorithm for Constrained Least Squares Design of Multiband FIR Filters without Specified Transition Bands.
  77. Selesnick, Ivan W. and Lang, Marcus and Burrus, C. Sidney. (1995, May 8–12). Constrained Least Square Design of FIR Filters without Specified Transition Bands. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. (Vol. 2, p. 1260–1263). IEEE ICASSP-95, Detroit
  78. Selesnick, Ivan W. and Lang, Markus and Burrus, C. Sidney. (1996, August). Constrained Least Square Design of FIR Filters without Explicitly Specified Transition Bands. IEEE Transactions on Signal Processing, 44(8), 1879–1892.
  79. Streit, R. L. and Nutall, A. H. (1982). A General Chebyshev Complex Function Approximation Procedure and an Application to Beamforming. J. Acoust. Soc. Am., 72(1), 181–190.
  80. Steiglitz, K. and Parks, T.W. and Kaiser, J.F. (1992, August). METEOR: A Constraint-based FIR Filter Design Program. IEEE Transactions on Signal Processing, 40(8), 1901–1909.
  81. Steiglitz, K. (1985). Linear Phase FIR Design with Upper and Lower Constraints using Linear Programming. [submitted]. Signal Processing.
  82. Strang, Gilbert. (1976). Linear Algebra and Its Applications. New York: Academic Press.
  83. Strang, Gilbert. (1986). Introduction to Applied Mathematics. Wellesley, MA: Wellesley-Cambridge Press.
  84. Streit, R. L. (1986, January). Solutions of Systems of Complex Linear Equatins in Norm with Constraints on the Unknowns. SIAM J. Aci. Stat. Comput., 7, 132–149.
  85. Tang, P. T. (1988, October). A Fast Algorithm for Linear Complex Chebyshev Approximations. Mathematics of Computation, 51(184), 721–739.
  86. Tseng, Ching-Yih and Griffiths, Lloyd J. (1994, January). Are Equiripple Digital FIR Filters Always Optimal with Minimax Error Criterion? IEEE Signal Processing Letters, 1(1), 5–8.
  87. Tufts, Donald W. and Rorabacher, Darold W. and Mosier, Wilbur E. (1970, June). Designing Simple, Effective Digital Filters. IEEE Transactions on Audio and Electroacoustics, 18(2), 142–158.
  88. Tseng, Ching-Yih. (1992, May). A Numerical Algorithm for Complex Chebyshev FIR Filter Design. In Proceedings of the IEEE International Symposium on Circuits and Systems. (Vol. 3, p. 549–552). San Diego, CA
  89. Vaidyanathan, P. P. (1987). Design and Implementation of Digital FIR Filters. In Elliott, Douglas F. (Ed.), Handbook of Digital Signal Processing. (p. 55–170). San Diego, CA: Academic Press.
  90. Vandenberghe, Lieven and Boyd, Stephen. (1996, March). Semidefinite Programming. SIAM Review, 38(1), 49–95.
  91. Vandenberghe, Lieven and Boyd, Stephen. (to appear 1998). Connections Between Semi-Infinite and Semidefinite Programming. In Reemtsen, R. and Rueckmann, J.-J. (Eds.), Semi-Infinite Programming. Kluwer.
  92. Veidinger, L. (1960). On the Numerical Determination of best Approximation in the Chebyshev Sense. Numerische Mathematik, 99–105.
  93. Wu, Shao-Po and Boyd, Stephen and Vandenberghe, Lieven. (1997). FIR Filter Design via Spectral Factorization and Convex Optimization. In Datta, Biswa (Ed.), Applied Computational Control, Signal and Communications. Birkhauser.
  94. Weisburn, B. A. and Parks, T. W. and Shenoy, B. G. (1994, April 19–22). Error Criteria for Filter Design. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. (Vol. 3, p. III:565–568). IEEE ICASSP-94, Adelaide, Australia

Content actions

Download module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks