Finite Impulse Response Filter Design - Digital Signal Processing: Fundamentals and Applications - page 278

EðU k Þ¼EðU kþ1 Þ for U 0 ; U 1 ; . U Mþ1

and

jEðU k Þj ¼ E max

But the alternation theorem does not tell us how to execute the algorithm. The Remez exchange algorithm actually
is employed to solve this problem. The equations and steps (Ambardar, 1999; Porat, 1997) are briefly summarized
for our illustrative example:
1. Given an order of N ¼ 2Mþ1, choose the initial extremal frequencies:

U 0 ; U 1 ; . ; U Mþ1 ðcan be uniformly distributed firstÞ

2. Solve the following equation to satisfy the alternate theorem:

k E ¼ WðU k ÞðH d ðe jU k

ÞHðe jU k ð1Þ ÞÞ for U 0 ; U 1 ; . ; U Mþ1

Note that since Hðe jU Þ¼b 1 þ 2b 0 cos U, for example, the solution will include solving for three unknowns:
b 0 ,b 1 , and E max .

3. Determine the extremal points including band edges (can be more than M þ 2 points), and retain M þ 2

extremal points with the largest error values E max .

4. Output the coefficients, if the extremal frequencies are not changed; otherwise, go to step 2 using the new set

of extremal frequencies.

Now let us apply the Remez exchange algorithm.
First Iteration
1. We use uniformly distributed extremal points U 0 ¼ 0, U 1 ¼ p=2, U 2 ¼ p whose ideal magnitudes are
marked by the symbol “o” in Figure 7.38 ( a).

k E ¼ H d ðe jU Þðb 1 þ 2b 0 cos UÞ.
Applying extremal points yields the following three simultaneous equations with three unknowns: b 0 ,b 1 ,
and E:

2. The alternation theorem requires ð1Þ

<
:

E ¼ 0:5 b 1 2b 0
E ¼ 0:75 b 1
E ¼ 0 b 1 þ 2b 0

We solve these three equations to get

b 1 ¼ 0:5; E ¼ 0:25; Hðe jU Þ¼0:5 þ 0:25 cos U

b 0 ¼ 0:125;

3. We then determine the extremal points, including at the band edge, with their error values from Figure 7.38 ( b)
using the following error function:

EðUÞ¼H d ðe jU Þ0:5 0:25 cos U

These extremal points are marked by symbol “o” and their error values are listed in Table 7.16 .

4. Since the band edge U ¼ p=4 has an larger error than the others, it must be chosen as the extremal frequency.

After deleting the extremal point at U ¼ p=2, a new set of extremal points are found according the largest error
values as

U 0 ¼ 0
U 1 ¼ p=4