Open access peer-reviewed chapter

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

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

Submitted: November 11th 2011Reviewed: April 21st 2012Published: July 11th 2012

DOI: 10.5772/48198

Downloaded: 2304

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.

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 nTtransmitter-end and nRreceiver-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 nTelements 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 xfrom yregarding 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 Hin (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.

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=2nRandNt=2nT, thenNrNt. Obviously, while seeking for a solution of signal vector Xfrom (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×1which solves the matrix-block equation Y=hX+Nso 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[1] - is associated with Γ[Y,h]and hNt×Nrstands for the Generalized-Inverse of the block-matrixh, where h=(hTh)1hT[17-18]. Clearly, []1and []Trepresent the inverse and transpose matrix operations over real-valued matrices. As a concluding remark, computing the Generalized-Inverse hcan be separated into two operations: 1) a block-matrix inversion(hTh)1[1] -; 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).

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 Lwith (n+q)×(m+p)dimension can be constructed (or partitioned) consistently according to matrix sub-blocksA, B, C, and Dofn×m,n×p, q×m, and q×pdimensions, 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 Aand Dto 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 ABD1CandDCA1B. The simple case is defined for L=[abcd](indistinctly for 2×2or2×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[1] -. Lemma 1 states this result.

Lemma 1. LetΨr×r,Σr×s,ϒs×s, and Ξs×rbe 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 Irrepresents the r×ridentity 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 LL1and L1Lmust 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×nand(DCA1B)1m×m, which are present in (8) and (9), and recalling full-rank conditions not only over those matrices but also for AandD, 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 GTdenote the rank of a rectangular matrixGMm×n, and GT=GHis the transpose-conjugate of G(whenM=Gm×n) or GT=GTis the transpose of G(whenM=Gm×n), respectively.

Definition 2. Let GMm×nand0ρ(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>nand0ρ(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=nanddet(G)0ρ(G)=n, then there exists a unique matrix GG1Mn×n(identified as Inverse) such thatG1G=GG1=In.

case iii: if m<nand0ρ(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 Gprovided in Definition 2, it can be easily validated that: 1) For a LPI matrix stipulated in case i, GGG=Gand GGG=GwithG=(GTG)1GT; 2) For a RPI matrix stipulated in case iii, GGG=Gand GGG=GwithG=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×mand G2Mn×msuch that G1G=Inand G2G=In(for case i), and GG1=Imand GG2=Im(for case iii). Notice immediately, (G1G2)G=0n(for case i) and G(G1G2)=0m(for case iii), which obligates G1=G2for both cases, because of full-rank properties overG. Clearly, case ii is a particular consequence of cases i and iii.

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 hijin HnR×nTrepresent 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 [1] - 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 Hpurposes, CSI is a necessary feature required at the reception part in (2), as well as the nRnTcondition. Table 1 provides severalnR>nTMIMO 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 Hand 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 106MIMO channel matrix realizations. As illustrated in figure 3, a common pattern is found regarding the statistical evolution for full-rank properties of Hand hwith nRnTat 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+j0value. 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 withnR≥nT.

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).

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 has 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 Hat 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=HrandB=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 ρ(Ω˜)=Ntas 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[1] -. The strategy to be followed in order to solve Ω˜1in (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=nTsub-block matrices of 2×2dimension 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[1] -. 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×2matrices, 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 ρ(Ω˜)=Ntassures 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 Handh. 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 Ω˜1involving 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 Ω˜1byhT. 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 3nT2partitions, 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×8with

ρ(Ω˜)=8E26
.

Figure 6.

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

Figure 7.

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

Figure 8.

Statistical evolution of the rank-determinant behaviour concerningZ0,Wk ,ϕk , and Zk−1(Zk−1−1) 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.

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 θkYkWk1presented 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 ϕk1can 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.

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.

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).

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.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

P. Cervantes, L.F. González, F.J. Ortiz and A.D. García (July 11th 2012). Partition-Matrix Theory Applied to the Computation of Generalized-Inverses for MIMO Systems in Rayleigh Fading Channels, Linear Algebra - Theorems and Applications, Hassan Abid Yasser, IntechOpen, DOI: 10.5772/48198. Available from:

Embed this chapter on your site Copy to clipboard

<iframe src="http://www.intechopen.com/embed/linear-algebra-theorems-and-applications/partition-matrix-theory-applied-to-the-computation-of-generalized-inverses-for-mimo-systems-in-rayle" />

Embed this code snippet in the HTML of your website to show this chapter

chapter statistics

2304total chapter downloads

1Crossref citations

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Operator Means and Applications

By Pattrawut Chansangiam

Related Book

First chapter

Cramer’s Rules for the System of Two-Sided Matrix Equations and of Its Special Cases

By Ivan I. Kyrchei

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More about us