FIR filter design - Continuous and Discrete Time Signals and Systems - page 695

The weighting function for highpass, bandpass, and bandstop filters can be
derived in a similar fashion. Given a weighting function, the Parks-McClellan
algorithm seeks to solve the following optimization problem:

min
h [ k ]

max
Ω ∈ S

ε ( Ω ) , (15.45)

where S is defined as a set of discrete frequencies chosen within the pass and
stop bands. For a lowpass filter, the set of frequencies that can be included in S
should lie in the following range:

lowpass filter S = 0 ≤ Ω ≤ Ω p ∪ [ Ω s ≤ Ω ≤ π ] (15.46)

Similarly, the sets S of discrete frequencies are carefully selected over the pass
and stop bands for other types of filters.
Because Eq. (15.45) minimizes a cost function, which is the maximum of the
error ε ( Ω ), Eq. (15.45) is also referred to as the minimax optimization problem.
The goal in solving Eq. (15.45) is to determine the set of coefficients for the
impulse response h [ k ] of the optimal FIR filter of length N .
It was shown in Proposition 14.1 (see Section 14.3.1) that if the filter coe-
fficients of an FIR filter are symmetric or anti-symmetric, the phase response
of the filter is a linear function of frequency, and the transfer function can be
expressed as follows:

H ( Ω ) = G ( Ω )e j( β−α Ω ) , (15.47)

where α = ( N − 1) / 2 ,β is a constant, and G ( Ω ) is a real-valued function. Table
14.2 shows the values of β and G ( Ω ) for four types of linear-phase FIR filters.
The Parks-McClellan algorithm exploits Proposition 14.1 to solve the mini-
max optimization problem, as explained in the following. For various types of
linear-phase FIR filter, G ( Ω ) is a summation of a finite number of sinusoidal
terms of the form cos( Ω k ) or sin( Ω k ), which themselves can be expressed as
polynomials of cos( Ω ). For example, cos( Ω k ) can be expressed as a k th-order
polynomial of cos( Ω ), which, for k = 2 and 3, can be expressed as follows:

cos (2 Ω ) = 2 cos 2 ( Ω − 1);
cos (3 Ω ) = 4 cos 3 ( Ω ) − cos( Ω ) .

It is observed from Table 14.2 that the function G ( Ω ) can be expressed as a sum
of several higher-order terms cos( Ω k ) or sin( Ω k ). Therefore, G ( Ω ) can also be
expressed as a polynomial of cos( Ω ). It can be shown that the error function ε ( Ω )
in Eq. (15.42), corresponding to linear-phase FIR filters, can also be expressed
as a polynomial of cos( Ω ). Parks and McClellan applied the alternation theorem
from the theory of polynomial approximation to solve the minimax optimization
problem. For convenience, we first express the alternation theorem in the context
of polynomial approximation, and later we show its adaptation to the minimax
optimization problem.