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

15.5.1 Alternation theorem

Let S be a compact subset on the real axis x and let D ( x ) be a desired function
of x which is continuous on S . Let D ( x ) be approximated by P ( x ), an L th-order
polynomial of x , which is given by

P ( x ) = L

c m x m . (15.48a)

m = 0

Define the approximation error ε ( x ) and the amplitude of the maximum error
value ε max on S as follows:

ε ( x ) = W ( x )[ D ( x ) − P ( x )] : (15.48b)

ε max = arg max

x ∈ S

ε ( x ) . (15.48c)

A necessary and sufficient condition for P ( x ) to be the unique L th-order poly-
nomial minimizing ε max is that ε ( x ) exhibits at least L + 2 alternations. In other
words, there must exist L + 2 values of x , x 1 < x 2 < x L + 2 ∈ S such that
ε ( x m ) =−ε ( x m + 1 ) =ε max .
Note that the minimax optimization problem for optimal filter design fits
very well in the framework of the alternation theorem. In the filter design
problem, S is the subset of DT frequencies, D ( x ) is the desired filter response,
P ( x ) is the approximated filter response, and ε max is the maximum deviation
between the desired and approximated filter response. Therefore, the FIR filters
obtained using minimax optimization is also expected to exhibit alternations in
its frequency response. However, note that G ( Ω ) is a polynomial of cos( Ω ) and
not of Ω . This issue can be addressed by using the mapping function x = cos( Ω ).
In this case, the frequency space Ω = [0 ,π ] can be mapped to x = [ − 1 , 1], and
the optimization problem can be reformulated around x to calculate the optimal
filter coefficients. It can be shown that the alternation in the frequency response
of the optimal filters is still applicable.
Based on the above discussion, the alternation theorem can be restated for
the minimax optimization problem as follows. Consider the following minimax
optimization problem:

h [ k ] , 0 ≤ min

k ≤ ( N − 1)

max
Ω ∈ S

ε ( Ω ) ; (15.49a)

"
$

H d ( Ω ) − G ( Ω )e − j Ω ( N − 1 / 2) e j φ ε ( Ω ) = W ( Ω ) . (15.49b)

H ( Ω )

where S is a set of discrete extremal frequencies chosen within the pass and stop
bands, W ( Ω ) is a positive weighting function, H d ( Ω ) is the transfer function of
the ideal filter with a unity gain within the pass band and a zero gain within the
stop band, and G ( Ω ) is a polynomial of cos( Ω ) with degree L , which is uniquely