7.5 OPTIMAL EQUIRIPPLE DESIGN TECHNIQUE
7.5.2 CONSTRAINT ON THE NUMBER OF EXTREMA Before we give the solution to this above problem, we will first discuss
cos (2ω) = 2 cos2(ω)−1 cos (3ω) = 4 cos3(ω)−3 cos (ω)
... = ...
P(ω) can be converted to a trigonometric polynomial in cos (ω), which we can write (7.41) as
P(ω) = L n=0
β(n) cosnω (7.46)
EXAMPLE 7.21 Let h(n) = 151[1,2,3,4,3,2,1] . Then M = 7 and h(n) is symmetric, which means that we have a Type-1 linear-phase filter. Hence L= (M −1)/2 = 3.
Now from (7.7)
α(n) =a(n) = 2h(3−n), 1≤n≤2; and α(0) =a(0) =h(3) orα(n) = 151[4,6,4,2]. Hence
P(ω) = 3
0
α(n) cosωn=151 (4 + 6 cosω+ 4 cos 2ω+ 2 cos 3ω)
= 151
4 + 6 cosω+ 4(2 cos2ω−1) + 2(4 cos3ω−3 cosω)
= 0 + 0 +158 cos2ω+158 cos3ω= 3
0
β(n) cosnω
orβ(n) =
0,0, 8 15, 8
15
.
From (7.46) we note thatP(ω) is anLth-order polynomial in cos(ω). Since cos(ω) is a monotonefunction in theopeninterval 0< ω < π, then it follows that theLth-order polynomialP(ω) in cos(ω) should behave like an ordinary Lth-order polynomialP(x) inx.ThereforeP(ω) hasat most(i.e., no more than) (L−1) local extrema in the open interval 0< ω < π. For example,
cos2(ω) =1 + cos 2ω 2
has only one minimum atω=π/2. However, it has three extrema in the closed interval 0≤ ω≤π (i.e., a maximum at ω= 0, a minimum atω =π/2, and
0.0 0.04
0.4 1
−0.04 0.1 1.07 1.0 0.93
Amplitude Response
L − 1 = 2 extrema
0.4 1
0.1
ω/π
ω/π 0.07
0
−0.07
Error Function L + 3 = 6 extrema
FIGURE 7.34 Amplitude response and the error function in Example 7.22
a maximum at ω =π). Now if we include the end pointsω = 0 and ω=π, thenP(ω) has at most (L+ 1) local extrema in the closed interval 0≤ω≤π.
Finally, we would like the filter specifications to be met exactly at band edges ωpandωs. Then the specifications can be met at no more than (L+ 3) extremal frequencies in the 0≤ω≤πinterval.
Conclusion The error functionE(ω) has at most (L+ 3) extrema inS. EXAMPLE 7.22 Let us plot the amplitude response of the filter given in Example 7.21 and count
the total number of extrema in the corresponding error function.
Solution The impulse response is h(n) = 1
15[1,2,3,4,3,2,1], M= 7 or L= 3 andα(n) =151[4,6,4,2] andβ(n) =
0,0,158,158
from Example 7.21. Hence P(ω) = 8
15cos2ω+ 8 15cos3ω
which is shown in Figure 7.34. Clearly, P(ω) has (L−1) = 2 extrema in the open interval 0< ω < π. Also shown in Figure 7.34 is the error function, which
has (L+ 3) = 6 extrema.
Let us now turn our attention to the problem statement and equa- tion (7.45). It is a well-known problem in approximation theory, and the solution is given by the following important theorem.
THEOREM 1 Alternation Theorem
Let S be any closed subset of the closed interval [0, π]. In order that P(ω)be the unique minimax approximation toHdr(ω)onS, it is necessary and sufficient that the error function E(ω)exhibit at least(L+ 2)“alter- nations” or extremal frequencies in S; that is, there must exist (L+ 2) frequencies ωi in S such that
E(ωi) =−E(ωi−1) = ±max
S |E(ω)| (7.47)
=±δ,∀ω0< ω1<ã ã ã< ωL+1∈ S
Combining this theorem with our earlier conclusion, we infer that the optimal equiripple filter has either (L+ 2) or (L+ 3) alternations in its error function over S. Most of the equiripple filters have (L+ 2) alternations. However, for some combinations of ωp and ωs, we can get filters with (L+3) alternations. These filters have one extra ripple in their response and hence are called Extraripplefilters.
7.5.3 PARKS-McCLELLAN ALGORITHM
The alternation theorem ensures that the solution to our minimax ap- proximation problem exists and is unique, but it does not tell us how to obtain this solution. We know neither the order M (or equivalently, L), nor the extremal frequenciesωi, nor the parameters{α(n)}, nor the maximum errorδ. Parks and McClellan [20] provided an iterative solution using the Remez exchange algorithm. It assumes that the filter length M (orL) and the ratioδ2/δ1are known. If we choose the weighting function as in (7.43), and if we choose the order M correctly, then δ =δ2 when the solution is obtained. Clearly, δandM are related; the larger theM, the smaller the δ. In the filter specificationsδ1,δ2,ωp, and ωsare given.
Therefore M has to be assumed. Fortunately, a simple formula, due to Kaiser, exists for approximatingM. It is given by
Mˆ =−20 log10√
δ1δ2−13
2.285∆ω + 1; ∆ω=ωs−ωp (7.48) The Parks-McClellan algorithm begins by guessing (L+ 2) extremal frequencies{ωi}and estimating the maximum errorδat these frequencies.
It then fits anLth-order polynomial (7.46) through points given in (7.47).
Local maximum errors are determined over a finer grid, and the extremal frequencies{ωi} are adjusted at these new extremal values. A newLth- order polynomial is fit through these new frequencies, and the procedure is repeated. This iteration continues until the optimum set {ωi} and the global maximum errorδare found. The iterative procedure is guaranteed to converge, yielding the polynomialP(ω). From (7.46) coefficientsβ(n) are determined. Finally, the coefficients a(n) as well as the impulse re- sponse h(n) are computed. This algorithm is available in MATLAB as thefirpmfunction, which is described shortly.
Since we approximatedM, the maximum errorδmay not be equal to δ2. If this is the case, then we have to increaseM (ifδ > δ2) or decrease M (if δ < δ2) and use the firpm algorithm again to determine a new δ. We repeat this procedure until δ ≤ δ2. The optimal equiripple FIR filter, which satisfies all the three requirements discussed earlier, is now determined.
7.5.4 MATLAB IMPLEMENTATION