Digital Signal Processing Reference
In-Depth Information
and
unique
solution. Note that the extremal points (i.e. the values of the
error function at the edges of the optimization intervals)
do
count in the
number of alternations since the intervals
I
k
are closed.
The above theorem may seem a bit far-fetched since it does not tell us
how to find the coefficients but it only gives us a test to verify their optimal-
ity. This test, however, is at the core of an
iterative
algorithm which refines
the polynomial from an initial guess to the point when the optimality condi-
tion is met. Before considering the optimization procedure more in detail,
we will state without formal proof, three consequences of the alternation
theorem as it applies to the design of Type I lowpass filters:
l
g
r
,
y
i
d
.
,
©
,
L
s
•
The minimum number of alternations for an optimal
M
-tap lowpass
filter is
L
2; this is the result of the alternation the-
orem. The
maximum
number of alternation, however, is
L
+
2, with
L
=(
M
−
1
)
/
+
3; filters
with
L
+
3 alternation are called extraripple filters.
•
Alternations always take place at
x
=
cos
ω
p
and
x
=
cos
ω
s
(i.e. at
ω
=
ω
p
and
ω
=
ω
s
.
•
If the error function has a local maximum or minimum, its absolute
value at the extremummust be equal to
E
max
except possibly in
x
=
0
or
x
1. In other words, all local maxima and minima of the fre-
quency response must be alternation, except in
ω
=
0or
ω
=
π
.
=
•
If the filter is extraripple, the extra alternation occurs at either
ω
=
0
or
ω
=
π
.
Optimization Procedure.
Finally, by putting all the elements together,
we are ready to state an algorithmic optimization procedure for the design
of optimal minimax FIR filters; this procedure is usually called the Parks-
McClellan algorithm. Remember, we are trying to determine a polynomial
P
(
x
)
such that the approximation error in (7.23) is equiripple; for this, we
need to determine both the degree of the polynomial and its coefficients.
For a given degree
L
, for which the resulting filter has 2
L
1taps,the
L
co-
efficients are found by an iterative procedure which successively refines an
initial guess for the
L
+
2 alternation points
x
i
until the error is equiripple.
(5)
After the iteration has converged, we need to check that the corresponding
+
(5)
Details about this crucial optimization step can be found in the bibliographic refer-
ences. While a thoroughdiscussion of the algorithm is beyond the scope of the topic, we
can mention that at each iteration the new set of candidate extremal points is obtained
by exchanging the old set with the ordinates of the current local maxima. This trick is
known as the Remez exchange algorithmand that is why, inMatlab, the Parks-McClellan
algorithm is named
remez
.
