Multidim Syst Sign Process (2010) 21:3–23 DOI 10.1007/s11045-009-0092-5
Simple state-space formulations of 2-D frequency transformation and double bilinear transformation Shi Yan · Natsuko Shiratori · Li Xu
Received: 25 December 2008 / Revised: 19 June 2009 / Accepted: 7 July 2009 / Published online: 24 July 2009 © Springer Science+Business Media, LLC 2009
Abstract In this paper, an explicit relationship between the two-dimensional (2-D) frequency transformation and the theory of linear fractional transformation (LFT) representation is shown. Based on this relationship, a simple alternative state-space formulation of 2-D frequency transformation for 2-D digital filters is derived by utilizing the well-known Redheffer star product of LFT representations. The proposed formulation is then utilized to establish a simple relationship between the state-space representations of a 2-D continuous system and a 2-D discrete system which are related by the double bilinear transformation. Moreover, the inherent relations among the proposed formulations and the existing results are discussed. It turns out that all the existing results given in the literature can be unified as special or equivalent cases by the new state-space formulation of 2-D frequency transformation in a very concise and elegant form. Numerical examples are given to illustrate the effectiveness of the proposed formulations. Keywords Roesser state-space model · 2-D digital filters · 2-D frequency transformation · Double bilinear transformation · Linear fractional transformations 1 Introduction It is well known that the frequency transformation is a simple and useful method for design of one-dimensional (1-D) and two-dimensional (2-D) digital filters (Constantinides 1970;
This work was partially supported by JSPS.KAKENHI 19560048. S. Yan · N. Shiratori · L. Xu (B) Department of Electronics and Information Systems, Akita Prefectural University, Akita 015-0055, Japan e-mail:
[email protected] S. Yan e-mail:
[email protected] N. Shiratori e-mail:
[email protected]
123
4
Multidim Syst Sign Process (2010) 21:3–23
Pendergrass et al. 1976; Chakrabarti and Mitra 1977; Lu and Antoniou 1992). By utilizing 1-D and/or 2-D all-pass filters as transforming functions, a given prototype digital filter can be transformed to a new one which possesses certain desired frequency characteristic such as low-pass of different cutoff, high-pass, band-pass and bandstop (Pendergrass et al. 1976; Chakrabarti and Mitra 1977). A typical advantage of this approach is that it preserves the stability of the prototype filter in the transformed filter. That is, the stability of the filter obtained by a suitable frequency transformation will be automatically guaranteed as long as the original prototype filter is stable (Pendergrass et al. 1976; Chakrabarti and Mitra 1977). This property is particularly useful in the synthesis of stable digital filters with variable or tunable frequency characteristics (see, e.g., Pendergrass et al. 1976; Matsukawa and Kawamata 2001). Another well-used transformation is the bilinear transformation which can be viewed as a special case of frequency transformation and has various engineering applications such as the design of digital filters from analog ones, stability tests of discrete systems and numerical integration by transforming a differential equation into a difference equation (Bose and Jury 1974; Jury and Ruridant 1986; Lu and Antoniou 1992). Though these transformations are usually described in terms of transfer functions, it has particular advantages to express them by means of state-space formulations (Mullis and Roberts 1976; Agathoklis and Kanellakis 1992; Agathoklis 1993; Yan et al. 2007). For instance, it is just based on a state-space formulation of the 1-D frequency transformation for 1-D digital filters that the invariance of the minimum attained value of roundoff noise under any 1-D frequency transformation has been clarified by Mullis and Roberts (1976). State-space formulations of the 1-D frequency transformation and the double bilinear transformation for 2-D digital filters have been given in Lodge and Fahmy (1982), Agathoklis and Kanellakis (1992), Agathoklis (1993) and Koshita and Kawamata (2004, 2005). Based on the state-space formulations obtained in Koshita and Kawamata (2004), it has been shown that, under certain conditions, the value of roundoff noise in a 2-D separable denominator digital filter remains constant even if the frequency characteristic of the filter is changed by 1-D frequency transformation (Koshita and Kawamata 2005). This invariance property provides a valuable way to synthesize variable digital filters with minimum roundoff noise (see Koshita and Kawamata (2005) for detailed discussions on this and some other nice properties of frequency transformation as well as their applications). However, for the general case of 2-D nonseparable denominator digital filters, the clarification of such invariance property still remains an open problem, though it has attracted considerable attention of many researchers (Koshita and Kawamata 2005; Lu and Antoniou 1992; Hinamoto et al. 2002). The first difficulty we meet here is how to establish a state-space formulation, ideally a simple one, for the general 2-D frequency transformation such that the relationship between the roundoff noises of the prototype filter and the transformed filter may be investigated via the formulation. Very recently, a state-space formulation of the general 2-D frequency transformation for 2-D digital filters has been proposed in Yan et al. (2007) by extending the techniques used in Mullis and Roberts (1976) to the 2-D case. However, all the formulations for 2-D digital filters obtained in Agathoklis and Kanellakis (1992), Agathoklis (1993), Koshita and Kawamata (2004, 2005) and Yan et al. (2007) possess much more complicated forms than the one for 1-D filters given in Mullis and Roberts (1976). We have then a very natural question whether it is possible to establish a simpler state-space formulation, similar to its 1-D counterpart in Mullis and Roberts (1976), for the 2-D case, which motivated this research. The purpose of this paper is to show a positive answer to the above question by proposing a new approach based on the theory of linear fractional transformation (LFT) representation
123
Multidim Syst Sign Process (2010) 21:3–23
5
(Zhou et al. 1996; Zerz 1999). The paper is organized as follows. In the next section, some necessary preliminaries are given. In Sect. 3, as the main results of the paper, an explicit relationship between the 2-D frequency transformation and the theory of LFT representation will be established, and then a simple alternative state-space formulation of 2-D frequency transformation for 2-D digital filters is derived by utilizing the well-known Redheffer star product of LFT representations (Redheffer 1960; Zhou et al. 1996). Moreover, the proposed formulation is utilized to establish a simple relationship between the state-space representations of the considered continuous and discrete systems which are related by the double bilinear transformation. In Sect. 4, the inherent relations among the proposed formulations and the existing results are discussed. It turns out that all the results given in Mullis and Roberts (1976), Lodge and Fahmy (1982), Agathoklis and Kanellakis (1992), Agathoklis (1993), Koshita and Kawamata (2004, 2005) and Yan et al. (2007) can be unified as special or equivalent cases by the new state-space formulation of 2-D frequency transformation in a very concise and elegant form. Numerical examples are shown in Sect. 5 to illustrate the effectiveness of the proposed formulations. Conclusions are given in Sect. 6.
2 Preliminaries 2.1 The discrete and continuous 2-D state-space models Consider a 2-D discrete system represented by the 2-D Roesser (local) state-space model (Roesser 1975): x (n 1 , n 2 ) = Ax(n 1 , n 2 ) + Bu(n 1 , n 2 ) y(n 1 , n 2 ) = C x(n 1 , n 2 ) + Du(n 1 , n 2 ) where
(1)
h x h (n 1 , n 2 ) x (n 1 + 1, n 2 ) (n , n ) = , x , 1 2 x v (n 1 , n 2 ) x v (n 1 , n 2 + 1) b A1 A2 , B = 1 , C = [ c1 c2 ], D = d; A= A3 A4 b2
x(n 1 , n 2 ) =
x h (n 1 , n 2 ) ∈ Rr1 and x v (n 1 , n 2 ) ∈ Rr2 are the horizontal and vertical state vectors, respectively; u(n 1 , n 2 ) and y(n 1 , n 2 ) are the scalar input and output, respectively; A, B, C and D are real coefficient matrices with suitable sizes. In particular, A1 ∈ Rr1 ×r1 , A4 ∈ Rr2 ×r2 . The state-space representation (1) is also simply denoted by (A, B, C, D) and the transfer function of (1) is given by H (z 1 , z 2 ) = C Z (Ir − AZ )−1 B + D where
Z=
z 1 Ir1 0 , r = r1 + r2 . 0 z 2 Ir2
(2)
(3)
Note that z 1 and z 2 can be viewed as the horizontal and vertical unit delay operators, respectively (see, e.g., Bose 1982). In addition, special attention should be paid to the structure of Z where z 1 only appears in the first diagonal block entry while z 2 only in the second one. To specify a 2-D Roesser state-space model, besides the coefficient matrices A, B, C, D, we have also to know the structure of Z with the sizes r1 , r2 .
123
6
Multidim Syst Sign Process (2010) 21:3–23
Fig. 1 Feedback interpretation of LFT
The 2-D continuous state-space model (Lodge and Fahmy 1982; Xu et al. 2005) being considered here is described by h ∂ h xˆ (t1 , t2 ) ∂t1 xˆ (t1 , t2 ) = A ˆ + Bˆ u(t ˆ 1 , t2 ) ∂ v xˆ v (t1 , t2 ) ∂t2 xˆ (t1 , t2 ) h xˆ (t1 , t2 ) ˆ yˆ (t1 , t2 ) = C (4) + Dˆ u(t ˆ 1 , t2 ) xˆ v (t1 , t2 ) where Aˆ =
Aˆ 1 Aˆ 2 , Aˆ 3 Aˆ 4
bˆ Bˆ = ˆ1 , Cˆ = cˆ1 cˆ2 , b2
ˆ Dˆ = d;
xˆ h (t1 , t2 ) ∈ Rrˆ1 and xˆ v (t1 , t2 ) ∈ Rrˆ2 are the horizontal and vertical state vectors, respecˆ B, ˆ Cˆ and Dˆ are tively; u(t ˆ 1 , t2 ) and yˆ (t1 , t2 ) are the scalar input and output, respectively; A, real coefficient matrices with suitable sizes. The transfer function of (4) is given by
where
ˆ rˆ − Aˆ S) ˆ −1 Bˆ + Dˆ Hˆ (s1 , s2 ) = Cˆ S(I
(5)
−1 s I 0 Sˆ = 1 rˆ1 −1 , rˆ = rˆ1 + rˆ2 . 0 s2 Irˆ2
(6)
Note the structure of Sˆ and that s1 and s2 can be viewed as partial differential operators in the horizontal and vertical directions, respectively. 2.2 Linear fractional transformation and Redheffer star product Since the LFT and the Redheffer star product of LFTs (Redheffer 1960; Doyle et al. 1991; Zhou et al. 1996; Cockburn 2000; Zerz 2000) will play a central role in this paper, a brief review is given here. Consider a partitioned matrix P11 P12 P= (7) ∈ C( p1 + p2 )×(q1 +q2 ) P21 P22 and ∈ Cq1 × p1 . Then the (upper) LFT of is defined as (see, e.g., Zhou et al. 1996) F (P, ) P22 + P21 (I − P11 )−1 P12 .
An LFT, F (P, ), is said to be well-posed if I − P11 is invertible.
123
(8)
Multidim Syst Sign Process (2010) 21:3–23
7
Fig. 2 The Redheffer star product of LFTs
The usefulness of LFT in system theory can be interpreted by using the feedback loop representation shown in Fig. 1. The corresponding equations to the feedback loop representation are z P11 P12 w = (9) y u P21 P22 and w = z.
(10)
Assuming the well-posedness, i.e., the invertibility of (I − P11 ), we can easily see that z = (I − P11 )−1 P12 u
(11)
y = P21 (I − P11 )−1 P12 + P22 u.
(12)
and hence
That is, the LFT F (P, ) can just be viewed as the closed-loop transfer function from u to y (Zhou et al. 1996; Zerz 2000; Cockburn 2000). An important property of LFTs is that any interconnection of LFTs is again an LFT, and the Redheffer star product is one of the most fundamental interconnection structures (Redheffer 1960; Zhou et al. 1996). Suppose that Q and K are compatibly partitioned matrices Q 11 Q 12 K 11 K 12 Q= , K = (13) Q 21 Q 22 K 21 K 22 such that I − Q 22 K 11 is invertible. Then the Redheffer star product of Q and K , as shown in Fig. 2, is given by S11 S12 QK (14) S21 S22 with S11 = Q 11 + Q 12 K 11 (I − Q 22 K 11 )−1 Q 21 , S12 = Q 12 (I − K 11 Q 22 )−1 K 12 , S21 = K 21 (I − Q 22 K 11 )−1 Q 21 , S22 = K 22 + K 21 Q 22 (I − K 11 Q 22 )−1 K 12 .
(15)
123
8
Multidim Syst Sign Process (2010) 21:3–23
¯ is a matrix of suitable dimension such that u 1 = y ¯ 1 and the required Note that, if well-posedness holds, then it follows from Fig. 2 that
¯ F K , F Q,
¯ . = F Q K,
(16)
2.3 2-D frequency transformation for 2-D digital filters Let H (z 1 , z 2 ) be a given 2-D prototype digital filter which has a Roesser state-space representation (A, B, C, D) satisfying (1) and (2). Then, a new 2-D digital filter Hd (z 1 , z 2 ) with a desired frequency characteristic can be obtained by the 2-D frequency transformation (Pendergrass et al. 1976; Chakrabarti and Mitra 1977) Hd (z 1 , z 2 ) = H (z 1 , z 2 )|z 1 ←T1 (z 1 ,z 2 ),z 2 ←T2 (z 1 ,z 2 )
(17)
where Ti (z 1 , z 2 ), i = 1, 2, are certain suitable 2-D all-pass filters having, respectively, the Roesser state-space representations (αi , βi , γi , δi ), i = 1, 2, such that −1 βi + δi Ti (z 1 , z 2 ) = γi Z Ti Iqi − αi Z Ti
(18)
with Z Ti = diag{z 1 Iqi1 , z 2 Iqi2 }, qi = qi1 + qi2 , i = 1, 2. Then, the first problem we are interested in can be stated as follows. Problem 1 Establish a 2-D state-space formulation, in terms of (A, B, C, D) and (αi , βi , γi , δi ), i = 1, 2, to generate a Roesser state-space representation (A, B, C , D) for the transformed filter Hd (z 1 , z 2 ) such that Hd (z 1 , z 2 ) = CZ (I R − AZ )−1 B + D
(19)
with Z = diag{z 1 I R1 , z 2 I R2 }, and R1 , R2 , R = R1 + R2 being certain integers. Remark 1 We would like to emphasize that the key point here is to establish a closed-form formula that can explicitly reflect the relation of the state-space representation (A, B, C , D) of Hd (z 1 , z 2 ) to the given state-space representations (A, B, C, D) and (αi , βi , γi , δi ), i = 1, 2, and this is substantially different to the problem of constructing merely a state-space realization of Hd (z 1 , z 2 ). If only a state-space realization of Hd (z 1 , z 2 ) is interested in, then one may just apply any of the existing LFT representation or n-D system realization approaches to construct such a realization directly from the transfer function Hd (z 1 , z 2 ) (Cockburn and Morton 1997; Cockburn 2000; Hecker 2007; Hecker and Varga 2004, 2006; Xu et al. 2008; Zerz 1999). In fact, even in this case, a realization produced by the proposed state-space formulation may have lower order than the one directly constructed from Hd (z 1 , z 2 ), as shown later in Sect. 5. Problem 1 has recently been considered in Yan et al. (2007) approach has and a two-stage been proposed. In the first stage, a state-space representation A¯ , B¯ , C¯, D¯ of the transformed filter Hd (z 1 , z 2 ), which is not in the standard Roesser model form (see Yan et al. 2007 for the details), can be obtained from (A, B, C, D) given in (1) and (αi , βi , γi , δi ), i = 1, 2, with A¯ =
123
A¯ 1 A¯ 3
A¯ 2 , B¯ = A¯ 4
B¯1 , C¯ = C¯1 C¯2 , D¯ , ¯ B2
(20)
Multidim Syst Sign Process (2010) 21:3–23
9
where
A¯ 1 = Ir1 ⊗ α1 + A1 F −1 + δ2 A2 G −1 A3 (Ir1 − δ1 A1 )−1 ⊗ (β1 γ1 ),
A¯ 2 = F −1 A2 (Ir2 − δ2 A4 )−1 ⊗ (β1 γ2 ), A¯ 3 = G −1 A3 (Ir1 − δ1 A1 )−1 ⊗ (β2 γ1 ),
A¯ 4 = Ir2 ⊗ α2 + A4 G −1 + δ1 A3 F −1 A2 (Ir2 − δ2 A4 )−1 ⊗ (β2 γ2 ),
B¯1 = F −1 b1 + δ2 F −1 A2 (Ir2 − δ2 A4 )−1 b2 ⊗ β1 , B¯2 = G −1 b2 + δ1 G −1 A3 (Ir1 − δ1 A1 )−1 b1 ⊗ β2 , C¯1 = c1 F −1 + δ2 c2 G −1 A3 (Ir1 − δ1 A1 )−1 ⊗ γ1 , C¯2 = c2 G −1 + δ1 c1 F −1 A2 (Ir2 − δ2 A4 )−1 ⊗ γ2 ,
D¯ = d + δ1 c1 F −1 b1 + δ2 A2 (Ir2 − δ2 A4 )−1 b2
+δ2 c2 G −1 b2 + δ1 A3 (Ir1 − δ1 A1 )−1 b1
(21)
and −1 A3 , F = Ir1 − δ1 A1 − δ1 δ2 A2 Ir2 − δ2 A4 −1 G = Ir2 − δ2 A4 − δ1 δ2 A3 Ir1 − δ1 A1 A2 .
(22)
In the second stage, a standard 2-D Roesser state-space representation (A, B, C , D) for Hd (z 1 , z 2 ) can be obtained, by applying the linear transformation or permutation matrix M defined in Yan et al. (2007), as A = M A¯ M T , B = M B¯ , C = C¯ M T , D = D¯ .
(23)
However, it is seen that the state-space formulation given by (20)–(23) is rather complicated. In Sect. 3, it will be shown, as the main result of this paper, that a much simpler state-space formulation of 2-D frequency transformation can be established. 2.4 Double bilinear transformation for 2-D systems The double bilinear transformation is defined by Bose (1982), Lodge and Fahmy (1982), Agathoklis and Kanellakis (1992) and Agathoklis (1993) sk =
1 1 − zk , λk 1 + z k
zk =
1 − λk sk , 1 + λk sk
k = 1, 2.
(24)
For simplicity, however, it is supposed that λk = 1, k = 1, 2 in the sequel, as the case for general λk , k = 1, 2, can be discussed in the very same way. Let H˜ (z 1 , z 2 ) be a 2-D discrete system and Hˆ (s1 , s2 ) be a 2-D continuous system. These two systems are said to be related by the double bilinear transformation (24) if
1 − z1 1 − z2 ; , 1 + z1 1 + z2
1 − s1 1 − s2 Hˆ (s1 , s2 ) = H˜ . , 1 + s1 1 + s2
H˜ (z 1 , z 2 ) = Hˆ
(25) (26)
123
10
Multidim Syst Sign Process (2010) 21:3–23
˜ B, ˜ C, ˜ D) ˜ and ( A, ˆ B, ˆ C, ˆ D) ˆ are the 2-D discrete and continuous Roesser Suppose that ( A, ˜ ˆ state-space realizations of H (z 1 , z 2 ) and H (s1 , s2 ), respectively, such that ˜ H˜ (z 1 , z 2 ) = C˜ Z˜ (Ir˜ − A˜ Z˜ )−1 B˜ + D, −1 ˆ ˆ ˆ ˆ ˆ ˆ ˆ (27) H (s1 , s2 ) = C S(Irˆ − A S) B + D with Z˜ = diag{z 1 Ir˜1 , z 2 Ir˜2 }, r˜ = r˜1 + r˜2 , Sˆ = diag s1−1 Irˆ1 , s2−1 Irˆ2 , rˆ = rˆ1 + rˆ2 . Then, the second problem we are interested in can be stated as follows. ˜ B, ˜ C, ˜ D) ˜ and a continProblem 2 Establish a relationship between a discrete system ( A, ˆ ˆ ˆ ˆ uous system ( A, B, C, D) such that they are related by the double bilinear transformation. ˆ B, ˆ C, ˆ D), ˆ find a formulation to calculate ( A, ˜ B, ˜ C, ˜ D) ˜ from ( A, ˆ B, ˆ C, ˆ D), ˆ That is, given ( A, or vice versa, such that (25) and (26) are satisfied. Though this problem has been considered by several researchers and some formulations can be found in Lodge and Fahmy (1982), Agathoklis and Kanellakis (1992) and Agathoklis (1993), it will be shown that a new relationship can be established in a much simpler form. It is easy to see that Problem 2 can be viewed as a special case of Problem 1. That is, the double bilinear transformation (25) and (26) can be expressed as H˜ (z 1 , z 2 ) = Hˆ (s1 , s2 )|s −1 ←Tˆ −1 (z 1 ),s −1 ←Tˆ −1 (z 2 ) ;
(28)
Hˆ (s1 , s2 ) = H˜ (z 1 , z 2 )|z 1 ←T˜1 (s1 ),z 2 ←T˜2 (s2 )
(29)
1
1
2
2
where Tˆk (z k ) =
1−z k 1+z k ,
T˜k (sk ) =
1−sk 1+sk ,
k = 1, 2.
(30)
Therefore, in what follows, we will first focus on Problem 1 and then show how to apply the results obtained for Problem 1 to Problem 2.
3 New state-space formulations In this section, an explicit relationship between the theory of LFT representation and 2-D frequency transformation will be clarified, and based on this relationship a new concise statespace formulation of the general 2-D frequency transformation will be derived by utilizing the Redheffer star product of LFT representations (Redheffer 1960; Zhou et al. 1996). Then, the obtained results will be used to establish a simple relationship between the 2-D discrete and continuous systems related by the double bilinear transformation. 3.1 Formulation of 2-D frequency transformation Comparing (1) and (9) and noting that x(n 1 , n 2 ) = Z x (n 1 , n 2 ) (with z 1 , z 2 viewed as delay operators), it is easy to see that the transfer function (2) is in fact an LFT representation of the 2-D state-space filter (1), and thus can be shown as in Fig. 3. That is, we can express H (z 1 , z 2 ) as
A B with = . C D
123
H (z 1 , z 2 ) = F ( , Z )
(31)
Multidim Syst Sign Process (2010) 21:3–23
11
Fig. 3 An LFT representation of a 2-D state-space digital filter
Then, the 2-D frequency transformation (17) can be expressed as Hd (z 1 , z 2 ) = H (z 1 , z 2 )|z 1 ←T1 (z 1 ,z 2 ),z 2 ←T2 (z 1 ,z 2 ) = C Z (Ir − AZ )−1 B + D |z 1 ←T1 (z 1 ,z 2 ),z 2 ←T2 (z 1 ,z 2 ) = C Z T (Ir − AZ T )−1 B + D = F ( , Z T )
(32)
where
Z T = Z |z 1 ←T1 (z 1 ,z 2 ),z 2 ←T2 (z 1 ,z 2 ) =
Ir1 ⊗ T1 (z 1 , z 2 ) 0 0 Ir2 ⊗ T2 (z 1 , z 2 )
(33)
and ⊗ denotes the Kronecker product of matrices (Lancaster and Tismenetsky 1985). Equations (32) and (33) imply that replacing Z by Z T in Fig. 3 results in an LFT representation of the desired filter Hd (z 1 , z 2 ). In what follows, a Roesser state-space realization (α, β, γ , δ) of Z T will first be constructed in terms of the state-space realizations (αi , βi , γi , δi ) of Ti (z 1 , z 2 ), i = 1, 2. Then, it is shown that the 2-D frequency transformation can be formulized as the Redheffer star product of LFT representations stated in Sect. 2, and a new formulation to generate the Roesser state-space representation (A, B, C , D) of Hd (z 1 , z 2 ) will be derived in terms of (α, β, γ , δ) and (A, B, C, D) by directly utilizing the Redheffer star product. In view of the following properties of Kronecker product (see, e.g., Lancaster and Tismenetsky 1985): (M1 ⊗ M2 )(M3 ⊗ M4 ) = (M1 M3 ) ⊗ (M2 M4 ), (M1 ⊗ M2 )−1 = M1−1 ⊗ M2−1 ,
(34)
it is easy to see from (18) that Iri ⊗ Ti (z 1 , z 2 ) = Iri ⊗ [γi Z Ti (Iqi − αi Z Ti )−1 βi + δi ] = (Iri ⊗ γi )(Iri ⊗ Z Ti )[Iri ⊗ Iqi − (Iri ⊗ αi ) ×(Iri ⊗ Z Ti )]−1 (Iri ⊗ βi ) + Iri ⊗ δi ,
(35)
i = 1, 2. It follows then from (33) and (35) that ¯ Z¯ ) Z T = γ¯ Z¯ (I R − α¯ Z¯ )−1 β¯ + δ¯ = F ( , where ¯ =
α¯ β¯ , γ¯ δ¯
Z¯ =
(36)
0 Ir1 ⊗ Z T1 , 0 Ir2 ⊗ Z T2
123
12
Multidim Syst Sign Process (2010) 21:3–23
0 0 Ir1 ⊗ β1 Ir1 ⊗ α1 ¯ , β= , α¯ = 0 Ir2 ⊗ α2 0 Ir2 ⊗ β2 0 0 I ⊗ γ1 I ⊗ δ1 γ¯ = r1 , δ¯ = r1 , 0 Ir2 ⊗ γ2 0 Ir2 ⊗ δ2
(37)
and R = r1 × q1 + r2 × q2 . ¯ γ¯ , δ) ¯ gives a kind of state-space representation for The result of (36) means that (α, ¯ β, the 2-D transfer matrix Z T . However, it is trivial to confirm that the diagonal block entries of Z¯ = diag{Ir1 ⊗ Z T1 , Ir2 ⊗ Z T2 } are in the form of Iri ⊗ Z Ti = diag {z 1 Iqi1 , z 2 Iqi2 , . . . , z 1 Iqi1 , z 2 Iqi2 }, i = 1, 2.
ri pairs That is, Z¯ does not have the structure that z 1 only appears in the first diagonal block entry ¯ γ¯ , δ) ¯ is not a Roesser state-space while z 2 only in the second one, which means that (α, ¯ β, representation of Z T . ¯ γ¯ , δ) ¯ into a standard Roesser state-space representation by applying We can convert (α, ¯ β, a block permutation matrix M ∈ R R×R satisfying Z M Z¯ M T = diag{z 1 I R1 , z 2 I R2 }
(38)
where R1 = r1 × q11 + r2 × q21 and R2 = r1 × q12 + r2 × q22 (Yan et al. 2007). Note that R = R1 + R2 and M −1 = M T . It follows then from (36) and (38) that
˜ = where
αβ γ δ
˜ Z) Z T = γ Z (I R − α Z )−1 β + δ = F ( ,
(39)
¯ γ = γ¯ M T , δ = δ. ¯ α = M α¯ M T , β = M β,
(40)
and
It is obvious from (38) and (39) that (α, β, γ , δ) is a Roesser state-space representation of Z T , which shows that there exist some state vectors s h (n 1 , n 2 ) ∈ R R1 and s v (n 1 , n 2 ) ∈ R R2 such that s (n 1 , n 2 ) = αs(n 1 , n 2 ) + βx (n 1 , n 2 ) x(n 1 , n 2 ) = γ s(n 1 , n 2 ) + δx (n 1 , n 2 )
(41)
where s(n 1 , n 2 ) =
h s h (n 1 , n 2 ) s (n + 1, n 2 ) , s (n 1 , n 2 ) = v 1 , v s (n 1 , n 2 ) s (n 1 , n 2 + 1)
and x (n 1 , n 2 ), x(n 1 , n 2 ) can be viewed as the input and output vectors to Z T , respectively. Now, first replacing Z in Fig. 3 by Z T and then replacing Z T by its Roesser state-space representation (α, β, γ , δ), we have the LFT representation of Hd (z 1 , z 2 ) shown in Fig. 4, which gives an explicit relationship between the 2-D frequency transformation and LFT representations.
123
Multidim Syst Sign Process (2010) 21:3–23
13
Fig. 4 An LFT representation for 2-D frequency transformation
As Fig. 4 has the same structure of the Redheffer star product of LFT representations shown in Fig. 2, the results of (14) and (16) can be directly applied here to obtain: ˜ Z )) Hd (z 1 , z 2 ) = F ( , Z T ) = F ( , F ( ,
AB ,Z =F C D
= CZ (I R − AZ )−1 B + D where
AB C D
˜ =
αβ A B , γ δ C D
(42)
(43)
or equivalently, A = α + β A(Ir − δ A)−1 γ , B = β(Ir − Aδ)−1 B, C = C(Ir − δ A)−1 γ , D = D + Cδ(Ir − Aδ)−1 B.
(44)
This result can be shown as in Fig. 5, which means that (A, B, C , D) is a Roesser state-space representation of Hd (z 1 , z 2 ) described by s (n 1 , n 2 ) = As(n 1 , n 2 ) + Bu(n 1 , n 2 ), y(n 1 , n 2 ) = C s(n 1 , n 2 ) + Du(n 1 , n 2 ).
(45)
The result of (44) gives a new state-space formulation of 2-D frequency transformation for 2-D digital filters, which has a much simpler form than the existing 2-D result given in Yan et al. (2007), i.e., the formulation described by (20)–(23).
123
14
Multidim Syst Sign Process (2010) 21:3–23
Fig. 5 An LFT representation of the transformed 2-D digital filter Hd (z 1 , z 2 )
3.2 Formulation of double bilinear transformation It is shown here that the state-space formulation (44) can be easily applied to Problem 2. ˆ B, ˆ C, ˆ D) ˆ to a 2-D discrete Consider first the case to transform a 2-D continuous system ( A, ˜ ˜ ˜ ˜ one ( A, B, C, D) by the double bilinear transformation (28). That is, H˜ (z 1 , z 2 ) = Hˆ (s1 , s2 )|s −1 ←Tˆ −1 (z 1 ),s −1 ←Tˆ −1 (z 2 ) 1 1 2 2 −1 ˆ ˆ ˆ ˆ ˆ ˆ = C S(Irˆ − A S) B + D |s −1 ←Tˆ −1 (z 1 ),s −1 ←Tˆ −1 (z 2 ) 1
1
2
2
= Cˆ Zˆ T (Irˆ − Aˆ Zˆ T )−1 Bˆ + Dˆ
(46)
where ˆ −1 ˆ −1 Zˆ T = S| s1 ←T1 (z 1 ),s2−1 ←Tˆ2−1 (z 2 ) 0 I ⊗ s1−1 = rˆ1 −1 −1 −1 −1 0 Irˆ2 ⊗ s2−1 s1 ←Tˆ1 (z 1 ),s2 ←Tˆ2 (z 2 ) Irˆ1 ⊗ Tˆ1−1 (z 1 ) 0 = . 0 Irˆ2 ⊗ Tˆ2−1 (z 2 )
(47)
It is trivial to see (Doyle et al. 1991; Zhou et al. 1996) that, for k = 1, 2, 1 + zk = γˆk z k (1 − αˆ k z k )−1 βˆk + δˆk , Tˆk−1 (z k ) = 1 − zk
(48)
αˆ k = 1, βˆk = 1, γˆk = 2, δˆk = 1.
(49)
with
That is, (αˆ k , βˆk , γˆk , δˆk ) is a minimal state-space realization of Tˆk−1 (z k ) (see, e.g., Kailath 1980). Then, using the results of (37) and (49) and noting that M = I2 in this case, we have ˆ γˆ , δ) ˆ of Zˆ T as a Roesser state-space realization (α, ˆ β, αˆ = γˆ =
βˆ1 Irˆ1 0 Irˆ1 0 = Irˆ , βˆ = = = Irˆ , 0 Irˆ2 0 βˆ2 Irˆ2 0 0 2Irˆ1 0 I 0 δˆ I = = 2Irˆ , δˆ = 1 rˆ1 ˆ = rˆ1 = Irˆ . (50) γˆ2 Irˆ2 0 2Irˆ2 0 Irˆ2 0 δ2 Irˆ2
αˆ 1 Irˆ1 0 0 αˆ 2 Irˆ2 γˆ1 Irˆ1 0
123
=
Irˆ1 0 0 Irˆ2
Multidim Syst Sign Process (2010) 21:3–23
15
˜ B, ˜ C, ˜ D), ˜ ( A, ˆ B, ˆ C, ˆ D) ˆ Then, replacing (A, B, C , D), (A, B, C, D) and (α, β, γ , δ) by ( A, ˆ ˆ and (α, ˆ β, γˆ , δ) in (44), respectively, we have that ˆ rˆ − A) ˆ −1 , A˜ = Irˆ + 2 A(I ˆ ˆ −1 B, B˜ = (Irˆ − A) −1 ˆ rˆ − A) ˆ , C˜ = 2C(I
ˆ −1 B. ˆ rˆ − A) ˆ D˜ = Dˆ + C(I
(51)
˜ B, ˜ C, ˜ D) ˜ to a 2-D continConsider now the case to transform a 2-D discrete system ( A, ˆ B, ˆ C, ˆ D) ˆ by utilizing the double bilinear transformation (29), i.e., uous one ( A, Hˆ (s1 , s2 ) = H˜ (z 1 , z 2 )|z 1 ←T˜1 (s1 ),z 2 ←T˜2 (s2 ) = C˜ Z˜ (Ir˜ − A˜ Z˜ )−1 B˜ + D˜ |
z 1 ←T˜1 (s1 ),z 2 ←T˜2 (s2 )
= C˜ S˜ T (Ir˜ − A˜ S˜ T )
−1
B˜ + D˜
(52)
where S˜ T = Z˜ |z 1 ←T˜1 (s1 ),z 2 ←T˜2 (s2 ) 0 Ir˜1 ⊗ T˜1 (s1 ) . = 0 Ir˜2 ⊗ T˜2 (s2 )
(53)
Again, it is easy to see that (α˜ k , β˜k , γ˜k , δ˜k ) with α˜ k = −1, β˜k = 2, γ˜k = 1, δ˜k = −1 is a minimal state-space realization of T˜k (sk ) such that −1 1 − sk T˜k (sk ) = = γk sk−1 1 − αk sk−1 βk + δk , 1 + sk
(54)
(55)
for k = 1, 2. Using the results of (37) and (54), we have a Roesser state-space realization ˜ γ˜ , δ) ˜ of S˜ T as (α, ˜ β, −Ir˜1 0 2Ir˜1 0 β˜1 Ir˜1 0 α˜ 1 Ir˜1 0 = = −Ir˜ , β˜ = = = 2Ir˜ , α˜ = 0 α˜ 2 Ir˜2 0 −Ir˜2 0 2Ir˜2 0 β˜2 Ir˜2 0 γ˜1 Ir˜1 0 I 0 −Ir˜1 0 δ˜ I γ˜ = = r˜1 = Ir˜ , δ˜ = 1 r˜1 ˜ = = −Ir˜ . (56) 0 γ˜2 Ir˜2 0 Ir˜2 0 −Ir˜2 0 δ2 Ir˜2 In the same way used previously, we see from (44) that ˜ −1 − Ir˜ , ˜ r˜ + A) Aˆ = 2 A(I ˜ −1 B, ˜ Bˆ = 2(Ir˜ + A) −1 ˜ ˆ ˜ C = C(Ir˜ + A) ,
˜ −1 B. ˜ ˜ r˜ + A) Dˆ = D˜ − C(I
(57)
The results of (51) and (57) give a new solution to Problem 2, and are obviously simpler than the existing results given in Lodge and Fahmy (1982), Agathoklis and Kanellakis (1992) and Agathoklis (1993), which will be further discussed in the next section. Remark 2 For the general case when λk = 1, k = 1, 2, are not necessarily satisfied, we will have that γˆk = 2λk , δˆk = λk in (49), and α˜ k = −1/λk , γ˜k = 1/λk in (54), while the other corresponding results can be derived in the same way used above.
123
16
Multidim Syst Sign Process (2010) 21:3–23
4 Relations to existing results The purpose of this section is to clarify the inherent relations among the new results obtained in this paper and the existing results given in Mullis and Roberts (1976), Lodge and Fahmy (1982), Agathoklis and Kanellakis (1992), Agathoklis (1993), Koshita and Kawamata (2004, 2005) and Yan et al. (2007). It turns out that all the existing results can be unified as special or equivalent cases by the new state-space formulation of 2-D frequency transformation in a very concise and elegant way. 4.1 The case for 1-D digital filters The case of 1-D frequency transformation for 1-D digital filters considered in Mullis and Roberts (1976) can be viewed as a special case of the general 2-D frequency transformation considered in this paper with (A, B, C, D) = (A1 , b1 , c1 , d), (α, β, γ , δ) = (Ir1 ⊗ α1 , Ir1 ⊗ β1 , Ir1 ⊗ γ1 , Ir1 ⊗ δ1 ), r = r1 = 0, q1 = q11 = 0 and r2 = q12 = q2 = q21 = q22 = 0. Then, (44) reduces to A = Ir1 ⊗ α1 + (Ir1 ⊗ β1 )A1 [Ir1 − (Ir1 ⊗ δ1 )A1 ]−1 (Ir1 ⊗ γ1 ), B = (Ir1 ⊗ β1 )[Ir1 − A1 (Ir1 ⊗ δ1 )]−1 b1 , C = c1 [Ir1 − (Ir1 ⊗ δ1 )A1 ]−1 (Ir1 ⊗ γ1 ),
D = d + c1 (Ir1 ⊗ δ1 )[Ir1 − A1 (Ir1 ⊗ δ1 )]−1 b1 .
(58)
In view of the properties of Kronecker product shown in (34) and the fact that δ1 is a scalar, it is easy to convert (58) into the form A = Ir1 ⊗ α1 + A1 (Ir1 − δ1 A1 )−1 ⊗ (β1 γ1 ), B = (Ir1 − δ1 A1 )−1 b1 ⊗ β1 , C = c1 (Ir1 − δ1 A1 )−1 ⊗ γ1 ,
D = d + δ1 c1 (Ir1 − δ1 A1 )−1 b1 ,
(59)
which is just the state-space formulation given in Mullis and Roberts (1976). Therefore, it is seen that the proposed formulation (44) includes the 1-D result of (59) as a special case. 4.2 The case for 2-D digital filters Due to (40), we can also express (44) as A = M A¯ M T, B = M B¯ , C = C¯ M T, D = D¯
(60)
where A¯ = α¯ + β¯ A(Ir − δ¯ A)−1 γ¯ ,
¯ r − Aδ) ¯ −1 B, B¯ = β(I C¯ = C(Ir − δ¯ A)−1 γ¯ ,
¯ r − Aδ) ¯ −1 B. D¯ = D + C δ(I
123
(61)
Multidim Syst Sign Process (2010) 21:3–23
17
By utilizing the Sherman-Morrison-Woodbury formula for the inversion of a block matrix (see, e.g., Golub and Van Loan 1996; Zhang 2005), it can be shown that F −1 δ1 F −1 A2 (Ir2 − δ2 A4 )−1 −1 ¯ (Ir − δ A) = , (62) δ2 G −1 A3 (Ir1 − δ1 A1 )−1 G −1 δ2 F −1 A2 (Ir2 − δ2 A4 )−1 F −1 ¯ −1 = (Ir − Aδ) , (63) −1 −1 δ1 G A3 (Ir1 − δ1 A1 ) G −1 where F and G are defined by (22). Then, it can be derived from (62) that M1 M2 −1 ¯ A(Ir − δ A) =
(64)
M3 M4
where M1 = A1 F −1 + δ2 A2 G −1 A3 (Ir1 − δ1 A1 )−1 ,
M2 = A2 G −1 + δ1 A1 F −1 A2 (Ir2 − δ2 A4 )−1 = F −1 A2 (Ir2 − δ2 A4 )−1 ,
M3 = A3 F −1 + δ2 A4 G −1 A3 (Ir1 − δ1 A1 )−1 = G −1 A3 (Ir1 − δ1 A1 )−1 , M4 = A4 G −1 + δ1 A3 F −1 A2 (Ir2 − δ2 A4 )−1 .
(65)
Note that the following relations, which follows directly from the Sherman–Morrison–Woodbury formula, were used in the derivation of the above results: (Ir1 − δ1 A1 )−1 A2 G −1 = F −1 A2 (Ir2 − δ2 A4 )−1 , (Ir2 − δ2 A4 )−1 A3 F −1 = G −1 A3 (Ir1 − δ1 A1 )−1 .
Substituting (62)–(65) into (61) and partitioning A¯ , B¯ , C¯ suitably as (20), we will have the result of (21) immediately. It has thus been clarified that the result (44) proposed in this paper and the result of (21) given in Yan et al. (2007) are essentially equivalent and an obvious advantage of (44) is that it owns a much simpler and more elegant form than the complicated existing result of (21). Moreover, the results of Koshita and Kawamata (2004, 2005) are restricted to the 1-D frequency transformation for 2-D filters, and are only special cases of the results of Yan et al. (2007) and this paper. 4.3 The case of double bilinear transformation From (51), it is easy to see that ˆ rˆ − A) ˆ −1 = Irˆ + 2(Irˆ − A) ˆ −1 Aˆ A˜ = Irˆ + 2 A(I ˆ −1 [(Irˆ − A) ˆ + 2 A] ˆ = (Irˆ − A) ˆ −1 (Irˆ + A), ˆ = (Irˆ − A) ˆ −1 = C(I ˆ rˆ − A) ˆ −1 [(Irˆ + A) ˆ + (Irˆ − A)] ˆ ˆ rˆ − A) C˜ = 2C(I ˆ rˆ − A) ˆ −1 (Irˆ + A) ˆ + Irˆ ]. = C[(I
(66)
Therefore, (51) can be converted into the following form: ˆ −1 (Irˆ + A), ˆ A˜ = (Irˆ − A) −1 ˆ ˆ B, B˜ = (Irˆ − A) −1 ˜ ˆ ˆ ˆ + Irˆ ] = C( ˆ A˜ + Irˆ ), C = C[(Irˆ − A) (Irˆ + A) −1 ˆ ˜ ˆ rˆ − A) Bˆ = Dˆ + Cˆ B. D˜ = Dˆ + C(I
(67)
123
18
Multidim Syst Sign Process (2010) 21:3–23
In the similar way, (57) can also be converted into Aˆ = ( A˜ − Ir˜ )( A˜ + Ir˜ )−1 , ˆ B, ˜ Bˆ = [Ir˜ − ( A˜ − Ir˜ )( A˜ + Ir˜ )−1 ] B˜ = (Ir˜ − A) −1 ˆ ˜ ˜ C = C( A + Ir˜ ) ,
˜ ˜ A˜ + Ir˜ )−1 B˜ = D˜ − Cˆ B. Dˆ = D˜ − C(
(68)
(67) and (68) are just the results obtained in Lodge and Fahmy (1982). Comparing (51) and (57) with (67) and (68), it is seen that the formulations proposed in this paper are slightly ˆ and ( A˜ − Ir˜ ) are not required. simpler as the calculations of (Irˆ + A) Moreover, in a similar way to the 2-D digital filter case, the equivalence of the results of (51) and (57) to those given in Agathoklis and Kanellakis (1992) and Agathoklis (1993) can be shown. Again, it should be noted that the results of Agathoklis and Kanellakis (1992) and Agathoklis (1993) are much more complicated than (51) and (57). In view of the above discussions, the formulation (44) can be viewed as a natural unification for all the results given in Mullis and Roberts (1976), Lodge and Fahmy (1982), Agathoklis and Kanellakis (1992), Agathoklis (1993), Koshita and Kawamata (2004, 2005) and Yan et al. (2007).
5 Numerical examples Example 1 Consider Example 1 of Yan et al. (2007). The Roesser state-space representation (A, B, C, D) for the prototype filter H (z 1 , z 2 ) is given by 1 −0.42602 0.53096 , B= , C = −0.28336 1 , D = 0.59944 A= 0.54320 −0.42602 −0.28336 which satisfies (2) with Z = diag{z 1 , z 2 }. The Roesser state-space representations (αi , βi , γi , δi ) of the applied 2-D all-pass filters Ti (z 1 , z 2 ) , i = 1, 2, are given by −0.2612 1.2612 2.7155 , β1 = , γ1 = 0.1213 1.0000 , δ1 = −0.2612, α1 = 0.2612 −0.2612 0.3294 0.7154 0.2846 −0.3258 , β2 = , γ2 = 0.6249 1.0000 , δ2 = 0.7154, α2 = −0.7154 0.7154 −0.2036 which satisfy (18) with Z Ti = diag{z 1 , z 2 }, i = 1, 2 (see Yan et al. 2007 for the details). Starting from the given (A, B, C, D) and (αi , βi , γi , δi ), i = 1, 2, we first construct the ¯ γ¯ , δ) ¯ for Z T . That is state-space realization (α, ¯ β, Z T = Z |z 1 ←T1 (z 1 ,z 2 ),z 2 ←T2 (z 1 ,z 2 ) z1 0 = 0 z 2 z ←T (z ,z ),z ←T (z ,z ) 1 1 1 2 2 2 1 2 T1 (z 1 , z 2 ) 0 = 0 T2 (z 1 , z 2 ) 0 γ1 Z T1 (I2 − α1 Z T1 )−1 β1 + δ1 = 0 γ2 Z T2 (I2 − α2 Z T2 )−1 β2 + δ2 −1 β¯ + δ¯ = γ¯ Z¯ I4 − α¯ Z¯
123
(69)
Multidim Syst Sign Process (2010) 21:3–23
where
⎤ ⎡ −0.2612 1.2612 0 0 ⎢ 0.2612 −0.2612 α1 0 0 0 ⎥ ⎥, α¯ = =⎢ ⎣ 0 α2 0 0 0.7154 0.2846⎦ 0 0 −0.7154 0.7154 ⎤ ⎡ 2.7155 0 ⎥ ⎢ 0.3294 0 β1 0 ⎥, ⎢ ¯ =⎣ β= 0 −0.3258 ⎦ 0 β2 0 −0.2036 γ1 0 0.1213 1 0 0 δ 0 −0.2612 0 γ¯ = = , δ¯ = 1 = 0 0 0.6249 1 0 0.7154 0 γ2 0 δ2
and
19
⎡ ⎢ Z¯ = ⎢ ⎣
⎤
z1
⎥ ⎥. ⎦
z2 z1 z2
¯ γ¯ , δ¯ can be directly calculated by using (37). It is clear that α, ¯ γ¯ , δ¯ is Note that α, ¯ β, ¯ β, not yet a standard Roesser state-space realization of Z T , as Z¯ is not in the required structure. Now, construct the block permutation matrix ⎤ ⎡ 1000 ⎢0 0 1 0⎥ ⎥ M =⎢ ⎣0 1 0 0⎦ 0001 such that Z = M Z¯ M T = diag{z 1 , z 1 , z 2 , z 2 }. By (40), then, we get the Roesser state-space realization (α, β, γ , δ) of Z T as ⎤ ⎤ ⎡ ⎡ 2.7155 0 −0.2612 0 1.2612 0 ⎥ ⎢ ⎢ 0 0.7154 0 0.2846 ⎥ ⎥, β = M β¯ = ⎢ 0 −0.3258 ⎥, α = M α¯ M T = ⎢ ⎦ ⎣0.3294 ⎣ 0.2612 0 −0.2612 0 ⎦ 0 0 −0.7154 0 −0.2036 0 0.7154 0.1213 0 10 −0.2612 0 T ¯ γ = γ¯ M = , δ=δ= . 0 0.6249 0 1 0 0.7154 Finally, by (44), we obtain the Roesser state-space realization (A, B, C , D) for the desired filter Hd (z 1 , z 2 ): ⎤ ⎡ ⎡ ⎤ −0.3561 0.7425 0.4790 1.1882 2.6789 ⎢ −0.0177 0.7916 −0.1458 0.4065 ⎥ ⎢ 0.1057 ⎥ ⎥ ⎢ ⎥ A=⎢ ⎣ 0.2497 0.0901 −0.3561 0.1441 ⎦, B = ⎣ 0.3250 ⎦, −0.0111 −0.6678 −0.0911 0.7916 0.0661 C = 0.0019 0.4779 0.0156 0.7648 , D = 0.4403. Though the same result on (A, B, C , D) has also been obtained in Yan et al. (2007), the complicated formulation given by (20)–(23), instead of the simple one (44), was used there. A comparison on the computation time of the method of Yan et al. (2007) and the method
123
20 Table 1 Computation time comparison
Multidim Syst Sign Process (2010) 21:3–23 Examples Example 1 Example 2
Methods
Runtime (10−4 s)
(Yan et al. 2007)
12.353
New formulation (44)
9.1122
(Lodge and Fahmy 1982)
0.4844
(Agathoklis 1993)
1.8528
New formulation (51)
0.4750
proposed in this paper can be found in Table 1, which shows that a reduction of about 26% on the computation time is reached by the new method for this example. It should be pointed out that the formulations given in Agathoklis and Kanellakis (1992) and Koshita and Kawamata (2004, 2005) cannot be applied to this example because they are only valid to the special case of 1-D frequency transformation. Remark 3 It is noted that (A, B, C , D) obtained in Example 1 has an order of 4 and is a minimal realization of Hd (z 1 , z 2 ). In fact, it can be shown that the proposed state-space formulation produces a minimal realization as long as (A, B, C, D) and (αi , βi , γi , δi ) (i = 1, 2) are minimal. As mentioned previously, in the case when only a realization of Hd (z 1 , z 2 ) itself is of interest, one can obtain a realization directly from Hd (z 1 , z 2 ) by using some existing realization method given in Cockburn and Morton (1997), Cockburn (2000), Hecker (2007), Hecker and Varga (2004, 2006), Xu et al. (2008) and Zerz (1999). This approach, however, does not necessarily generate a minimal realization of Hd (z 1 , z 2 ) even if some minimal realizations of H (z 1 , z 2 ) and Ti (z 1 , z 2 ) (i = 1, 2) can be obtained. For Example 1, we have tried the methods of Cockburn and Morton (1997), Cockburn (2000), Hecker (2007), Hecker and Varga (2004, 2006), Xu et al. (2008) and Zerz (1999) and the toolbox developed by Magni (2005), but all failed to get a minimal realization of order 4. Example 2 Consider the following 2-D continuous system Hˆ (s1 , s2 ) given in Example 2 of Lodge and Fahmy (1982): ⎤⎡ ⎡ ⎤ 1 −1 −2 1 2 4 1 s1 s1 ⎣ 2 2 2 ⎦ ⎣ s2−1 ⎦ 428 s2−2 (70) Hˆ (s1 , s2 ) = ⎡ ⎤⎡ ⎤. 1 1 0.80 0.82 −1 −2 1 s1 s1 ⎣ 0.80 0.65 0.66 ⎦ ⎣ s2−1 ⎦ 0.82 0.66 0.70 s2−2 By the methods of Cockburn and Morton (1997), Cockburn (2000), Hecker (2007), Hecker and Varga (2004, 2006), Magni (2005), Xu et al. (2008) and Zerz (1999), a 2-D Roesser stateˆ B, ˆ C, ˆ D) ˆ of Hˆ (s1 , s2 ) (with order 6) can be obtained. For example, by space realization ( A, using the method of Xu et al. (2008), we obtain the realization: ⎡ ⎤ ⎤ ⎡ 1 −0.8000 −0.6600 −0.6600 −0.8200 −0.8200 0.2319 ⎢0⎥ ⎥ ⎢ 0 0 −3.7600 0 0 −0.3838 ⎢ ⎥ ⎥ ⎢ ⎢ ⎥ ⎢ 0 0 0 0 1.0000 −0.2660 ⎥ ⎥ , Bˆ = ⎢ 0 ⎥ , Aˆ = ⎢ ⎢0⎥ ⎥ ⎢ 1.0000 0 3.8800 0 0 0.3089 ⎢ ⎥ ⎥ ⎢ ⎣0⎦ ⎣ 0 0 0 0 0 1.0000 ⎦ −0.8000 −0.6600 −0.6600 −0.8200 −0.8200 −0.8000 1 Cˆ = 1.2000 1.3400 1.3400 3.1800 3.1800 1.2000 , Dˆ = 1. (71)
123
Multidim Syst Sign Process (2010) 21:3–23
21
ˆ B, ˆ C, ˆ D) ˆ given by (20) of Note that there is perhaps some error in the realization ( A, Lodge and Fahmy (1982) as we found that the transfer function calculated from the matrices ˆ B, ˆ C, ˆ Dˆ given there is not the original Hˆ (s1 , s2 ). of A, ˜ B, ˜ C, ˜ D) ˜ related to The aim here is to find a 2-D discrete state-space realization ( A, ˆ B, ˆ C, ˆ D) ˆ by the double bilinear transformation (28). ( A, By the proposed formulation (51), the corresponding 2-D discrete state-space realization can be obtained as ⎡ ⎡ ⎤ ⎤ 0.0473 −0.3882 −0.7998 −0.4822 −1.2821 −0.4592 0.2941 ⎢ 1.4741 1.6006 −6.2825 0.7461 −5.5363 −2.3840 ⎥ ⎢ −0.4550 ⎥ ⎢ ⎢ ⎥ ⎥ ⎢ −0.3442 −0.1402 0.7111 −0.1742 1.5368 0.5566 ⎥ ⎢ 0.1062 ⎥ ⎢ ⎢ ⎥ ⎥ ˜ ˜ A=⎢ ⎥ , B = ⎢ 0.7509 ⎥ , ⎢ −0.4330 −0.9912 5.7175 −0.2315 4.4859 1.9349 ⎥ ⎢ ⎥ ⎣ −0.4689 −0.1910 −0.3936 −0.2373 0.3690 0.7583 ⎦ ⎣ 0.1447 ⎦ −0.4689 −0.1910 −0.3936 −0.2373 −0.6310 −0.2417 0.1447 C˜ = −0.6599 −1.1577 9.3719 1.5919 10.9638 6.4747 , D˜ = 3.9074. (72) ˜ B, ˜ C, ˜ D) ˜ It has been verified that the 2-D transfer function H˜ (z 1 , z 2 ) calculated from ( A, is just the same as the one obtained by directly using the double bilinear transformation (28). For simplicity, however, the details are omitted here. From the comparison shown in Table 1, we see that the new formulation is much faster than the one given in Agathoklis (1993) and almost the same to (or a bit better than) the one given in Lodge and Fahmy (1982).
6 Conclusions An explicit relationship between the 2-D frequency transformation and the theory of LFT representation has been obtained. Then, by utilizing the Redheffer star product of LFT representations, a simple alternative state-space formulation of the 2-D frequency transformation for 2-D digital filters has been derived which unifies all the existing results of Mullis and Roberts (1976), Lodge and Fahmy (1982), Agathoklis and Kanellakis (1992), Agathoklis (1993), Koshita and Kawamata (2004, 2005) and Yan et al. (2007) as special or equivalent cases in a very concise and elegant way. We believe that this is a significant step towards the challenging open problem of the invariance property analysis of 2-D digital filters under 2-D frequency transformation (Koshita and Kawamata 2005). It has been noted that the proposed formulation produces a minimal realization (A, B, C , D ) as long as (A, B, C, D) and (αi , βi , γi , δi ) (i = 1, 2) are minimal ones, though it does not guarantee the minimality in general. Another obvious advantage of the proposed formulation is that it can be implemented in, e.g., MATLAB much more easily than the existing one of Yan et al. (2007). Numerical examples have been given to illustrate the effectiveness of the proposed formulation.
References Agathoklis, P. (1993). The double bilinear transformation for 2-D systems in state-space description. IEEE Transactions on Signal Processing, 41(2), 994–996. Agathoklis, P., & Kanellakis, A. (1992). Complex domain transformations for 2-D systems in state-space description. In Proceedings of the 1992 ISCAS, Vol. 2 (pp. 710–713). San Diego, CA. Bose, N. K. (1982). Applied multidimensional system theory. New York: Van Nostrand Reinhold.
123
22
Multidim Syst Sign Process (2010) 21:3–23
Bose, N. K., & Jury, E. I. (1974). Positivity and stability tests for multidimensional filters (discrete–continuous). IEEE Transactions on Acoustics, Speech, and Signal Processing, ASSP-22(3), 174–180. Chakrabarti, S., & Mitra, S. K. (1977). Design of two-dimensional digital filters via spectral transformations. Proceedings of the IEEE, 65(6), 905–914. Cockburn, J. C. (2000). Multidimensional realizations of systems with parametric uncertainty. In Proceedings of MTNS, Perpignan, France, June 2000, Session si20a, 6 pages. Cockburn, J. C., & Morton, B. G. (1997). Linear fractional representations of uncertain systems. Automatica, 33, 1263–1271. Constantinides, A. G. (1970). Spectral transformations for digital filters. Proceedings of the Institute Electrical Engineers, 117(8), 1585–1590. Doyle, J., Packard, A., & Zhou, K. (1991). Review of LFTs, LMI, and µ. In Proceedings of the 30th IEEE conference on decision and control, Vol. 2 (pp. 1227–1232). Golub, G. H., & Van Loan, C. F. (1996). Matrix computations (3rd ed.). Baltimore: Johns Hopkins University Press. Hecker, S. (2007). Generation of low order LFT representations for robust control applications. Fortschrittberichte VDI, series 8, no. 1114. Available at: http://mediatum2.ub.tum.de/doc/601652/601652. pdf. Hecker, S., & Varga, A. (2004). Generalized LFT-based representation of parametric uncertain models. European Journal of Control, 4, 326–337. Hecker, S., & Varga, A. (2006). Symbolic manipulation techniques for low order LFT-based parametric uncertainty modelling. International Journal of Control, 79(11), 1485–1494. Hinamoto, T., Yokoyama, S., Inoue, T., Zeng, W., & Lu, W.-S. (2002). Analysis and minimization of L 2 -sensitivity for linear systems and two-dimensional state-space filters using general controllability and observability gramians. IEEE Transactions on Circuits and Systems, CAS-I-49(9), 1279–1289. Jury, E. I., & Ruridant, T. Y. (1986). On the evaluation of double square integral in the (s1 , s2 ) complex biplane. IEEE Transactions on Acoustics, Speech, and Signal Processing, ASSP-34(3), 630–632. Kailath, T. (1980). Linear systems. USA: Prentice-Hall. Koshita, S., & Kawamata, M. (2004). State-space formulation of frequency transformation for 2-D digital filters. IEEE Signal Processing Letters, 11(10), 784–787. Koshita, S., & Kawamata, M. (2005). Invariance of second-order modes under frequency transformation in 2-D separable denominator digital filters. Multidimensional Systems and Signal Processing, 16(3), 305– 333. Lancaster, P., & Tismenetsky, M. (1985). The theory of matrices (2nd ed.). New York: Academic Press. Lodge, J. H., & Fahmy, M. M. (1982). The bilinear transformation of two-dimensional state-space systems. IEEE Transactions on Acoustics, Speech, and Signal Processing, ASSP-30(3), 500–502. Lu, W.-S., & Antoniou, A. (1992). Two-dimensional digital filters. New York: Marcel Dekker. Magni, J. F. (2005). User manual of the linear fractional representation toolbox. Version 2, Technical Report. France, October 2005 (Revised Feb 2006). (http://www.cert.fr/dcsd/idco/perso/Magni/toolboxes.html). Matsukawa, H., & Kawamata, M. (2001). Design of variable digital filters based on state-space realizations. IEICE Transactions Fundamentals of Electronics, Communications and Computer Sciences, E84-A(8), 1822–1830. Mullis, C. T., & Roberts, R. A. (1976). Roundoff noise in digital filters: Frequency transformations and invariants. IEEE Transactions on Acoustics, Speech, and Signal Processing, ASSP-24(6), 538–550. Pendergrass, N. A., Mitra, S. K., & Jury, E. I. (1976). Spectral transformations for two-dimensional digital filters. IEEE Transactions on Circuits and Systems, CAS-23(1), 26–35. Redheffer, R. M. (1960). On a certain linear fractional transformation. Journal of Mathematics and Physics, 39, 269–286. Roesser, R. P. (1975). A discrete state-space model for linear image processing. IEEE Transactions on Automatic Control, 20(1), 1–10. Xu, L., Fan, H., Lin, Z., & Bose, N. K. (2008). A direct-construction approach to multidimensional realization and LFR uncertainty modeling. Multidimensional Systems and Signal Processing, 19(3–4), 323–359. Xu, S., Lam, J., Zou, Y., Lin, Z., & Paszke, W. (2005). Robust H-infinity filtering for uncertain 2-D continuous systems. IEEE Transaction on Signal Processing, 53(5), 1731–1738. Yan, S., Xu, L., & Anazawa, Y. (2007). A two-stage approach to the establishment of state-space formulation of 2-D frequency transformation. IEEE Signal Processing Letters, 14(12), 960–963. Zerz, E. (1999). LFT representations of parametrized polynomial systems. IEEE Transactions on Circuits and Systems, 46(3), 410–416. Zerz, E. (2000). Topics in multidimensional linear systems theory. Lecture Notes in Control and Information Sciences 256. London: Springer.
123
Multidim Syst Sign Process (2010) 21:3–23
23
Zhang, F. (2005). The Schur complement and its applications. New York: Springer. Zhou, K., Doyle, J. C., & Glover, K. (1996). Robust and optimal control. New Jersey: Prentice Hall.
Author Biographies Shi Yan received the B.S. and M.Eng. degrees from Lanzhou University, Lanzhou, China, in 2001 and 2004, respectively. From July 2004 to December 2006, he was an Assistant Professor at the School of Information Science and Engineering, Lanzhou University. From January 2007 to March 2007, he was a visiting researcher in Akita Prefectural University, Akita, Japan, where he is currently pursuing a Dr. Eng. degree. His research interests include multidimensional system control and signal processing.
Natsuko Shiratori received the B.Eng. degree from Akita Prefectural University, Akita, Japan, in March 2009, where she is currently pursuing a master degree. Her research interests include system control and signal processing.
Li Xu received the B.Eng. degree from Huazhong University of Science and Technology, Wuhan, China, in 1982, and the M.Eng. and Dr. Eng. degrees from Toyohashi University of Technology, Toyohashi, Japan, in 1990 and 1993, respectively. From April 1993 to March 1998, he was an Assistant Professor at the Department of Knowledge-Based Information Engineering, Toyohashi University of Technology. From April 1998 to March 2000, he was a Lecturer at the Department of Information Management, Asahi University, Gifu, Japan. Since April 2000, he has been with the Faculty of Systems Science and Technology, Akita Prefectural University, Akita, Japan, where he is currently a Professor at the Department of Electronics and Information Systems. His research interests include multidimensional system theory, signal processing and the applications of computer algebra to system theory. Dr. Xu has been an Associate Editor for the international journal of Multidimensional Systems and Signal Processing (MSSP) since 2000, and was a Guest Co-Editor for the special issue of “Applications of Gröbner Bases in Multidimensional Systems and Signal Processing” for MSSP published in 2001.
123