Open access

Partition-Matrix Theory Applied to the Computation of Generalized-Inverses for MIMO Systems in Rayleigh Fading Channels

Written By

P. Cervantes, L.F. González, F.J. Ortiz and A.D. García

Submitted: November 11th, 2011 Published: July 11th, 2012

DOI: 10.5772/48198

Chapter metrics overview

3,268 Chapter Downloads

View Full Metrics

1. Introduction

Partition-Matrix Theory and Generalized-Inverses are interesting topics explored in linear algebra and matrix computation. Partition-Matrix Theory is associated with the problem of properly partitioning a matrix into block matrices (i.e. an array of matrices), and is a matrix computation tool widely employed in several scientific-technological application areas. For instance, blockwise Toeplitz-based covariance matrices are used to model structural properties for space-time multivariate adaptive processing in radar applications [1], Jacobian response matrices are partitioned into several block-matrix instances in order to enhance medical images for Electrical-Impedance-Tomography [2], design of state-regulators and partial-observers for non-controllable/non-observable linear continuous systems contemplates matrix blocks for controllable/non-controllable and observable/non-observable eigenvalues [3]. The Generalized-Inverse is a common and natural problem found in a vast of applications. In control robotics, non-collocated partial linearization is applied to underactuated mechanical systems through inertia-decoupling regulators which employ a pseudoinverse as part of a modified input control law [4]. At sliding-mode control structures, a Right-Pseudoinverse is incorporated into a state-feedback control law in order to stabilize electromechanical non-linear systems [5]. Under the topic of system identification, definition of a Left-Pseudoinverse is present in auto-regressive moving-average models (ARMA) for matching dynamical properties of unknown systems [6]. An interesting approach arises whenever Partition-Matrix Theory and Generalized-Inverse are combined together yielding attractive solutions for solving the problem of block matrix inversion [7-10]. Nevertheless, several assumptions and restrictions regarding numerical stability and structural properties are considered for these alternatives. For example, an attractive pivot-free block matrix inversion algorithm is proposed in [7], which unfortunately exhibits an overhead in matrix multiplications that are required in order to guarantee full-rank properties for particular blocks within it. For circumventing the expense in rank deficiency, [8] offers block-matrix completion strategies in order to find the Generalized-Inverse of any non-singular block matrix (irrespective of the singularity of their constituting sub-blocks). However, the existence of intermediate matrix inverses and pseudoinverses throughout this algorithm still rely on full-rank assumptions, as well as introducing more hardness to the problem. The proposals exposed in [9-10] avoid completion strategies and contemplate all possible scenarios for avoiding any rank deficiency among each matrix sub-block, yet demanding full-rank assumptions for each scenario. In this chapter, an iterative-recursive algorithm for computing a Left-Pseudoinverse (LPI) of a MIMO channel matrix is developed by combining Partition-Matrix Theory and Generalized-Inverse concepts. For this approach, no matrix-operations’ overhead nor any particular block matrix full-rank assumptions are needed because of structural attributes of the MIMO channel matrix, which models dynamical properties of a Rayleigh fading channel (RFC) within wireless MIMO communication systems.

The content of this work is outlined as follows. Section 2 provides a description of the MIMO communication link, pointing out its principal physical effects and the mathematical model considered for RFC-based environments. Section 3 defines formally the problem of computing the Left-Pseudoinverse as the Generalized-Inverse for the MIMO channel matrix applying Partition-Matrix Theory concepts. Section 4 presents linear algebra and matrix computation concepts and tools needed for tracking a solution for the aforementioned problem. Section 5 analyzes important properties of the MIMO channel matrix derived from a Rayleigh fading channel scenario. Section 6 explains the proposed novel algorithm. Section 7 presents a brief analysis of VLSI (Very Large Scale of Integration) aspects towards implementation of arithmetic operations presented in this algorithm. Section 8 concludes the chapter. Due to the vast literature about MIMO systems, and to the best of the authors’ knowledge, this chapter provides a nice and strategic list of references in order to easily correlate essential concepts between matrix theory and MIMO systems. For instance, [11-16] describe and analyze information and system aspects about MIMO communication systems, as well as studying MIMO channel matrix behavior under RFC-based environments; [17-18] contain all useful linear algebra and matrix computation theoretical concepts around the mathematical background immersed in MIMO systems; [19-21] provide practical guidelines and examples for MIMO channel matrix realizations comprising RFC scenarios; [22] treats the formulation and development of the algorithm presented in this chapter; [23-27] detail a splendid survey on architectural aspects for implementing several arithmetic operations.

Advertisement

2. MIMO systems

In the context of wireless communication systems, MIMO (Multiple-Input Multiple-Output) is an extension of the classical SISO (Single-Input Single-Output) communication paradigm, where instead of having a communication link composed of a single transmitter-end and a receiver-end element (or antenna), wireless MIMO communication systems (or just MIMO systems) consist of an array of multiple elements at both the transmission and reception parts [11-16,19-21]. Generally speaking, the MIMO communication link contains nT transmitter-end and nR receiver-end antennas sending-and-receiving information through a wireless channel. Extensive studies on MIMO systems and commercial devices already employing them reveal that these communication systems offer promising results in terms of: a) spectral efficiency and channel capacity enhancements (many user-end applications supporting high-data rates at limited available bandwidth); b) improvements on Bit-Error-Rate (BER) performance; and c) practical feasability already seen in several wireless communication standards. The conceptualization of this paradigm is illustrated in figure 1, where Tx is the transmitter-end, Rx the receiver-end, and Chx the channel.

Figure 1.

The MIMO system: conceptualization for the MIMO communication paradigm.

Notice that information sent from the trasnmission part (Tx label on figure 1) will suffer from several degradative and distorional effects inherent in the channel (Chx label on figure 1), forcing the reception part (Rx label on figure 1) to decode information properly. Information at Rx will suffer from degradations caused by time, frequency, and spatial characteristics of the MIMO communication link [11-12,14]. These issues are directly related to: i) the presence of physical obstacles obstructing the Line-of-Sight (LOS) between Tx and Rx (existance of non-LOS); ii) time delays between received and transmitted information signals due to Tx and Rx dynamical properties (time-selectivity of Chx); iii) frequency distortion and interference among signal carriers through Chx (frequency-selectivity of Chx); iv) correlation of information between receiver-end elements. Fading (or fading mutlipath) and noise are the most common destructive phenomena that significantly affect information at Rx [11-16]. Fading is a combination of time-frequency replicas of the trasnmitted information as a consequence of the MIMO system phenomena i)-iv) exposed before, whereas noise affects information at every receiver-end element under an additve or multiplicative way. As a consequence, degradation of signal information rests mainly upon magnitude attenuation and time-frequency shiftings. The simplest treatable MIMO communication link has a slow-flat quasi-static fading channel (proper of a non-LOS indoor environment). For this type of scenario, a well-known dynamical-stochastic model considers a Rayleigh fading channel (RFC) [13,15-16,19-21], which gives a quantitative clue of how information has been degradated by means of Chx. Moreover, this type of channels allows to: a) distiguish among each information block tranmitted from the nT elements at every Chx realization (i.e. the time during which the channel’s properties remain unvariant); and b) implement easily symbol decoding tasks related to channel equalization (CE) techniques. Likewise, noise is commonly assumed to have additive effects over Rx. Once again, all of these assumptions provide a treatable information-decoding problem (refered as MIMO demodulation [12]), and the mathematical model that suits the aforementioned MIMO communication link characteristics will be represented by

y=Hx+ηE1

where: x[j]nT×1nT×1is a complex-valued nTdimensional transmitted vector with entries drawn from a Gaussian-integer finite-lattice constellation (digital modulators, such as: q-QAM, QPSK); ynR×1is a complex-valued nRdimensional received vector; ηnR×1is a nRdimensional independent-identically-distributed (idd) complex-circularly-symmetric (ccs) Additive White Gaussian Noise (AWGN) vector; and HnR×nTis the (nR×nT)dimensional MIMO channel matrix whose entries model: a) the RFC-based environment behavior according to a Gaussian probabilistic density function with zero-mean and 0.5-variance statistics; and b) the time-invariant transfer function (which measures the degradation of the signal information) between the i-th receiver-end and the j-th trasnmitter-end antennas [11-16,19-21]. Figure 2 gives a representation of (1). As shown therein, the MIMO communication link model stated in (1) can be also expressed as

[y1ynR]=[h11h1nThnR1hnRnT][x1xnT]+[η1ηnR]E2

Notice from (1-2) that an important requisite for CE purposes within RFC scenarios is that His provided somehow to the Rx. This MIMO system requirement is classically known as Channel State Information (CSI) [11-16]. In the sequel of this work, symbol-decoding efforts will consider the problem of finding x from y regarding CSI at the Rx part within a slow-flat quasi-static RFC-based environment as modeled in (1-2). In simpler words, Rx must findxfrom degradated informationythrough calculating an inversion overH. Moreover, nRnTis commonly assumed for MIMO demodulation tasks [13-14] because it guarantees linear independency between row-entries of matrix H in (2), yielding a nonhomogeneous overdetermined system of linear equations.

Figure 2.

Representation for the MIMO communication link model according toy=Hx+η. Here, each dotted arrow represents an entry hij in H which determines channel degradation between the j-th transmitter and the i-th receiver elements. AWGN appears additively in each receiver-end antenna.

Advertisement

3. Problem definition

Recall for the moment the mathematical model provided in (1). Consider Φrand Φito be the real and imaginary parts of a complex-valued matrix (vector)Φ, that is,Φ=Φr+jΦi. Then, Equation (1) can be expanded as follows:

yr+jyi=(HrxrHixi+ηr)+j(Hixr+Hrxi+ηi)E3

It can be noticed from Equation (3) that:xr,xinT×1;yr,yinR×1;ηr,ηinR×1; andHr,HinR×nT. An alternative representation for the MIMO communication link model in (2) can be expressed as

[yryi]=[HrHiHiHr][xrxi]+[ηrηi]E4

where[yryi]Y2nR×1, [HrHiHiHr]h2nR×2nT, [xrxi]X2nT×1, and [ηrηi]N2nR×1. CSI is still needed for MIMO demodulation purposes involving (4). Moreover, if Nr=2nR andNt=2nT, thenNrNt. Obviously, while seeking for a solution of signal vector X from (4), the reception part Rx will provide also the solution for signal vectorx, and thus MIMO demodulation tasks will be fulfilled. This problem can be defined formally into the following manner:

Definition 1. Given parameters Nr=2nR+andNt=2nT+, and a block-matrixhNr×Nt, there exists an operator Γ:(Nr×1×Nr×Nt)Nt×1 which solves the matrix-block equation Y=hX+N so thatΓ[Y,h]=X. ■

From Definition 1, the following affirmations hold: i) CSI over his a necessary condition as an input argument for the operatorΓ; and ii) Γcan be naïvely defined as a Generalized-Inverse of the block-matrixh. In simpler terms,X=hY

In the context of MIMO systems, this matrix operation is commonly found in Babai estimators for symbol-decoding purposes at the Rx part [12,13]. For the reader’s interest, refer to [11-16] for other MIMO demodulation techniques.

is associated with Γ[Y,h] and hNt×Nr stands for the Generalized-Inverse of the block-matrixh, where h=(hTh)1hT [17-18]. Clearly, []1and []T represent the inverse and transpose matrix operations over real-valued matrices. As a concluding remark, computing the Generalized-Inverse h can be separated into two operations: 1) a block-matrix inversion(hTh)1

Notice that and .

; 2) a typical matrix multiplication(hTh)1hT. For these tasks, Partition-Matrix Theory will be employed in order to find a novel algorithm for computing a Generalized-Inverse related to (4).

Advertisement

4. Mathematical background

4.1. Partition-matrix theory

Partition-Matrix Theory embraces structures related to block matrices (or partition matrices: an array of matrices) [17-18]. Furthermore, a block-matrix L with (n+q)×(m+p) dimension can be constructed (or partitioned) consistently according to matrix sub-blocksA, B, C, and D ofn×m,n×p , q×m, and q×p dimensions, respectively, yielding

L=[ABCD]E5

An interesting operation to be performed for these structures given in (5) is the inversion, i.e. a blockwise inversionL1. For instance, let L(n+m)×(n+m) be a full-rank real-valued block matrix (the subsequent treatment is also valid for complex-valued entities, i.e.L(n+m)×(n+m)). An alternative partition can be performed withAn×n, Bn×m, Cm×n, andDm×m. Assume also A and D to be full-rank matrices. Then,

L1=[(ABD1C)1(ABD1C)1BD1(DCA1B)1CA1(DCA1B)1]E6

This strategy (to be proved in the next part) requires additonally and mandatorily full-rank over matrices ABD1C andDCA1B. The simple case is defined for L=[abcd](indistinctly for 2×2 or2×2). Once again, assumingdet(L)0, a0, and d0(related to full-rank restictions within block-matrixL):

L1=[(abd1c)1(abd1c)1bd1(dca1b)1ca1(dca1b)1]=1adbc[dbca],

where evidently(adbc)0,(n+m)×(n+m)(abd1c)0, and(dca1b)0.

4.2. Matrix Inversion Lemma

The Matrix Inversion Lemma is an indirect consequence of inverting non-singular block matrices [17-18], either real-valued or complex-valued, e.g., under certain restrictions

Refer to [3,7-10,17,18] to review lemmata exposed for these issues and related results.

. Lemma 1 states this result.

Lemma 1. LetΨr×r,Σr×s ,ϒs×s , and Ξs×r be real-valued or complex-valued matrices. Assume these matrices to be non-singular:Ψ,ϒ ,(Ψ+ΣϒΞ) , and(ϒ1+ΞΨ1Σ). Then,

(Ψ+ΣϒΞ)1=Ψ1Ψ1Σ(ϒ1+ΞΨ1Σ)1ΞΨ1E7

Proof. The validation of (7) must satisfy

  1. (Ψ+ΣϒΞ)(Ψ1Ψ1Σ(ϒ1+ΞΨ1Σ)1ΞΨ1)=IrE8

(Ψ1Ψ1Σ(ϒ1+ΞΨ1Σ)1ΞΨ1)(Ψ+ΣϒΞ)=Ir., where Ir represents the r×r identity matrix. Notice the existance of matricesΨ1, ϒ1, (Ψ+ΣϒΞ)1and(ϒ1+ΞΨ1Σ)1. Manipulating i) shows:

(Ψ+ΣϒΞ)(Ψ1Ψ1Σ(ϒ1+ΞΨ1Σ)1ΞΨ1)

=IrΣ(ϒ1+ΞΨ1Σ)1ΞΨ1+ΣϒΞΨ1ΣϒΞΨ1Σ(ϒ1+ΞΨ1Σ)1ΞΨ1

=Ir+ΣϒΞΨ1Σϒ(ϒ1+ΞΨ1Σ)(ϒ1+ΞΨ1Σ)1ΞΨ1

=Ir+ΣϒΞΨ1ΣϒΞΨ1=Ir.

Likewise for ii):

(Ψ1Ψ1Σ(ϒ1+ΞΨ1Σ)1ΞΨ1)(Ψ+ΣϒΞ)

=Ir+Ψ1ΣϒΞΨ1Σ(ϒ1+ΞΨ1Σ)1ΞΨ1Σ(ϒ1+ΞΨ1Σ)1ΞΨ1ΣϒΞ

=Ir+Ψ1ΣϒΞΨ1Σ(ϒ1+ΞΨ1Σ)1(ϒ1+ΞΨ1Σ)ϒΞ

=Ir+Ψ1ΣϒΞΨ1ΣϒΞ=Ir.

Now it is pertinent to demonstrate (6) with the aid of Lemma 1. It must be verified that both LL1 and L1L must be equal to the (n+m)×(n+m) identity block matrixI(n+m)=[In0n×m0m×nIm], with consistent-dimensional identity and zero sub-blocks:In,Im;0n×m, 0m×n, respectively. We start by calulating

LL1=[ABCD][(ABD1C)1(ABD1C)1BD1(DCA1B)1CA1(DCA1B)1]E9

and

L1L=[(ABD1C)1(ABD1C)1BD1(DCA1B)1CA1(DCA1B)1][ABCD]E10

by applying (7) in Lemma 1 to both matrices (ABD1C)1n×n and(DCA1B)1m×m, which are present in (8) and (9), and recalling full-rank conditions not only over those matrices but also for A andD, yields the relations

(ABD1C)1=A1+A1B(DCA1B)1CA1E11
(DCA1B)1=D1+D1C(ABD1C)1BD1E12

Using (10-11) in (8-9), the following results arise:

  1. for operations involved in sub-blocks ofLL1:

A(ABD1C)1B(DCA1B)1CA1

=A[A1+A1B(DCA1B)1CA1]B(DCA1B)1CA1

=In+B(DCA1B)1CA1B(DCA1B)1CA1=In

A(ABD1C)1BD1+B(DCA1B)1

=A[A1+A1B(DCA1B)1CA1]BD1+B(DCA1B)1

=BD1B(DCA1B)1CA1BD1+B(DCA1B)1

=BD1B(DCA1B)1(CA1B+D)D1=0n×m

C(ABD1C)1D(DCA1B)1CA1

=C(ABD1C)1D[D1+D1C(ABD1C)1BD1]CA1

=C(ABD1C)1CA1C(ABD1C)1BD1CA1

=C(ABD1C)1[ABD1C]A1CA1=0m×n;

C(ABD1C)1BD1+D(DCA1B)1

=C(ABD1C)1BD1+D[D1+D1C(ABD1C)1BD1]

=C(ABD1C)1BD1+Im+C(ABD1C)1BD1=Im;

thus,

LL1=I(n+m)E13
.

  1. for operations involved in sub-blocks ofL1L:

(ABD1C)1A(ABD1C)1BD1C

=(ABD1C)1[ABD1C]=In;

(ABD1C)1B(ABD1C)1BD1D=0n×m;

(DCA1B)1CA1A+(DCA1B)1C=0m×n;

(DCA1B)1CA1B+(DCA1B)1D

=(DCA1B)1[CA1B+D]=Im;

thus,L1L=I(n+m).

4.3. Generalized-Inverse

The concept of Generalized-Inverse is an extension of a matrix inversion operations applied to non-singular rectangular matrices [17-18]. For notation purposes and without loss of generalization, ρ(G)and GT denote the rank of a rectangular matrixGMm×n, and GT=GH is the transpose-conjugate of G (whenM=Gm×n) or GT=GT is the transpose of G (whenM=Gm×n), respectively.

Definition 2. Let GMm×n and0ρ(G)min(m,n). Then, there exists a matrix GMn×m (identified as the Generalized-Inverse), such that it satisfies several conditions for the following cases:

case i: if m>n and0ρ(G)min(m,n)ρ(G)=n, then there exists a unique matrix GG+Mn×m (identified as Left-Pseudoinverse: LPI) such thatG+G=In, satisfying: a)GG+G=G, and b)G+GG+=G+. Therefore, the LPI matrix is proposed asG+=(GTG)1GT.

case ii: if m=n anddet(G)0ρ(G)=n, then there exists a unique matrix GG1Mn×n (identified as Inverse) such thatG1G=GG1=In.

case iii: if m<n and0ρ(G)min(m,n)ρ(G)=m, then there exists a unique matrix GGMn×m (identified as Right-Pseudoinverse: RPI) such thatGG=Im, satisfying: a)GGG=G, and b)GGG=G. Therefore, the RPI matrix is proposed asG=GT(GGT)1. ■

Given the mathematical structure for G provided in Definition 2, it can be easily validated that: 1) For a LPI matrix stipulated in case i, GGG=Gand GGG=G withG=(GTG)1GT; 2) For a RPI matrix stipulated in case iii, GGG=Gand GGG=G withG=GT(GGT)1; iii) For the Inverse in case ii,G+=(GTG)1GT=GT(GGT)1=G. For a uniqueness test for all cases, assume the existance of matrices G1Mn×m and G2Mn×m such that G1G=In and G2G=In (for case i), and GG1=Im and GG2=Im (for case iii). Notice immediately, (G1G2)G=0n(for case i) and G(G1G2)=0m(for case iii), which obligates G1=G2 for both cases, because of full-rank properties overG. Clearly, case ii is a particular consequence of cases i and iii.

Advertisement

5. The MIMO channel matrix

The MIMO channel matrix is the mathematical representation for modeling the degradation phenomena presented in the RFC scenario presented in (2). The elements hij in HnR×nT represent a time-invariant transfer function (possesing spectral information about magnitude and phase profiles) between a j-th transmitter and an i-th receiver antenna. Once again, dynamical properties of physical phenomena

We suggest the reader consulting references [11-16] for a detail and clear explanation on these narrowband and wideband physical phenomena presented in wireless MIMO communication systems.

such as path-loss, shadowing, multipath, Doppler spreading, coherence time, absorption, reflection, scattering, diffraction, basestation-user motion, antenna’s physical properties-dimensions, information correlation, associated with a slow-flat quasi-static RFC scenario (proper of a non-LOS indoor wireless environments) are highlighted into a statistical model represented by matrixH. For H purposes, CSI is a necessary feature required at the reception part in (2), as well as the nRnT condition. Table 1 provides severalnR>nT MIMO channel matrix realizations for RFC-based environments [19-21]. On table 1: a)MIMO(nR,nT): refers to the MIMO communication link configuration, i.e. amount of receiver-end and transmitter-end elements; b)Hm: refers to a MIMO channel matrix realization; c)Hm+: refers to the corresponding LPI, computed asHm=(HmHHm)1HmH; d)h: blockwise matrix version forHm; e)h+: refers to the corresponding LPI, computed ash=(hTh)1hT. As an additional point of analysis, full-rank properties over H and h (and thus the existance of matricesH+,H1 ,h+ , andh1) are validated and corroborated through a MATLAB simulation-driven model regarding frequency-selective and time-invariant properties for several RFC-based scenarios at different MIMO configurations. Experimental data were generated upon 106 MIMO channel matrix realizations. As illustrated in figure 3, a common pattern is found regarding the statistical evolution for full-rank properties of H and h with nRnT at several typical MIMO configurations, for instance, MIMO(2,2),MIMO(4,2) , andMIMO(4,4). It is plotted therein REAL(H,h) against IMAG(H,h), where each axis label denote respectively the real and imaginary parts of: a) det(H)and det(h) whennR=nT, and b) det(HHH)and det(hTh) when. Blue crosses indicate the behavior of ρ(H) related to det(H) and det(HHH) (det(H) legend on top-left margin), while red crosses indicate the behavior of ρ(h) related to det(h) and det(hTh) (det(h) legend on top-left margin). The black-circled zone intersected with black-dotted lines locates the 0+j0 value. As depicted on figures (4)-(5), a closer glance at this statistical behavior reveals a prevalence on full-rank properties of Handh, meaning that non of the determinantsdet(H),det(h) ,det(HHH) and det(hTh) is equal to zero (behavior enclosed by the light-blue region and delimited by blue/red-dotted lines).

Figure 3.

MIMO channel matrix rank-determinant behavior for several realizations for H andh. This statistical evolution is a common pattern found for several MIMO configurations involving slow-flat quasi-static RFC-based environments withnRnT.

Table 1.

MIMO channel matrix realizations for several MIMO communication link configurations at slow-flat quasi-static RFC scenarios.

Figure 4.

MIMO channel matrix rank-determinant behavior for several realizations forH. Full-rank properties for H and HHH preveal for RFC-based environments (light-blue region delimited by blue-dotted lines).

Figure 5.

MIMO channel matrix rank-determinant behavior for several realizations forh. Full-rank properties for hand hTh preveal for RFC-based environments (light-blue region delimited by red-dotted line).

Advertisement

6. Proposed algorithm

The proposal for a novel algorithm for computing a LPI matrix h+2nT×2nR (withnRnT) is based on the block-matrix structure of h as exhibited in (4). This idea is an extension of the approach presented in [22]. The existence for this Generalized-Inverse matrix is supported on the statistical properties of the slow-flat quasi-static RFC scenario which impact directly on the singularity of H at every MIMO channel matrix realization. Keeping in mind that other approaches attempting to solve the block-matrix inversion problem [7-10] requires several constraints and conditions, the subsequent proposal does not require any restriction at all mainly due to the aforementioned properties ofH. From (4), it is suggested that [xrxi] is somehow related to[{H+}{H+}{H+}{H+}]Y; hence, calculating h+will lead to this solution. Let A=Hr andB=Hi. It is kwon a priori thatρ(A+jB)=nT. Then h=[ABBA] withρ(h)=2nT=Nt. Define the matrix Ω˜ asΩ˜hThNt×Nt, where Ω˜=[MLLM] withM=ATA+BTBnT×nT, L=ATB(ATB)TnT×nT, and ρ(Ω˜)=Nt as a direct consequence from2nR2nTNrNt. It can be seen that

h+=Ω˜1hTNt×NrE15

For simplicity, matrix operations involved in (12) require classic multiply-and-accumulate operations between row-entries of Ω˜1Nt×Ntand column-entries ofhTNt×Nr. Notice immediately that the critical and essential task of computing h+ relies on finding the block matrix inverse Ω˜1

Notice that . Moreover, , where and .

. The strategy to be followed in order to solve Ω˜1 in (12) will consist of the following steps: 1) the proposition of partitioning Ω˜ without any restriction on rank-defficiency over inner matrix sub-blocks; 2) the definition of iterative multiply-and-accumulate operations within sub-blocks comprised inΩ˜; 3) the recursive definition for compacting the overall blockwise matrix inversion. Keep in mind that matrix Ω˜ can be also viewed asΩ˜=[ω˜1,1ω˜1,Ntω˜Nt,1ω˜Nt,Nt]. The symmetry presented in Ω˜=[MLLM] will motivate the development for the pertinent LPI-based algorithm. From (12) and by the use of Lemma 1 it can be concluded thatΩ˜1=[QPPQ], whereQ=(M+LM1L)1nT×nT,P=QXnT×nT , andX=LM1nT×nT. Interesting enough, full-rank is identified at each matrix sub-block in the main diagonal of Ω˜ (besidesρ(Q)=nT). This structural behavior serves as the leitmotiv for the construction of an algorithm for computing the blockwise inverseΩ˜1. Basically speaking and concerning step 1) of this strategy, the matrix partition procedure obeys the assignments (13-16) defined as:

Wk=[ω˜Nt(2k+1),Nt(2k+1)ω˜Nt(2k+1),Nt2kω˜Nt2k,Nt(2k+1)ω˜Nt2k,Nt2k]2×2E16
Xk=[ω˜Nt(2k+1),Nt(2k1)ω˜Nt(2k+1),Ntω˜Nt2k,Nt(2k1)ω˜Nt2k,Nt]2×2kE17
Yk=[ω˜Nt(2k1),Nt(2k+1)ω˜Nt(2k1),Nt2kω˜Nt,Nt(2k+1)ω˜Nt,Nt2k]2k×2E18
Z0=[ω˜Nt1,Nt1ω˜NT1,Ntω˜Nt,Nt1ω˜Nt,Nt]2×2E19

The matrix partition over Ω˜ obeys the indexk=1:1:(Nt/2 1). Because of the even-rectangular dimensions ofΩ˜, matirx Ω˜ owns exactly an amount ofNt/2=nT sub-block matrices of 2×2 dimension along its main diagonal. Interesting enough, due to RFC-based environment characteristics studied in (1) and (4), it is found that:

ρ(Wk)=ρ(Z0)=2E20

After performing these structural characteristics forΩ˜, and with the use of (13-16), step 2) of the strategy consists of the following iterative operations also indexed byk=1:1:(Nt/2 1), in the sense of performing:

ϕk=WkXkZk11YkE21
αk=ϕk1XkZk11E22
θk=Zk11+Zk11YkαkE23

Here:Zk112k×2k, ϕk2×2, αk2×2k, andθk2k×2k. Steps stated in (18-20) help to construct intermediate sub-blocks as

Ω˜k2(k+1)×2(k+1)=[Wk2×2Xk2×2kYk2k×2Zk12k×2k]Ω˜k12(k+1)×2(k+1)=[ϕk12×2αk2×2kθkYkWk12k×2θk2k×2k]E24

The dimensions of each real-valued sub-block in (21) are indicated consistently

Matrix structure given in (21) is directly derived from applying Equation (6), and by the use of Lemma 1 as . See that this expansion is preferable instead of , which is undesirable due to an unnecessary matrix operation overhead related to computing , e.g. inverting , which comes preferably from the recursion.

. For step 3) of the strategy, a recursion step Zk1(Zk11) is provided in terms of the assignmentZk1=Ω˜k12(k+1)×2(k+1). Clearly, only inversions ofWk, Z0, and ϕk (which are 2×2 matrices, yielding correspondinglyWk1, Z01, andϕk1) are required to be performed throughout this iterative-recursive process, unlike the operation linked toZk11, which comes from a previous updating step associated with the recursion belonging toZk1. Although ρ(Ω˜)=Nt assures the existance ofΩ˜1, full-rank requirements outlined in (17) and non-zero determinants for (18) are strongly needed for this iterative-recursive algorithm to work accordingly. Also, full-rank is expected for every recursive outcome related toZk1(Zk11). Again, thank to the characteristics of the slow-flat quasi-static RFC-based environment in which these operations are involved among every MIMO channel matrix realization, conditions in (17) and full-rank of (18) are always satisfied. These issues are corroborated with the aid of the same MATLAB-based simulation framework used to validate full-rank properties over H andh. The statistical evolution for the determinants forWk, Z0, andϕk, and the behavior of singularity within the Zk1(Zk11) recursion are respectively illustrated in figures (6)-(8).MIMO(2,2),MIMO(4,2) , and MIMO(4,4) were the MIMO communication link configurations considered for these tests. These simulation-driven outcomes provide supportive evidence for the proper functionality of the proposed iterative-recursive algorithm for computing Ω˜1 involving matrix sub-block inversions. On each figure, the statistical evolution for the determinants associated withZ0,Wk ,ϕk , and Zk1(Zk11) are respectively indicated by labels det(Zo), det(Wk), det(Fik), and det(iZk,iZkm1), while the light-blue zone at bottom delimited by a red-dotted line exhibits the gap which marks the avoidance in rank-deficincy over the involved matrices. The zero-determinant value is marked with a black circle.

The next point of analysis for the behavior of the h+ LPI-based iterative-recursive algorithm is complexity, which in essence will consist of a demand in matrix partitions (amount of matrix sub-blocks: PART) and arithmetic operations (amount of additions-subtractions: ADD-SUB; multiplications: MULT; and divisions: DIV). Let PART-mtx and ARITH-ops be the nomenclature for complexity cost related to matrix partitions and arithmetic operations, respectively. Without loss of generalization, define C[] as the complexity in terms of the costs PART-mtx and ARITH-ops belonging to operations involved in. Henceforth, C[h+]=C[Ω˜1]+C[Ω˜1·hT]denotes the cost of computing h+ as the sum of the costs of inverting Ω˜ and multiplying Ω˜1 byhT. It is evident that: a) C[Ω˜1·hT]implies PART=0 and ARITH-ops itemized into MULT=8nRnT2, ADD-SUB=4nRnT(2nT1), and DIV=0; b)C[Ω˜1]=C[hT·h]+C[(hTh)-1]. Clearly, C[hT·h]demands no partitions at all, but with a ARITH-ops cost of MULT=8nRnT2, and ADD-SUB=4(2nR1)nT2. However, the principal complexity relies critically onC[(hTh)-1], which is the backbone forh+, as presented in [22]. Table 2 summerizes these complexity results. For this treatment, C[(hTh)-1]consists of 3nT2 partitions, MULT =k=1nT1CkI+6, ADD-SUB =k=1nT1CkII+1, and DIV =k=1nT1CkIII+1. The ARITH-ops cost depends onCkI, CkII, andCkIII; the constant factors for each one of these items are proper of the complexity presented inC[Z01]. The remain of the complexities, i.e.CkI, CkII, andCkIII, are calculated according to the iterative stpes defined in (18-20) and (21), particularly expressed in terms of

C[ϕk1]+C[αk]+C[θkYkWk1]+C[θk]E25
(22)

It can be checked out that: a) no PART-mtx cost is required; b) the ARITH-ops cost employs (22) for each item, yielding: CkI=40k2+24k+12(for MULT), CkII=40k2+2(for ADD_SUB), and CkIII=2(for DIV).

An illustrative application example is given next. It considers a MIMO channel matrix realization obeying statistical behavior according to (1) and a MIMO(4,4) configuration:

H=[0.3059+j0.75430.8107+j0.20820.2314j0.48920.416j1.01891.1777+j0.04190.8421j0.94480.1235+j0.60671.5437+j0.40390.0886j0.06760.8409+j0.50510.132+j0.88670.0964j0.28280.2034j0.58860.0266+j1.1480.5132j1.12690.0806+j0.4879]4×4withρ(H)=4. As a consequence, Ω˜=[2.45161.26710.13622.702801.94480.60220.20021.26714.58321.72921.37761.944801.2292.41680.13621.72923.01320.09130.60221.22900.8622.70281.37760.09134.09130.20022.41680.862001.94480.60220.20022.45161.26710.13622.70281.944801.2292.41681.26714.58321.72921.37760.60221.22900.8620.13621.72923.01320.09130.20022.41680.86202.70281.37760.09134.0913]8×8 with

ρ(Ω˜)=8E26
.

Figure 6.

Statistical evolution of the rank-determinant behaviour concerningZ0,Wk ,ϕk , and Zk1(Zk11) for a MIMO(2,2) configuration.

Figure 7.

Statistical evolution of the rank-determinant behaviour concerningZ0,Wk ,ϕk , and Zk1(Zk11) for a MIMO(4,2) configuration.

Figure 8.

Statistical evolution of the rank-determinant behaviour concerningZ0,Wk ,ϕk , and Zk1(Zk11) for a MIMO(4,4) configuration.

Table 2.

Complexity cost results of the LPI-based iterative-recursive algorithm forh+.

Applying partition criteria (13-16) and givenk=1:1:3, the following matrix sub-blocks are generated:

W1=[2.45161.26711.26714.5832],

X1=[0.13622.70281.72921.3776],Y1=[0.13621.72922.70281.3776],Z0=[3.01320.09130.09134.0913],

W2=[3.01320.09130.09134.0913]

X2=[0.60221.229000.8620.20022.41680.8620],Y2=[0.60220.20021.2292.416800.8620.8620],

W3=[2.45161.26711.26714.5832],X3=[0.13622.702801.94480.60220.20021.72921.37761.944801.2292.4168],

andY3=[0.13621.72922.70281.377601.94481.944800.60221.2290.20022.4168]. Suggested by (18-20), iterative operations (23-25) are computed as:

ϕ1=W1X1Z01Y1,α1=ϕ11X1Z01,θ1=Z01+Z01Y1α1E27
ϕ2=W2X2Z11Y2,α2=ϕ21X2Z11,θ2=Z11+Z11Y2α2E28
ϕ3=W3X3Z21Y3,α3=ϕ31X3Z21,θ3=Z21+Z21Y3α3E29

From (21), the matrix assignments related to recursion Zk1(Zk11) produces the following intermediate blockwise matrix results:

Z11(Z01)=Ω˜11=[ϕ11α1θ1Y1W11θ1]=[1.57650.12350.03071.00050.12350.33320.18670.03480.03070.18670.44320.0931.00050.03480.0930.9191],Z21(Z11)=Ω˜21=[ϕ21α2θ2Y2W21θ2]

=[0.40980.08790.08290.18390.07430.07750.08790.43550.28470.31820.04220.09850.08290.28471.76420.33930.00121.06860.18390.31820.33930.60230.23760.05480.07430.04220.00120.23760.45830.07380.07750.09851.06860.05480.07380.9499],Z31(Z21)=Ω˜1=[ϕ31α3θ3Y3W31θ3]

=[1.97980.38080.11141.022400.36050.25240.21830.38080.67590.26190.08560.360500.23680.11930.11140.26190.54930.02180.25240.236800.05351.022240.08560.02180.98390.21830.11930.0535000.36050.25240.21831.97980.38080.11141.02240.360500.23680.11930.38080.67590.26190.08560.25240.236800.05350.11140.26190.54930.02180.21830.11930.053500.11140.08560.02180.9839]. This last recursive outcome from Zk1(Zk11) corresponds toΩ˜1, and is further used for calculatingh+=Ω˜1hT8×8. Moreover, notice that full-rank properties are always presented in matricesZ0,W1 ,W2 ,W3 ,ϕ1 ,ϕ2 ,ϕ3 ,Z11 ,Z21 , andZ31.

Advertisement

7. VLSI implementation aspects

The arithmetic operations presented in the algorithm for computing h+ can be implemented under a modular-iterative fashion towards a VLSI (Very Large Scale of Integration) design. The partition strategy comprised in (13-16) provides modularity, while (18-20) is naturally associated with iterativeness; recursion is just used for constructing matrix-blocks in (21). Several well-studied aspects aid to implement a further VLSI architecture [23-27] given the nature of the mathematical structure of the algorithm. For instance, systolic arrays [25-27] are a suitable choice for efficient, parallel-processing architectures concerning matrix multiplications-additions. Bidimensional processing arrays are typical architectural outcomes, whose design consist basically in interconnecting processing elements (PE) among different array layers. The configuration of each PE comes from projection or linear mapping techniques [25-27] derived from multiplications and additions presented in (18-20). Also, systolic arrays tend to concurrently perform arithmetic operations dealing with the matrix concatenated multiplicationsXkZk11Yk,ϕk1XkZk11 ,Zk11Ykαk , and θkYkWk1 presented in (18-20). Consecutive additions inside every PE can be favourably implemented via Carry-Save-Adder (CSA) architectures [23-24], while multiplications may recur to Booth multipliers [23-24] in order to reduce latencies caused by adding acummulated partial products. Divisions presented inWk1, Z01, and ϕk1 can be built through regular shift-and-subtract modules or classic serial-parallel subtractors [23-24]; in fact, CORDIC (Coordinate Rotate Digital Computer) processors [23] are also employed and configured in order to solve numerical divisions. The aforementioned architectural aspects offer an attractive and alternative framework for consolidating an ultimate VLSI design for implementing the h+algorithm without compromising the overall system data throughput (intrinsicly related to operation frequencies) for it.

Advertisement

8. Conclusions

This chapter presented the development of a novel iterative-recursive algorithm for computing a Left-Pseudoinverse (LPI) as a Generalized-Inverse for a MIMO channel matrix within a Rayleigh fading channel (RFC). The formulation of this algorithm consisted in the following step: i) first, structural properties for the MIMO channel matrix acquired permanent full-rank due to statistical properties of the RFC scenario; ii) second, Partition-Matrix Theory was applied allowing the generation of a block-matrix version of the MIMO channel matrix; iii) third, iterative addition-multiplication operations were applied at these matrix sub-blocks in order to construct blockwise sub-matrix inverses, and recursively reusing them for obtaining the LPI. For accomplishing this purpose, required mathematical background and MIMO systems concepts were provided for consolidating a solid scientific framework to understand the context of the problem this algorithm was attempting to solve. Proper functionality for this approach was validated through simulation-driven experiments, as well as providing an example of this operation. As an additional remark, some VLSI aspects and architectures were outlined for basically implementing arithmetic operations within the proposed LPI-based algorithm.

Advertisement

Acknowledgement

This work was supported by CONACYT (National Council of Science and Technology) under the supervision, revision, and sponsorship of ITESM University (Instituto Tecnológico y de Estudios Superiores de Monterrey).

References

  1. 1. Abramovich YI, Johnson BA, and Spencer NK2008Two-Dimensional Multivariate Parametric Models for Radar Applications-Part I: Maximum-Entropy Extensions for Toeplitz-Block Matrices. IEEE Transactions on Signal Processing, 5611November 2008: 5509-5526.
  2. 2. Bera TK, et al2011Improving the image reconstruction in Electrical Impedance Tomography (EIT) with block matrix-based Multiple Regularization (BMMR): A practical phantom study. World Congress on Information and Communication Technologies (WICT). 201113461351
  3. 3. KailathT.1980Linear Systems. Prentice-Hall. 682 p.
  4. 4. Spong MW1998Underactuated Mechanical Systems. Control Problems in Robotics and Automation, Lecture Notes in Control and Information Sciences, 230Springer-Verlag: 135150
  5. 5. UtkinV.GuldnerJ.ShiJ. X.1992Sliding Mode Control in Electro-Mechanical Systems. CRC Press. April 1999: 338 p.
  6. 6. Juang J-N1993Applied System Identification. Prentice Hall. 400 p.
  7. 7. Watt SM2006Pivot-Free Block Matrix Inversion. Proceedings of the Eighth International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), IEEE Computer Society: 5 p.
  8. 8. TianY.TanakeY.2009The inverse of any two-by-two nonsingular partitioned matrix and three matrix inverse completion problems. Journal Computers & Mathematics with Applications, 578April 2009: 12 p.
  9. 9. ChoiY.2009New Form of Block Matrix Inversion. International Conference on Advanced Intelligent Mechatronics. July 200919521957
  10. 10. ChoiY.CheongJ.2009New Expressions of 2X2 Block Matrix Inversion and Their Application. IEEE Transactions on Automatic Control, 5411November 2009: 2648-2653.
  11. 11. Fontán FP, and Espiñera PM2008Modeling the Wireless Propagation Channel. Wiley. 268 p.
  12. 12. El -HajjarM.HanzoL.2010Multifunctional MIMO Systems: A Combined Diversity and Multiplexing Design Perspective. IEEE Wireless Communications. April 20107379
  13. 13. BiglieriE.et al.2007MIMO Wireless Communications. Cambridge University Press: United Kingdom. 344 p.
  14. 14. JankiramanM.2004Space-Time Codes and MIMO Systems. Artech House: United States. 327 p.
  15. 15. BiglieriE.ProakisJ.ShamaiS.1998Fading Channels: Information-Theoretic and Communications Aspects. IEEE Transactions on Information Theory, 446October 1998: 2619-2692.
  16. 16. AlmersP.BonekE.BurrA.et al.2007Survey of Channel and Radio Propagation Models for Wireless MIMO Systems. EURASIP Journal on Wireless Communications and Networking, 20111January 2007: 19 p.
  17. 17. Golub GH, and Van Loan CF1996Matrix Computations. The Johns Hopkins University Press. 694 p.
  18. 18. SerreD.2001Matrices: Theory and Applications. Springer Verlag. 202 p.
  19. 19. R&S®. Rohde & Schwarz GmbH & Co. KG. WLAN 802.11n: From SISO to MIMO. Application Note: 1MA179_9E. Available: www.rohde-schwarz.com:p.
  20. 20. Agilent©.TechnologiesInc.2008Agilent MIMO Wireless LAN PHY Layer [RF] : Operation & Measurement: Application Note: 1509. Available: www.agilent.com:p.
  21. 21. PaulT.OgunfunmiT.2008Wireless LAN Comes of Age : Understanding the IEEE 802.11n Amendment. IEEE Circuits and Systems Magazine. First Quarter 20082854
  22. 22. CervantesP.GonzálezV. M.MejíaP. A.2009Left-Pseudoinverse MIMO Channel Matrix Computation. 19th International Conference on Electronics, Communications, and Computers (CONIELECOMP 2009). July 2009134138
  23. 23. MilosE.TomasL.2004Digital Arithmetic. Morgan Kauffmann Publishers. 709 p.
  24. 24. Parhi KK1999VLSI Digital Signal Processing Systems: Design and Implementation. John Wiley & Sons. 784 p.
  25. 25. Song SW1994Systolic Algorithms: Concepts, Synthesis, and Evolution. Institute of Mathematics, University of Sao Paulo, Brazil. Available: http://www.ime.usp.br/~song/papers/cimpa.pdf. DOI10p.
  26. 26. Kung SY1985VLSI Array Processors. IEEE ASSP Magazine. July 1985422
  27. 27. JagadishH. V.RaoS. K.KailathT.1987Array Architectures for Iterative Algorithms. Proceedings of the IEEE, 759September 1987: 1304-1321.

Notes

  • In the context of MIMO systems, this matrix operation is commonly found in Babai estimators for symbol-decoding purposes at the Rx part [12,13]. For the reader’s interest, refer to [11-16] for other MIMO demodulation techniques.
  • Notice that and .
  • Refer to [3,7-10,17,18] to review lemmata exposed for these issues and related results.
  • We suggest the reader consulting references [11-16] for a detail and clear explanation on these narrowband and wideband physical phenomena presented in wireless MIMO communication systems.
  • Notice that . Moreover, , where and .
  • Matrix structure given in (21) is directly derived from applying Equation (6), and by the use of Lemma 1 as . See that this expansion is preferable instead of , which is undesirable due to an unnecessary matrix operation overhead related to computing , e.g. inverting , which comes preferably from the recursion.

Written By

P. Cervantes, L.F. González, F.J. Ortiz and A.D. García

Submitted: November 11th, 2011 Published: July 11th, 2012