THE REMEZ ALGORITHM

THE REMEZ ALGORITHM

This section describes how to design linear-phase FIR filters based on the Chebyshev (or minimax) error criterion. The minimization of the Chebyshev norm is useful because it permits the user to explicitly specify band-edges and relative error sizes in each band. We will see that linear-phase FIR filters that minimize a Chebyshev error criterion can be found with the Remez algorithm or by linear programming techniques. Both these methods are iterative numerical algorithms and can be used for very general functions D() and W () (although many implementations work only for piecewise linear functions). The Remez algorithm is not as general as the linear programming approach, but it is very robust, converges very rapidly to the optimal solution, and is widely used.

I. Selesnick

EL 713 Lecture Notes

1

THE PARKS-McCLELLAN ALGORITHM

Parks and McClellan proposed the use of the Remez algorithm for

FIR filter design and made programs available [5, 6, 9, 15]. Many

texts describe the Parks-McClellan (PM) algorithm in detail [7, 8,

11, 14].

The Remez algorithm can be use to design all four types of linear-

phase filters (I,II,III,IV), but for convenience only the design of type

I filters will be described here. Note that the weighted error function

is given by

E() = W () (A() - D()).

(1)

The amplitude response of a type I FIR filter is given by

M

A() = a(n) cos(n).

(2)

n=0

I. Selesnick

EL 713 Lecture Notes

2

PROBLEM FORMULATION

The Chebyshev design problem can formulated as follows. Given:

N : filter length D() : desired (real-valued) amplitude function W () : nonnegative weighting function, find the linear-phase filter that minimizes the weighted Chebyshev error, defined by

||E()|| = max |W () (A() - D())|.

(3)

[0,]

The solution to this problem is called the best weighted Chebyshev approximation to D(). Because it minimizes the maximum value of the error, it is also called the minimax solution. The Remez algorithm for computing the best Chebyshev solution uses the alternation theorem. This theorem characterizes the best Chebyshev solution.

I. Selesnick

EL 713 Lecture Notes

3

LOW-PASS CHEBYSHEV FILTERS

For low-pass filter design via the PM algorithm, the functions D() and W () are usually defined as

1 D() =

0 < < o

(pass-band)

(4)

0 o < <

(stop-band)

and

Kp

0 p

W () = 0

p < < s

(5)

Ks

s

where 0 < p < o < s < .

1

D()

0

o

Ks W () Kp

0 ps

For low-pass filters so obtained, the deviations p and s satisfy the relation p/s = Ks/Kp. For example, consider the design of a symmetric low-pass filter of length N = 31, with Kp = 1, Ks = 4 and p = 0.26, s = 0.34. The best Chebyshev solution and its weighted error function are illustrated in the figure. The

I. Selesnick

EL 713 Lecture Notes

4

maximum errors in the pass-band and stop-band are p = 0.0892 and s = 0.0223 respectively. The circular marks in the figure indicate the extremal points of the alternation theorem.

A()

1

0.8

0.6

0.4

0.2

0

-0.2

0

0.2 0.4 0.6 0.8

1

/

10

0

-10

-20

-30

-40

-50

-60

0

0.2 0.4 0.6 0.8

1

/

W() (A()-D())

h(n)

0.1 0.05

0 -0.05

-0.1 0

0.3 0.2 0.1

0 -0.1

0

0.2 0.4 0.6 0.8

1

/

10

20

30

n

|A()|, in dB

I. Selesnick

EL 713 Lecture Notes

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download