# Double-Layer Low-Density Parity-Check Codes over Multiple-Input Multiple-Output Channels

Authors: Yun Mao; Ying Guo; Jun Peng; Xueqin Jiang; Moon Ho Lee
Journal: International Journal of Antennas and Propagation
 (2012)

---

## Abstract

We introduce a double-layer code based on the combination of a low-density parity-check (LDPC) code with the multiple-input multiple-output (MIMO) system, where the decoding can be done in both inner-iteration and outer-iteration manners. The present code, called low-density MIMO code (LDMC), has a double-layer structure, that is, one layer defines subcodes that are embedded in each transmission vector and another glues these subcodes together. It supports inner iterations inside the LDPC decoder and outeriterations between detectors and decoders, simultaneously. It can also achieve the desired design rates due to the full rank of the deployed parity-check matrix. Simulations show that the LDMC performs favorably over the MIMO systems.


---

## Body

## 1. Introduction

Multiple-input multiple-output (MIMO) transmission has been identified as one of the most practical methods to combat fading and to increase the capacity of wireless channels in the recent years [1–3]. In order to ensure a desired quality of transmission, an outer error correction code can be employed additionally to decrease the occurring errors in imperfect channels. In this case, an appropriate low-density parity-check (LDPC) code [4–7] may be elegantly used for MIMO channels. Actually, the decoding of LDPC codes over MIMO channels can be well dealt with an iterative manner, where probabilistic information should be exchanged iteratively between MIMO detector and LDPC decoder. At the receiver, the detector has to calculate the maximum posteriori probability for each bit. One possible realization of this calculation is called sphere decoder [8]. Much effort has been taken to reduce the complexity of the detection process by introducing constraints in space and/or time. A modified sphere decoder was proposed in [6], which sacrifices performance to reduce the complexity of detection.The complexity of the MIMO detector depends on the number of bits mapped to a transmission vector (symbols) transmitted simultaneously via multiple antennas. In order to reduce its complexity, the low-density MIMO code (LDMC) was presented with the constraints for each transmitting vector [4, 5, 9]. For an LDMC, the parity-check matrix has to be divided into two layers. One layer defines subcodes which are embedded in each transmitting vector, and another glues these subcodes together. The goal of the double-layer structure is that the first layer reduces the complexity of the decoder, while the second layer has to be handed by an outer decoder. Unfortunately, the double-layer structure of the original LDMC only supports the outer-iterations and it cannot bolster the inner-iterations inside the decoder. This limits the performance and the flexibility of the decoding at the receiver. It seems that a systematic LDMC design that stands by both outer-iterations and inner-iterations for double-layer decoder still remains an open problem.In this paper, we introduce a novel double-layer decoder for a benefit of the LDMC design criterion over MIMO channels. One advantage of this structure is that the yielded parity-check matrix of an LDMC has full rank and hence can achieve the desired code rates. Another is that the present LDMC can be decoded with low complexity since it supports both inner-iterations and out-iterations at the receiver.This paper is organized as follows. In Section2, we introduce the LDPC coded MIMO channels. Some properties of the LDMC are presented for the benefits of the construction. Section 3 describes the conventional LDPC code with multiple parity-check (MPC) encoders. After that an LDMC based on the MPC encoder is designed in Section 4. Simulation results are given in Section 5. Finally, Section 6 concludes this paper.


## 2. System Model

At the output of the LDPC encoder, the encodedMtQ bits, s=[b1,…,bMtQ]∈{0,1}MtQ, are mapped into a group of Mt constellation symbols x=[x1,…,xMt]∈𝒜Mt, where each symbol xj is taken out of constellations 𝒜 of size 2Q. The sequence of constellation symbols is passed to the transmit filter, and then sent through Mt transmit antennas. At the receiver, the detector has to calculate the maximum posteriori probability for each bit, and this probability will be passed to the LDPC decoder for iterative decoding. After a finite number of inneriterations in the LDPC decoder, hard decisions, which are the estimated codewords, are made at the decoder. Soft information from the LDPC decoder is then passed back to the MIMO detector to produce the updated probabilities. The loop between the LDPC decoder and the MIMO detector is called outer-iteration.We consider a MIMO communication system withMt transmit antennas and Mr receive antennas. The MIMO channel model is described as
(1)y=Hx+N,
where y∈ℂMr×1 is the complex received signal vector, H∈ℂMr×Mt is the channel fading matrix with independent entries that are complex Gaussian distributed with zero mean and unit variance, N∈ℂMr×1 is the complex white Gaussian noise with variance σ2 per dimension, x∈ℂMt×1 is the complex transmitted signal vector that satisfies the component-wise energy constraint E(|xi|2)=Es/Mt, and the notation Es represents the total transmitted power. The channel information H is assumed to be known to the receiver but not the transmitter.Letb denote a set of MtQ-1 transmitted bits, which exclude the kth bit bk while x(b,bk) is a vector of Mt components containing the symbols corresponding to b and bk. For a given received signal vector y, we perform the bitwise detection [10] to determine the posteriori probability of bit bk, forallk∈{1≤k≤MtQ}, by calculating
(2)PM→L(bk)=∑b1(2πσ)Mre-∥y-Hx(b,bk)∥2/(2σ2)×∏bj∈bPL→M(bj)
or its log-likelihood ratio
(3)LM→L(bk)=log⁡PM→L(bk=1)PM→L(bk=0),
where ∥·∥2 denotes the norm square of a vector, the subscript M→L denotes the message passed from the MIMO detector to the LDPC decoder, and L→M denotes the message from the LDPC decoder to the MIMO detector.The remaining problem of this iterative decoding is the complexity of the MIMO detection. Next, we will show that the complexity of the MIMO detection can be reduced by introducing some constraints in the parity-check matrix of the LDPC codes, which are also called the LDMCs.The LDMC is a kind of the linear block codes that can be described with a parity-check matrixHc of the size m×n, subject to the constraint Hcx=0. The LDMC parity-check matrix can be described by two layers with
(4)Hc=(HgHe)=(HgHe′⋯00⋱00⋯He′).
The first layer Hg is a sparse parity-check matrix, and the second layer He defines multiple independent subcodes. Each subcode corresponding to He′ has a block length no more than MtQ.As the aforementioned structure, each transmission vector carriesMTQ bits. For the transmission, it has to be guaranteed that all bits of a subcode corresponding to He′ should be transmitted within one transmission vector. Thus, each transmission vector b carries an embedded code corresponding to He′. The action of Hg is to glue all embedded codes together. Since the matrix Hg is sparse and the embedded codes corresponding to the parity-check matrix He′ define code constraints to each MIMO transmission vector, the overall-coding process is called the LDMC coding scheme or LDMC.To enhance the performance of the LDMC coding scheme, we need to reduce the complexity of the MIMO detecting and the LDPC decoding in the combined MIMO transmission system, while keeping the overall data rate and the capacity approaching communication performance. As described, a straightforward approach is to embed constraints for the involved bits within one transmission vector. A simple constraint on several bits is a single parity-check (SPC) constraint. Namely, the matrixHe′ would become the parity-check matrix of an SPC code. Thus if we constraint the involved information bits in one SPC constraint, the overall possibility of detection is 2MTQ-1. Furthermore, if we constraint in q parity-check constraints embedded within one transmission vector, the overall possibility of detection will downscale to 2MTQ-q.In order to encode efficiently, a quasicyclic structure was proposed for the parity-check matrix of LDMCs [4, 5]. In the quasicyclic structure, the sparse matrix Hg consists of cyclic-permutation matrices and zero matrices. Since the subcodes He′ in transmission vectors are independent and should not be connected to each other, as shown in (4), the second layer He consists of only identity matrices and zero matrices. Therefore, He has no cyclic-permutation structure. Consequently, the flexibility of He may be reduced, which results in many short cycles. Therefore, He is only employed in the detection, not in the decoding. Since Hg alone is too sparse to be applied in the iterative decoding, there is no inner iterations in the decoder in [5]. Therefore, how to address the design of inner iterations in the LDMC is still a retained problem. In the next section, we will propose a simple LDMC to solve this problem.


## 3. LDPC Code Based on Multiple Parity-Check Codes

Recently, Baldi et al. have proposed an LDPC coding scheme on the basis of multiple serially concatenated multiple parity-check (M-SC-MPC) codes [11]. This code offers flexible code rate and code length with low encoding complexity. Let ni, ki, and ri denote code length, information length, and parity-check length of the ith MPC component code, respectively. The encoder of the ith MPC component code can be implemented as ri SPC encoders. The matrix cells of the ith encoder are filled in column-wise order. The first ri-si cells, with si=ki mod ri, are unused. The parity bit pj is calculated by XORing the elements of the row, which is stored in the last column, at the same row. We obtain a parity-check matrix Hi for the ith component code, consisting of a row of ⌈ni/ri⌉ identity matrices of size ri×ri, and the first ri-si columns are shortened. The yielded matrix Hi forms a block-row of the parity-check matrix Hc of the M-SC-MPC code. The M-SC-MPC code has information length k=k1, parity-check length m=∑i=1Mri and the code length n=k+m can be viewed as LDPC codes.If an interleaver is inserted before each MPC encoder, an LDPC code can be constructed with larger girths [12]. The parity-check matrix Hc can be designed in columnwise or rowwise to avoid short cycles. In the next section, we will introduce a modified progress edge-growth algorithm (PEG) to construct Hc see Algorithm 1. Each component matrix Hi has row weight ⌊nj/rj⌋ in ri-si rows, row weight ⌈nj/rj⌉ in the remaining si rows. Also, it has column weigh one in ni columns and column weight zero in the remaining n-ni columns. The interleaver of the ith MPC encoder is constructed according to the structure of designed parity-check matrix Hi.Algorithm 1:Modified PEG algorithm.
(1)q=0.(2)y=Ø(3)forl=0do(4)  arrange the check node degrees of thecheck node groupgl in nondecreasing orderxi=[xi0,xi1,…,xiri-1]=[ρ⌊ni/ri⌋,ρ⌊ni/ri⌋,…,ρ⌈ni/ri⌉].(5)end for(6)forj=0 to n-1do(7)ifj≥n-mthen(8)sc={cj-(n-m),…,cm-1}∖y.(9)else(10)sc={c0,c1,…,cm-1}∖y.(11)end if(12)fork=0 to M-1do(13)ifk=0then(14)ifj≥n-mthenevj0← edge (ci,vj), where evj0 is the first edgeincident tovj. This edge corresponds to the “1” inthe diagonal line of matrixHp.(15)elseevj0← edge (ci,vj), where i=(j+(r1-s1))modr1.(16)end if(17)elseexpand a subgraph fromvj up to depth l underthe current graph settingn̅vjl such that n̅vjl∩sc≠Øbutn̅vjl+1∩sc=Ø, or the cardinality of n̅vjl stopsincreasing, thenevjk← edge(ci,vj), where evjk is thekth edge incident to vj and ci is a check node pickedfrom the setn̅vjl∩sc having the lowest check-nodedegree.(18)end if(19)ifthe degree of ci equals xkqthenAdd ci into Y.xi←xi∖xkq.q=q+1.(20)end iffind out which check node group gi includes ci.sc←sc∖gi.(21)end for(22)end forTheorem 1 (full-rank criteria).
The parity-check matrices of LDPC codes on the basis of the MPC encoders are of full rank, and hence they can achieve the desired code rates.Proof.
If all the rows of the component parity-checkHi are summed, respectively, a vector will be obtained with the first ni elements are ones and the remaining n-ni elements are zeros. Then it is obvious that any row of Hc cannot be obtained by a linear combination of the other rows in Hc. Therefore, we can get the desired code rate R=k/n.Theorem 2 (low-complexity criteria).
The encoding com-plexity of the LDPC code on the basis of the MPC encoders is upper bounded by∑i=1M(ki-ri) and lower bounded by ∑i=1M⌈ki/ri⌉-1, respectively.Proof.
We evaluate the computation complexity of the encoding processing. There are three cases of encoding processing [13]. If the ith component encoder generates the ri parity bits in parallel, the ith component encoder determines ri parity bits with ki-ri XOR operations. In this case, ∑i=1M(ki-ri) XOR operations are required to obtain all the parity bits. The encoding processing is accomplished from the 1st MPC component encoder to the Mth MPC component encoder in M steps. If the ith component encoder generates the ri parity bits in serial, the ith component encoder determines ri parity bits serially with ⌈ki/ri⌉-1 XOR operations. In this case, ∑i=1M(⌈ki/ri⌉-1) XOR operations are required to obtain all the parity bits. Therefore, the encoding processing is completed from the 1st SPC encoder to the mth SPC encoder in m steps. If the encoding processing is a combination of the above-mentioned two cases, the complexity and encoding time is lower bounded by the parallel case and upper bounded by the serial case.


## 4. LDMCs Based on MPC Codes

To illustrate the double-layer structure of the LDMC, we propose a simple LDMC as an example in this section.We consider a parity-check matrixHc given by
(5)Hc=[HdHp]=[H1H2H3]=[100110100000011001010000011010111000100101000100001010110110110101001001],
where the subscript “T” denotes the transpose of the matrix. This is a parity-check matrix that corresponds to an LDPC code [d1,d2,…,d6,p1,p2,…,p6] of length 12, where d1,d2,…,d6 are the information bits and p1,p2,…,p6 are the parity bits. It is by no means a good LDPC code, which is nothing more than a simple example. The parity-check matrix Hc in (5) can be divided into three 2×12 submatrices, that is, H1, H2, H3. In each column of Hi (i=1,2,3), there is only one “1” element. Due to the special structure of the three submatrices H1, H2 and H3, we define Hg=(H1TH2T)T and He=H3. Therefore, we first obtain the parity bits [p5,p6] from H3, then the parity bits [p3,p4] from H2, and the parity bits [p1,p2] from H1. The encoding processing of this code includes three steps as follows.Step 1.
Given the information bits[d1,d2,…,d6], compute the parity bits [p5,p6] based on the last two columns of the third parity-check matrix H3.Step 2.
Given the information bits[d1,d2,…,d6] along with the yielded parity bits [p5,p6] in Step 1, compute the parity bits [p3,p4] based on the ninth column and the tenth column of the second parity-check matrix H2.Step 3.
Given the information bits[d1,d2,…,d6] along with the previous parity bits [p3,p4,p5,p6], compute the parity bits [p1,p2] based on the seventh column and the eighth column of the first parity-check matrix H1.Now we transmit this code through a MIMO system with two transmit antennas and 8PSK modulation scheme. Each transmission vector carries 6 bits which results in2MtQ=64 possibilities reflecting all bit possibilities. However, because of the parity-check constraints in H3, that is,
(6)d3⊕d5⊕p1⊕p2⊕p4⊕p5=0,d1⊕d2⊕d4⊕d6⊕p3⊕p6=0,
where ⊕ denotes the XOR operation, we can divide the code word into two transmission vectors, that is, [d3,d5,p1,p2,p4,p5] and [d1,d2,d4,d6,p3,p6]. Each transmission vector contains one parity-check constraint. This results in 2MTQ-1=32 possibilities. Therefore, the present LDPC code is an LDMC in essence. In this code, the first layer that glues the subcodes is Hg and the second layer that defines the subcode is He=H3. Note that we can transform He into the diagonal form by column permutations, which results in the parity-check matrix
(7)H̅c=[011000101000100100010100111100010010000010101100111111000000000000111111]=(H̅gTH̅eT)T=(H̅1TH̅2TH̅3T)T.
It is obvious that the first transformed layer H̅g is a sparse parity-check matrix and the second layer H̅e can generate two unconnected subcodes corresponding to H̅e′=[1,1,1,1,1,1].We note that if we letHg=(H2TH3T)T and He=H1, in a similar way we calculate the parity bits [p1,p2] from H1, then the parity bits [p3,p4] from H2, and the parity bits [p5,p6] from H3. Therefore, the equivalent constructions of this code can be described as the following.Step E1
given the information bits[d1,d2,…,d6], compute the parity bits [p1,p2] based on H1.Step E2
given the information bits[d1,d2,…,d6] along with the yielded parity bits [p1,p2], compute the parity bits [p3,p4] based on H2.Step E3
given the information bits[d1,d2,…,d6] along with the previous parity bits [p1,p2,p3,p4], compute the parity bits [p5,p6] based on H3.According to the aforementioned LDMC construction based on three matrices{Hi:i=1,2,3}, the proposed design approach can be generalized with M block matrices {Hi:i=1,…,M}.Theorem 3.
The LDPC code on the basis of the MPC component encoder in (4) is an LDMC, where
(8)Hc=(HdHp)=(HgTHeT)T
with Hg=(H1TH2T⋯HM-1T)T and He=HM. Generally, the first layer Hg can be selected as Hg=(H1T⋯Hi-1THi+1T⋯HMT)T and the second layer He can be selected as He=Hi, foralli∈{1,…,M}.Proof.
The present LDMC is a straightforward extending of the LDMC given in (5). Therefore, the proof of this theorem can be derived in a similar way, which is omitted for simplicity.
For simplicity, we consider the LDMC withHg=(H1TH2T⋯HM-1T)T and He=HM. We note that there are rM SPC constraints in the parity-check matrix He that has row weight ⌊nM/rM⌋ in the first rM-sM rows and row weight ⌈nM/rM⌉ in the remaining sM rows. Each subcode He′ involves q SPC constraints. We divide rm SPC constraints into rm/q separate subgroups. At the transmitter, each transmission vector involves one of the rm/q subgroups. Then the overall possibilities for the MIMO detection is downscaled from 2MtQ to 2MtQ-q. The larger q means the smaller complexity of the MIMO detection. Namely, let rm/q=n/ne′, and then it is obvious that the larger ne′ implies the smaller complexity of the MIMO detection. Since ne′≤MtQ, the optimal block length of the subcode is
(9)ne′=MtQ.
In addition, the parity-check matrixHc of the present LDMCs should satisfy the following two constraints:  (1)
theHp part of Hc contains the lower triangular pattern;(2)
in each column ofHi, foralli∈{1,…,m}, of Hc, there is only one “1” element.
The first constraint ensures that the present LDMC is linear encodable [14]. The second constraint guarantees that the ri parity bits can be generated by the ri parity-check constraints, simultaneously, in the ith component encoder corresponding to the matrix Hi [11–13]. Observing two constraints, the parity-check matrix Hc of the LDMC can be efficiently designed with the modified progress edge-growth (PEG) algorithm.Remark 4.
In the present algorithm, lines 1–5 and lines 20-21 are used to ensure that the parity-check matrixHi has row weight ⌊ni/ri⌋ in ri-si rows and row weight ⌈ni/ri⌉ in the remaining si rows, which are required for the design of parity-check matrix of an LDMC with a double-layer structure. Line 14 and line 17 are used to guarantee that Hp is a lower triangular matrix, which is for the desired code rate. Since there is no interleaver in front of the first component encoder, line 15 is used to ensure that H1 consists of identity matrices with the first r1-si columns eliminated, as shown in (5). Due to this special structure, the LDPC decoding can be well performed with low complexity.Remark 5.
SinceHc is obtained from the modified PEG algorithm, the girth of Hc and He can be enlarged, simultaneously [12]. Therefore, the matrix He can be used in both detection and inner iteration. Consequently, we can perform multiple out iterations between MIMO detector and LDPC decoder at the receiver. In each out iteration, the MIMO detection is performed once followed by a number of inner iterations of LDPC decoding. The decoding process is halted if the decoder converges to a valid code or a maximum number of iterations is reached. It is obvious that the proposed double-layer LDMC is different from the quasicyclic LDMC [4], where the PEG algorithm is based on the permuted identity matrices.


## 5. Simulations

So far, we have constructed an LDMC with the modified PEG algorithm in the previous section. In order to simulate the proposed LDMC denotedcM with simplicity, it is assumed that the block length of the LDMC is n=1920 and the code rate is 0.5. The numbers of the component encoder M are 5 and 6, respectively, that is, M∈{5,6}. Some parameters are given as follows:  (1)
M=5, r1=360, r2=360, r3=360, r4=360, r5=480, and L=⌈n/r5⌉=4;(2)
M=6, r1=288, r2=288, r3=288, r4=288, r5=288, r6=480, and L=⌈n/r6⌉=4.The simulation results are in terms of the frame error rate (FER) with the iterative decoding. We make use of the QPSK modulation and the 16-QAM modulation transmissions over a4×4 MIMO channels, as shown in Figures 1 and 2. Therefore, the block length of transmission vector is 8 with ⌈ne′/L⌉=2. We simulate the proposed codes in two ways. For one hand, we perform 3 outer iterations and 50 inner iterations, shown in Figure 1, for both c5 and c6. For another, we perform 50 outer iterations and no inner iteration. For a fair comparison, we have also simulated the original LDMCs with a minor modification in [5]. The He′ part
(10)[1111000011110000001100110011001101010101010101010000111111110000],
which involves a parity-check matrix [5], is replaced with the matrix
(11)[1111000000000000000011110000000000000000111100000000000000001111],
which involves 4 parity-check constraints of length 4. Each transmission vector of length 8 involves 2 SPC constraints. This modified code is denoted by c0. The performance curve of c0 is illustrated with 50 outer iterations and no inner iteration.Figure 1
FER performances of the proposed LDMCsc5 and c6 with QPSK modulation.Figure 2
FER performances of the proposed LDMCsc5 and c6 with 16QAM modulation.It is shown in Figure2 that three LDMCs, c0, c5, c6, can downscale overall possibilities of the MIMO detection from 28 to 26. The proposed two codes c5 and c6 perform the similar performances as that of the original LDMC c0 when no inner iteration is applied in the LDPC decoder. However, since the present LDMCs support inner iterations in the LDPC decoder, we can improve the performance of these codes by increasing several inner iterations in the LDPC decoder.


## 6. Conclusion

A double-layer structure LDMC is introduced with the LDPC decoder and the MIMO detector. It provides both inner iterations and outer iterations at the receiver, which gives more flexibility for detecting and decoding than that of the original LDMC. The advantage of the double-layer LDMC is that the parity-check matrix has the full rank to achieve the desired code rate, which can be efficiently employed in a modified PEG algorithm. The present LDMC also reduces the complexity of the MIMO detection due to the low-density of the parity-check matrix. Simulations show that the performance of the LDMC is enhanced with the increasing inner iterations in the LDPC decoder.



---

*Source: 716313-2012-01-12.xml*