MIMO channel matrix realizations for several MIMO communication link configurations at slow-flat quasi-static RFC scenarios.
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 , Jacobian response matrices are partitioned into several block-matrix instances in order to enhance medical images for Electrical-Impedance-Tomography , 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 . 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 . At sliding-mode control structures, a Right-Pseudoinverse is incorporated into a state-feedback control law in order to stabilize electromechanical non-linear systems . 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 . 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 , 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,  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;  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 transmitter-end and 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.
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 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 ), and the mathematical model that suits the aforementioned MIMO communication link characteristics will be represented by
where: is a complex-valued dimensional transmitted vector with entries drawn from a Gaussian-integer finite-lattice constellation (digital modulators, such as: q-QAM, QPSK); is a complex-valued dimensional received vector; is a dimensional independent-identically-distributed (idd) complex-circularly-symmetric (ccs) Additive White Gaussian Noise (AWGN) vector; and is the 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
Notice from (1-2) that an important requisite for CE purposes within RFC scenarios is that is 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 from 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 findfrom degradated informationthrough calculating an inversion over. Moreover, is commonly assumed for MIMO demodulation tasks [13-14] because it guarantees linear independency between row-entries of matrix in (2), yielding a nonhomogeneous overdetermined system of linear equations.
3. Problem definition
Recall for the moment the mathematical model provided in (1). Consider and to be the real and imaginary parts of a complex-valued matrix (vector), that is,. Then, Equation (1) can be expanded as follows:
where, , , and CSI is still needed for MIMO demodulation purposes involving (4). Moreover, if and, then. Obviously, while seeking for a solution of signal vector from (4), the reception part Rx will provide also the solution for signal vector, and thus MIMO demodulation tasks will be fulfilled. This problem can be defined formally into the following manner:
Definition 1. Given parameters and, and a block-matrix, there exists an operator which solves the matrix-block equation so that. ■
From Definition 1, the following affirmations hold: i) CSI over is a necessary condition as an input argument for the operator; and ii) can be naïvely defined as a Generalized-Inverse of the block-matrix. In simpler terms, - is associated with and stands for the Generalized-Inverse of the block-matrix, where [17-18]. Clearly, and represent the inverse and transpose matrix operations over real-valued matrices. As a concluding remark, computing the Generalized-Inverse can be separated into two operations: 1) a block-matrix inversion -; 2) a typical matrix multiplication. 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 with dimension can be constructed (or partitioned) consistently according to matrix sub-blocks, , , and of,, , and dimensions, respectively, yielding
An interesting operation to be performed for these structures given in (5) is the inversion, i.e. a blockwise inversion. For instance, let be a full-rank real-valued block matrix (the subsequent treatment is also valid for complex-valued entities, i.e.). An alternative partition can be performed with, , , and. Assume also and to be full-rank matrices. Then,
This strategy (to be proved in the next part) requires additonally and mandatorily full-rank over matrices and. The simple case is defined for (indistinctly for or). Once again, assuming, , and (related to full-rank restictions within block-matrix):
where evidently,, and.
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 -. Lemma 1 states this result.
Lemma 1. Let,,, and be real-valued or complex-valued matrices. Assume these matrices to be non-singular:,,, and. Then,
Proof. The validation of (7) must satisfy
., where represents the identity matrix. Notice the existance of matrices, , and. Manipulating i) shows:
Likewise for ii):
Now it is pertinent to demonstrate (6) with the aid of Lemma 1. It must be verified that both and must be equal to the identity block matrix, with consistent-dimensional identity and zero sub-blocks:,;, , respectively. We start by calulating
for operations involved in sub-blocks of:
for operations involved in sub-blocks of:
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, and denote the rank of a rectangular matrix, and is the transpose-conjugate of (when) or is the transpose of (when), respectively.
Definition 2. Let and. Then, there exists a matrix (identified as the Generalized-Inverse), such that it satisfies several conditions for the following cases:
case i: if and, then there exists a unique matrix (identified as Left-Pseudoinverse: LPI) such that, satisfying: a), and b). Therefore, the LPI matrix is proposed as.
case ii: if and, then there exists a unique matrix (identified as Inverse) such that.
Given the mathematical structure for provided in Definition 2, it can be easily validated that: 1) For a LPI matrix stipulated in case i, and with; 2) For a RPI matrix stipulated in case iii, and with; iii) For the Inverse in case ii,. For a uniqueness test for all cases, assume the existance of matrices and such that and (for case i), and and (for case iii). Notice immediately, (for case i) and (for case iii), which obligates for both cases, because of full-rank properties over. 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 in 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  - 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 matrix. For purposes, CSI is a necessary feature required at the reception part in (2), as well as the condition. Table 1 provides severalMIMO channel matrix realizations for RFC-based environments [19-21]. On table 1: a): refers to the MIMO communication link configuration, i.e. amount of receiver-end and transmitter-end elements; b): refers to a MIMO channel matrix realization; c): refers to the corresponding LPI, computed as; d): blockwise matrix version for; e): refers to the corresponding LPI, computed as. As an additional point of analysis, full-rank properties over and (and thus the existance of matrices,,, and) 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 MIMO channel matrix realizations. As illustrated in figure 3, a common pattern is found regarding the statistical evolution for full-rank properties of and with at several typical MIMO configurations, for instance, ,, and. It is plotted therein REAL(H,h) against IMAG(H,h), where each axis label denote respectively the real and imaginary parts of: a) and when, and b) and when. Blue crosses indicate the behavior of related to and (det(H) legend on top-left margin), while red crosses indicate the behavior of related to and (det(h) legend on top-left margin). The black-circled zone intersected with black-dotted lines locates the value. As depicted on figures (4)-(5), a closer glance at this statistical behavior reveals a prevalence on full-rank properties of and, meaning that non of the determinants,,and is equal to zero (behavior enclosed by the light-blue region and delimited by blue/red-dotted lines).
6. Proposed algorithm
The proposal for a novel algorithm for computing a LPI matrix (with) is based on the block-matrix structure of as exhibited in (4). This idea is an extension of the approach presented in . 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 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 of. From (4), it is suggested that is somehow related to; hence, calculating will lead to this solution. Let and. It is kwon a priori that. Then with. Define the matrix as, where with, , and as a direct consequence from. It can be seen that
For simplicity, matrix operations involved in (12) require classic multiply-and-accumulate operations between row-entries of and column-entries of. Notice immediately that the critical and essential task of computing relies on finding the block matrix inverse  -. The strategy to be followed in order to solve 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. The symmetry presented in will motivate the development for the pertinent LPI-based algorithm. From (12) and by the use of Lemma 1 it can be concluded that, where,, and. Interesting enough, full-rank is identified at each matrix sub-block in the main diagonal of (besides). This structural behavior serves as the leitmotiv for the construction of an algorithm for computing the blockwise inverse. Basically speaking and concerning step 1) of this strategy, the matrix partition procedure obeys the assignments (13-16) defined as:
The matrix partition over obeys the index. Because of the even-rectangular dimensions of, matirx owns exactly an amount ofsub-block matrices of dimension along its main diagonal. Interesting enough, due to RFC-based environment characteristics studied in (1) and (4), it is found that:
The dimensions of each real-valued sub-block in (21) are indicated consistently -. For step 3) of the strategy, a recursion step is provided in terms of the assignment. Clearly, only inversions of, , and (which are matrices, yielding correspondingly, , and) are required to be performed throughout this iterative-recursive process, unlike the operation linked to, which comes from a previous updating step associated with the recursion belonging to. Although assures the existance of, 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 to. 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 and. The statistical evolution for the determinants for, , and, and the behavior of singularity within the recursion are respectively illustrated in figures (6)-(8).,, and 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 involving matrix sub-block inversions. On each figure, the statistical evolution for the determinants associated with,,, and 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 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 as the complexity in terms of the costs PART-mtx and ARITH-ops belonging to operations involved in. Henceforth, denotes the cost of computing as the sum of the costs of inverting and multiplying by. It is evident that: a) implies PART=0 and ARITH-ops itemized into MULT=, ADD-SUB=, and DIV=0; b). Clearly, demands no partitions at all, but with a ARITH-ops cost of MULT=, and ADD-SUB=. However, the principal complexity relies critically on, which is the backbone for, as presented in . Table 2 summerizes these complexity results. For this treatment, consists of partitions, MULT =, ADD-SUB =, and DIV =. The ARITH-ops cost depends on, , and; the constant factors for each one of these items are proper of the complexity presented in. The remain of the complexities, i.e., , and, are calculated according to the iterative stpes defined in (18-20) and (21), particularly expressed in terms of
It can be checked out that: a) no PART-mtx cost is required; b) the ARITH-ops cost employs (22) for each item, yielding: (for MULT), (for ADD_SUB), and (for DIV).
An illustrative application example is given next. It considers a MIMO channel matrix realization obeying statistical behavior according to (1) and a configuration:
with. As a consequence, with
From (21), the matrix assignments related to recursion produces the following intermediate blockwise matrix results:
. This last recursive outcome from corresponds to, and is further used for calculating. Moreover, notice that full-rank properties are always presented in matrices,,,,,,,,, and.
7. VLSI implementation aspects
The arithmetic operations presented in the algorithm for computing 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 multiplications,,, and 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 in, , and can be built through regular shift-and-subtract modules or classic serial-parallel subtractors [23-24]; in fact, CORDIC (Coordinate Rotate Digital Computer) processors  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 algorithm without compromising the overall system data throughput (intrinsicly related to operation frequencies) for it.
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.
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).
- 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.