2.3 Chebyshev or equal ripple error approximation filters  (Page 2/9)

where $\Omega$ is the union of the bands of frequencies that the approximation is over [link] , [link] . The approximation problem in filter design is to choose the filter coefficients to minimize $\epsilon$ .

One way to minimize $\epsilon$ 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 [link] 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 $R$ cosine terms

or for even L

with $R=M+1=\frac{L+1}{2}$ for odd length- $L$ and $R=L/2$ for even length- $L$ , as derived in Equation 34 from FIR Digital Filters and Equation 40 FIR Digital Filters , then

Theorem 1

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

for $k=0,1,2,\cdots ,R$ , where the ${\omega }_k$ are the ordered extremal frequencies where the equal ripple error has maximum value. Inother words, the optimal solution to the linear phase FIR filter design problem will have an equal ripple error function with a required number ofripples. How all of these characteristics relate can be rather complicated and good designs require experience [link] . When applied to other approximation problems, care must be taken to ensure theapproximating functions satisfy the “Haar conditions" or other restrictions [link] , [link] , [link] , [link] .

Chebyshev approximation by linear programming

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

where the scalar $\delta$ is minimized.

The inequalities in [link] can be written as

or

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

If $\delta$ is minimized, the optimal Chebyshev approximation is achieved. This is done by minimizing

which, together with the inequality of [link] , is in the form of the dual problem in linear programming [link] , [link] , [link] .

This can be solved using the lp()command from the Optimization Toolbox with Matlab [link] , the Meteor software system [link] , CPlex [link] , or Karmarkar's algorithm [link] , [link] . The Matlab lpcommand is implemented in an m-file using a form of quadratic programming algorithm that is not well suited to our filterdesign 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 arelatively short m-file that is not particularly fast but is robust and can design filters on the order of length-100. CPlex is a proprietaryprogram that can be used alone or called from Fortran programs and is particularly robust and fast.