The 4th Asian Control Conference
September 25-27, 2002
Singapore

FA3-1

Optimal FIR Approximation for Discrete-Time IIR Filters
Yutaka Yamamoto∗

Brian D. O. Anderson†
Yoko Koyanagi∗

Masaaki Nagahara∗∗ Department of Applied Analysis and Complex
Dynamical Systems, Graduate School of Informatics,
Kyoto University, Kyoto 606-8501, JAPAN,
e-mail: yy@i.kyoto-u.ac.jp (corresponding author),{nagahara, koyanagi}@acs.i.kyoto-u.ac.jp,†
Research School of Information Sciences and Engineering,
Australian National University, Canberra, ACT 0200,
AUSTRALIA
e-mail: Brian.Anderson@anu.edu.anx(n)Abstractz −1

FIR(Finite Impulse Response) ﬁlters are often preferred to IIR(Inﬁnite Impulse Response) ﬁlters becauseof their various advantages in stability, phase characteristic possibilities, implementation, etc. This paper
proposes a new method to approximate an IIR ﬁlter
by an FIR ﬁlter, which directly yields an optimal approximation with respect to the H ∞ error norm. We
formulate this design problem as the minimization of
the H ∞ norm of the error transfer function of the difference between the given IIR ﬁlter and an FIR ﬁlter
to be designed. We show that this design problem canbe reduced to an LMI (Linear Matrix Inequality). We
will also make a comparison via a numerical example
with an existing approximation method, known as the
Nehari shuﬄe.

-H
a1H


?

z −1

-H
a2H
qq?

?
qq
q
−1
z
H
H
- aN


ak z −k .

(1)

On the other hand, a design process may have to startwith an IIR ﬁlter for variety of reasons. For example, we have a large number of continuous-time ﬁlters
available, and a digital ﬁlter may be obtained by discretizing one of them. It is then desired that suchan IIR ﬁlter be approximated by an FIR ﬁlter. An
easy, but not necessarily optimal, way of doing this is
to just truncate the Markov parameters of the IIR ﬁlter at a desired number of steps. This may howeverlead to either a very high-dimensional ﬁlter with good
approximation, or a lower dimensional ﬁlter with anunsatisfactory approximation, depending on the truncation point.

They are often preferred to those with inﬁnitely many
nonzero coeﬃcients known as IIR ﬁlters (Fig. 2)
M

k=0 ak z

1+

N

−k

k=1 bk z−k(2)

for the following reasons [7]:• FIR ﬁlters are intrinsically stable; the stability
issue is a non-issue.

981-04-6440-1/02/$10.00 © 2002 ASCC

-c
+
6
qq
q

• They can be free from certain problems in implementation, for example, limit cycles, attributed
to quantization and the existence of a feedback
loop in IIR ﬁlters.

k=0

F (z) =-c+6

• They can easily realize various features that are
not possible or are diﬃcult to achieve with IIR
ﬁlters, e.g., linear phase property.

Digital ﬁlters that have ﬁnitely many nonzero Markov
parameters are called FIR ﬁlters (Fig. 1):
M


y(n)
-c
+
6

Figure 1: FIR ﬁlter

1 Introduction

F (z) =

-H
a0H

?

2008

x(n)
-c
+6

-H
a0H

?

c
+6


b1 
HH

c
+6
qq
q

b2 

HH
qq
q

N
HbH

z −1

-H
a1H

?

z −1

-H
a2H
?
qq

?
qq
q
z −1
H
-H
aN


y(n)
-c
+
6

2 FIR Approximation Problem
Consider the block diagram Fig. 3.

-c
+
6

K(z)
w

-c
+
6
qq
q

−

e

W (z)
+

Kf (z)

Figure 2: IIR ﬁlter

Figure 3: Error system

The following problem is thus very natural and ofimportance:

K(z) is a given (rational and stable) IIR ﬁlter, W (z)is a proper and rational weighting function, and Kf (z)is an FIR ﬁlter of order N . The objective here is toﬁnd Kf (z) that makes the H ∞ error norm less than aprespeciﬁed bound γ.

Problem 1 Given an IIR ﬁlter K(z) and a positive integer N , ﬁnd an optimal FIR approximant Kf (z) thathas order N and approximates K(z) with respect to acertain performance measure.

Introduce state space realizations

A B
W (z) : =
,
C D


AK BK
K(z) : =,CK DKThere is a very elegant method called the Nehari shufﬂe, proposed by Kootsookos et al. [3, 4]. Its basic idea
may be described as follows: For a given IIR ﬁlter G
and a desired degree r − 1 that an approximating FIR
ﬁlter should assume, one ﬁrst truncates the impulse
response of G to the ﬁrst r steps. This is a mere truncation, and it may induce a large error. One then takes
its residual G1 , and approximates G1 by another FIR
ﬁlter of length r by using a Nehari approximation ofa shifted and mirror image version of G1 followed bytruncation. This truncation produces another residual;
the process can be continued, and the approximation
can be improved in each step. (Details may be found in[5]. An advantage here is that this procedure gives rise
to certain a priori and a posteriori error bounds. On
the other hand, it does not necessarily give an optimal
approximation with respect to the H ∞ norm.

andKf (z) =ak z −k =

k=0

Cf (α)=Df (α)

=

α =



aN

Af
Cf (α)

aN −1

...

a1

aN −1

...

a0

Bf
Df (α)



,

,

a0 ,


aN



.



aN aN −1 . . . a0
where α =denote theMarkov parameters of the ﬁlter Kf (z) to be designed.
The matrices Af and Bf are deﬁned as follows:

In contrast to the Nehari shuﬄe, we here propose amethod that directly deals with (sub)optimal approximants with respect to a (weighted) H ∞ error norm.
It is shown thatAf=• the design problem is reducible to an LMI [1];
and

0
 ..
 .

 ..
 .

 .
 ..

Bf

A comparison with the Nehari shuﬄe is made for the
Chebyshev ﬁlter of order 8, which has been studied indetail in [4].

=

1
..
.

0 ···

0
 .. 
 . 

,
 0 
1


• the obtained ﬁlter can be made close to be optimal by an iterative procedure.

981-04-6440-1/02/$10.00 © 2002 ASCC

N


0
..
.

···

..

..

.

.

..

···

.
···

and they contain just zeros and ones.

2009


0
.. 
. 


,
0 


1 
0

Denote by Tew (z) the transfer function from w to e inFig. 3. Its realization is then given as follows:BW,:
DW (α)

A00 Bk C Ak 0  ,Bf C 0 AfB Bk D  ,
Bf D(Df (α) − Dk )C −Ck

Tew (z) =

AW

BW
CW
DW

=

=

=
=



1.2

AW
CW (α)(Dk + Df (α))D

1MagnitudeMagnitude Response of Weighting

1.4

0.8

0.6

0.4

0.2

Cf (α)



,

0
0

0.1

0.3
0.2
Frequency [rad/sec]

0.4

0.5

.
Figure 4: Inverse of the weighting function

The important asset here is that the design parameter α appears only in the C and D matrices linearly,
and the underlying structure is of the one-block type.
Hence the overall transfer operator is linear in α, andthe design problem of choosing α to minimize the H∞
norm can be expected to become a linear matrix inequality. In fact, the bounded real lemma [1] readily
yields the following:

Then by using the Sure complement for T
T
ATW P BWAW P AW − P
Φ11 :=
,
T
T
BW
P AW
BW
P BW − γIΦ22 := −γI,

T
CW DW
,
Φ12 :=

Theorem 1 Tew  < γ if and only if there exists P > 0such that T
T
ATW P BWCWAW P AW − P
T
T
T 

BW
P AW
−γI + BW
P BW DW
< 0.
CW
DW
−γI

where P := γ −1 P̃ > 0, we obtain the inequality (3).
The obtained condition is an LMI in α, and can beeﬀectively solved by standard MATLAB routines [2].

(3)Proof: By the bounded real lemma [1], Tew  < γ isequivalent to the condition that there exists a matrix
P̃ > 0 such that




P̃ 0
P̃
0
T
Q
Q<
,
(4)
0 I
0 γ2I
where


Q =:

AW
CW (α)BW
DW (α)

3 Numerical Example
3.1 Comparison of H ∞ Design via LMI and the Nehari
ShuﬄeTake the following Chebyshev ﬁlter of order 8K(z) =

.

0.04705z 8 + 0.3764z 7 + 1.317z 6
z 8 − 4.953z 7 + 11.71z 6+2.635z 5 + 3.294z 4 + 2.635z 3 + 1.317z 2−16.95z 5 + 16.29z 4 − 10.58z 3 + 4.552z 2

Although the inequality (4) is not aﬃne in α, it canbe converted to an aﬃne one by the Schur complement[1]:
Φ11 Φ12<0ΦT12 Φ22+0.3764z + 0.04705.
−1.161z + 0.1369
as a target ﬁlter to be approximated. This has beenstudied thoroughly by Kootsookos and Bitmead [4] using the Nehari shuﬄe, and is suitable for comparison
with the present method. For simplicity, we conﬁne
ourselves to approximations by FIR ﬁlters with 32 tap
coeﬃcients (of order 31).

T
is equivalent to Φ22 < 0 and Φ11 < Φ12 Φ−1
22 Φ12 . By
dividing the inequality (4) by γ > 0, we obtain T −1ATW γ −1 P̃ BW
AW γ P̃ AW − γ −1 P̃
T −1
T −1
BW
γ P̃ AWBW
γ P̃ BW − γI
 T 


CW
<
(−γ −1 I) CW DW .
T
DW

981-04-6440-1/02/$10.00 © 2002 ASCC

10−3 ×The design depends crucially on the choice of theweight W (z). One natural choice ([5]) would be to2010

take W (z) to be equal to K −1 (z) (or some variant of
it having the same gain on the unit circle, since K is
not minimum phase). This is relative error approximation, where (approximately) dB and phase errors areweighted uniformly with frequency. Since the error criterion in Fig. 3 is taken with respect to the H ∞ norm,
it approximates equal amplitude at all frequencies, andthis will have the eﬀect of attenuating the stop-band
error with the weight of K −1 (z) (which is very large)
while maintaining reasonable pass-band characteristic.
Unfortunately, however, due to the very small gain ofK(z) in the stop-band, this will make the solution of
the approximation problem Fig. 3 numerically hard.
Neither the Nehari shuﬄe nor the LMI method gave asatisfactory result in this case. Hence one should sacriﬁce some stop-band attenuation to obtain a reasonable
W (z). There is also a trade-oﬀ, empirically observed,
between the stop-band attenuation and the pass-band
ripples.

Magnitude Response

1.4
Nehari Shuffle

1.2

1

Magnitude

Original

0.8

0.6

0.4

0.2
LMI

0
0

0.2

0.1

0.3

0.4

0.5

Frequency [rad/sec]

Kootsookos and Bitmead [4] thus employed the weightas depicted in Fig. 4. To be precise, the frequency response shown here is the inverse of the para-Hermitian
conjugate of the weight function. The reason for taking
the para-Hermitian conjugate is that the Nehari shufﬂe makes use of causal approximations of anti-causal
transfer functions, so that we must us reciprocals of
the poles and zeros. Then by taking the inverse, theweight attenuates the stop-band by the inverse of its
gain and approximately shapes the pass-band as it isin the pass band. On the other hand, for the FIR approximation as in Fig. 3, we simply take the inverse ofthis weight, since we do not need to make the weightanti-stable.

Figure 5: Gain responses of FIR approximants with weightfunction in Fig. 4: H ∞ via LMI (solid); Nehari
shuﬄe (dots); original IIR Chebyshev ﬁlter (- ·-)The gain responses of the obtained FIR ﬁlters based on
the Nehari shuﬄe and Theorem 1 are given in Fig. 5.
Fig. 6 shows their phase plots.

Phase Response

500
0

We see that the gain of the H ∞ approximant shows
smaller pass-band ripples and better stop-band attenuation than for the Nehari shuﬄe. The phase characteristics are about the same up to the edge of thetransition band.

Original-500

Phase [degree]-1000

Fig. 7 shows the error magnitude response. The designby the LMI method has the advantage of 5–7 dB over
the one by the Nehari shuﬄe.

Nehari Shuffle

-1500

LMI

-2000

-2500
-3000
-3500

-4000
-4500
0

0.1

0.2

0.3

0.4

0.5

Frequency [rad/sec]

3.2 Trade-oﬀ Between Pass-Band and Stop-Band
Characteristics
The design in the previous subsection depends crucially on the weighting function. It may be considered desirable to obtain smaller pass-band ripples while
maintaining reasonable stop-band attenuation. In thissection we attempt to see how the choice of a weighting
function aﬀects the overall approximation.

981-04-6440-1/02/$10.00 © 2002 ASCC

Figure 6: Phase plots of FIR approximants with weightfunction in Fig. 4: H ∞ via LMI (solid); Nehari
shuﬄe (dots); Chebyshev (- · -)

2011

1.4

Error Magnitude Response-5

1.2

Nehari Shuffle

Error Magnitude [dB]

-10

W1

1

-15
0.8

-20
0.6

LMI
-25

W2

0.4

-30
0.2
W3

-35
0

0.1

0.2
0.3
Frequency [rad/sec]

0.5

0.4

0

0.05

Figure 7: Gain of the error K − Kf : H ∞ design via LMI

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.5

Figure 8: Inverse of the gain of the weighting functions(solid); Nehari shuﬄe (dots)

tained using W2 and W3 . Note also that the design
resulting from W3 approximates the phase characteristic of the original ﬁlter up to the edge of the stop-band
as Fig. 10 shows.

We consider the following three weighting functions:
W1

=

W2

=

W3

0.7661z 2 − 1.305z + 0.675,
z 2 − 1.735z + 0.9289
0.2831z 4 − 0.5515z 3 + 0.5416z 2
z 4 − 2.865z 3 + 3.6z 2−0.2708z + 0.05882,−2.268z + 0.6056
7=60.01444z − 0.007838z + 0.01902z
z 7 − 4.229z 6 + 8.561z 5

1.4

W3

1.2

1
original

5
0.8−0.004448 + 0.006697z 3 − 0.0001857z 2−10.43z 4 + 8.172z 3 − 4.089z 2

0.6

0.4

+0.0005287z + 1.134e−5.
+1.206z − 0.1613

W1

These functions W1 , W2 , W3 are, respectively, obtained as the 2nd, 4th, 7th-order Hankel norm approximations [5] of the IIR Chebyshev ﬁlter to be approximated. The weight W2 is the same as that used in theprevious section. Their magnitude frequency responses
are shown in Fig. 8.

0
0

0.5

1

1.5

2

2.5

3

Figure 9: Gain responses of FIR ﬁlters via LMI

Fig. 9 and Fig. 10 show the resulting gain and phase responses of the FIR ﬁlters designed with the respective
weighting functions. Fig. 9 in particular shows that
there is a clear trade-oﬀ between the magnitude of thepass-band ripples and the stop-band attenuation. Thatis, if we attempt to decrease the stop-band error, wemust sacriﬁce the pass-band characteristic (i.e., accept
larger ripples), and vice versa.

4 Conclusion
We have given an LMI solution to the optimal H ∞ approximation of IIR ﬁlters via FIR ﬁlters. A comparison
with the Nehari shuﬄe is made with a numerical example, and it is observed that the LMI solution generally
performs better. Another numerical study also indicates that there is a trade-oﬀ between the pass-bandand stop-band approximation characteristics.

Fig. 11 shows the error magnitude responses. Table
1 also shows the H ∞ and H 2 error norms. Interestingly, the design via W1 exhibits the best overall approximation in both performance measures, although
its stop-band attenuation is not as good as those ob-

981-04-6440-1/02/$10.00 © 2002 ASCC

W2

0.2

2012

0

References−500[1] S. Boyd, L. E. Ghaoui, E. Feron and V. Balakrishnan, Linear Matrix Inequalities in Systems andControl Theory, SIAM, 1994.

−1000
orignalW1−1500[2] P. Gahinet, A. Nemirovski, A. J. Laub and M. Chilali, LMI Control Toolbox, the Math Works Inc. ,
1995

W3
−2000

W2

−2500

[3] P. J. Kootsookos, R. B. Bitmead and M. Green,“The Nehari shuﬄe: FIR(q) ﬁlter design with guaranteed error bounds,” IEEE Trans. Signal Processing, SP-40: 1876–1883, 1992.

−3000

−3500

−4000

−4500
0

0.5

1

1.5

2

2.5

[4] P. J. Kootsookos and R. B. Bitmead, “The Nehari
shuﬄe and minimax FIR ﬁlter design,” in Control
and Dynamic Systems, Academic Press, 64: 239–
298, 1994.

3

Figure 10: Phase responses of FIR ﬁlters via LMI[5] G. Obinata and B. D. O. Anderson, Model Reduction for Control System Design, Springer-Verlag,
2001.

0.3

W3

[6] Y. Yamamoto, A. G. Madievski and B. D. O.
Anderson, “Approximation of frequency response
for sampled-data control systems,” Automatica, 35:
729–734, 1999.

0.2[7] G. Zelniker and F. J. Taylor, Advanced Digital Signal Processing, Dekker , 1994.
W1
0.1

W2

0
0

0.1

0.2

0.3

0.4

0.5

Figure 11: Gain responses of the error Kf − K

Table 1: H ∞ and H 2 error norm
H ∞ error norm
H 2 error norm

W1
0.09540.0713W2
0.18380.0840W3
0.26270.1333

Acknowledgment The authors wish to thank Dr. P.
Kootsookos and Professor R. Bitmead for providing uswith detailed data of the weighting function in Fig. 4,
and particularly the MATLAB routines generating it.

981-04-6440-1/02/$10.00 © 2002 ASCC

2013