Low-density multiple-input multiple-output code (LDMC) can reduce the complexity of tree-search detection in MIMO systems. In this paper, we present a new modified progressive edge-growth (PEG) algorithm to construct large girth LDMCs, which are referred to as PEG-LDMCs. We analyze the complexity of the LDMC constrained sphere decoding (SD) and show that the LDMC constrained SD detection can be used for high reliability of the data transmission in MIMO systems. Furthermore, we propose two new efficient iterative decoding algorithms for LDMCs, which are high speed serial decoding and fast convergence shuffled decoding. Finally, we compare the bit error rate (BER) performance of PEG-LDMCs to that of the existing LDMCs. The simulation results show that the PEG-LDMCs can achieve better BER performance than that of the existing LDMCs.
Abkürzungen
BER
Bit error rate
BP
Belief propagation
CSI
Channel state information
FCSD
Fast convergence shuffled decoding
HSSS
High-speed serial decoding
LDMC
Low-density MIMO code
LDPC
Low-density parity-check
LLR
Log-likelihood ration
MIMO
Multiple-input multiple-output
MMSE
Minimum mean-square error
PEG
Progressive edge-growth
SD
Sphere decoding
ZF
Zero-forcing
1 Introduction
Multiple-input multiple-output (MIMO) techniques have been widely studied during the past decades as they can provide significant multiplexing and diversity gains in transmission. Therefore, MIMO techniques have 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‐4].
In order to provide high reliability of the data transmission in MIMO systems, special attention has to be paid in the receiver design. Maximum-likelihood (ML) detection is the optimal detection for MIMO systems [5, 6]. However, the complexity of the exhaustive searching in ML detection is too high for practical use. Therefore, suboptimal but low complexity detections were proposed, which include linear detection, such as zero-forcing (ZF) [7, 8], minimum mean-square error (MMSE) [9], and non-linear detection, such as sphere decoding (SD) [10]. The performance of MMSE detection is better than that of ZF detection, due to the fact that the correlation between the noises in ZF detection is neglected in the projection operation. However, both the ZF detection and the MMSE detection suffer from serious performance degradation with respect to the optimal ML detection. On the other hand, the SD detection draws attention of researchers as it can achieve a near-ML detection performance [11]. The main idea of the SD detection is that it only searches the ML candidate symbols which lie inside a specific sphere. For a given sphere size, the detection complexity of SD detection in MIMO systems becomes very high when the number of candidates is large.
Anzeige
Practically, error-correction codes are usually applied in MIMO systems. In particular, low-density parity-check (LDPC) codes have drawn attention of many researchers due to their Shannon limit approaching performance [12‐14]. As a subclass of LDPC codes, low-density MIMO codes (LDMCs) were presented in [15, 16], which reduce the complexity of the ML detection by introducing constraints in each transmission vector. The transmission vector is defined as the set of symbols which are transmitted simultaneously via multiple antennas. In [17], LDMCs with low-encoding complexity are further presented.
Motivated by the near-ML detection performance of the SD detection and the complexity reduction property of the LDMCs, in this paper, we study the design of LDMCs and the concatenation strategy of LDMCs and SD detection in MIMO systems.
Furthermore, we propose more efficient iterative decoding algorithms for LDMCs. It is well known that the iterative decoding converges to the optimal solution provided that the parity-check matrix of the code is of large girth [18]. Therefore, LDMCs of large girth are particularly desirable. Hence, we propose a modified progressive edge-growth (PEG) algorithm to construct LDMCs of large girth. The contributions of this paper are as follows:
We propose a new modified PEG algorithm to construct large girth LDMCs for good performance.
We analyze the complexity of SD detection in the LDMC-coded MIMO systems, which indicates that the LDMC-constrained SD detection can be used for MIMO systems with large number of transmit antennas.
We propose two efficient iterative decoding algorithms for LDMCs for high speed and fast convergence decoding.
This paper is organized as follows. In Section 2, we review MIMO systems and LDMCs. In Section 3, we introduce a modified PEG algorithm to construct large girth LDMCs. In Section 4, we compare the complexity of LDMC-constrained SD detection with that of the MMSE and ZF detections. In Section 5, we introduce two new shuffled decoding algorithms for LDMCs. Examples of the LDMC-constrained SD detection in MIMO systems and the corresponding simulation results are given in Section 6. Finally, Section 7 concludes the paper.
Anzeige
Notation: bold lower case letters represent vectors, while bold upper case letters denote matrices. (·)T, (·)H, and ∥·∥ denote transpose, Hermitian, and norm operations, respectively. \(\mathbb {C}^{m\times n}\) stands for the complex space of size m×n.
2 Preliminaries
This section introduces some background concepts that will be used throughout the paper.
2.1 MIMO systems
Let Mt be the number of transmit antennas and Mr be the number of receive antennas. The source binary information bits b=[b1,⋯,bnR] are first encoded using an LDPC encoder to generate a codeword \(\mathbf {w}=\left [\mathbf {w}_{1}, \mathbf {w}_{2}, \cdots, \mathbf {w}_{\frac {n}{M_{t}Q}}\right ]\), where R is the code rate and n is the length of the codeword. Then, each group of MtQ coded bits \(\mathbf {w}_{i}=[b_{1},\cdots,b_{M_{t}Q}]\phantom {\dot {i}\!}\) is mapped to a group of Mt transmission vector \(\phantom {\dot {i}\!}\mathbf {x}=[x_{1},\cdots,x_{M_{t}}]^{T}\), where xj is taken out of the constellations of size 2Q. x is then passed to the transmit filter and sent through the Mt transmit antennas. x is denoted as the transmission vector in the following.
Without loss of generality, we express the system model as
$$ \mathbf{y}=\mathbf{Hx}+\mathbf{z}. $$
(1)
Here, \(\mathbf {y}\in \mathbb {C}^{M_{r}\times 1}\) is the complex received signal vector. \(\mathbf {H}\in \mathbb {C}^{M_{r}\times M_{t}}\) is the Rayleigh fading channel matrix with independent entries that are complex Gaussian distributed with zero mean and unit variance. H is assumed to be known to the receiver, but not to the transmitter, and the channel coefficient randomly varys in time. \(\mathbf {z}\in \mathbb {C}^{M_{r}\times 1}\) is complex white Gaussian noise with variance σ2 per dimension.
Referring to [22‐24], the received signal is iteratively detected and decoded by mutually exchanging soft information between the detector and LDPC decoders. The detection computes the log-likelihood ratios (LLRs), Li, for each coded bit by using
each of whose elements is the number of constellation symbols to be searched at each antenna. Here, ηP+ηQ=Mt. ηQ denotes the number of candidates, which are considered to be fully searched, and ηP denotes the number of candidates are not required to be searched. It is clear that if ηQ=Mt, the SD detection becomes the ML detection.
The search over bit possibilities within x scales exponentially with the number of antennas Mt and the constellation size Q. In addition, the complexity of SD detection is very high when the number of bits mapped to the transmission vector and the constellation are large. Then, the complexity of the SD detection is the major problem for applying SD detection to MIMO systems with large number of transmit antennas. In the next subsection, we will describe that the LDMC is a subclass of LDPC codes and can reduce the complexity of the SD detection for MIMO systems.
2.2 Low-density MIMO codes
LDMCs are linear block codes which can be described by PwT=0, where P is a parity-check matrix of n columns and m rows. Therefore, the overall code rate is R=1−m/n. The LDMC parity-check matrix can be described by two layers as
The first layer Pg is a sparse parity-check matrix, while the second layer Pe is defined by multiple, unconnected sub-codes Pe′. Each sub-code Pe′ corresponding to wi has a code length Ne′≤MtQ. Let Ng=n/Ne′ denote the number of sub-codes in an LDMC codeword. The size of Pe′ is q×MtQ and the size of Pg is (m−Ngq)×n.
As mentioned before, each transmission vector x carries MtQ bits. It has to be guaranteed that all bits of a sub-code Pe′ are transmitted within one transmission vector x. Thus, each transmission vector x carries an embedded code Pe′, i.e., \(\mathbf {P}_{e}'\mathbf {w}_{i}^{T}=0\).
It has been shown that, the SD detection achieves near-ML performance if \(\eta _{Q}\geq \sqrt {M_{t}}-1\) [19]. Therefore, it requires at least \(2^{Q(\sqrt {M_{t}}-1)}\) times searching to achieve near-ML performance. With q constraints in LDMC-constrained SD detection, the number of searching in LDMC-constrained SD will downscale to \( 2^{Q(\sqrt {M_{t}}-1)-q}\) [15, 16].
3 LDMC design based on PEG algorithm
It was stated in [18] that large girths facilitate iterative decoding and impose a respectable minimum distance bound that enhances decoding performance. Among the existing approaches for constructing LDPC codes, one of the most successful approaches is PEG algorithm [17]. Recently, several PEG algorithms have been proposed [25‐27], which can be applied to construct Pe. For a given symbol node sj, define its neighborhood within depth l, \(N^{l}_{s_{j}}\), as the set consisting of all check nodes reached by a subgraph (or a tree) spreading from symbol node sj within depth l. Its complementary set, \(\bar {N}^{l}_{s_{j}}\), is defined as \(V_{c} \backslash N^{l}_{s_{j}}\), or equivalently \(\bar {N}^{l}_{s_{j}}\bigcup N^{l}_{s_{j}}=V_{c}\). Denote the symbol-degree sequence by
in which \(d_{s_{j}}\) is the degree of symbol node sj, 0≤j≤n−1 and \(d_{s_{0}}\leq d_{s_{1}}\cdots \leq d_{s_{n-1}}\). The PEG algorithm constructs a Tanner graph by operating progressively on symbol nodes to establish edges required by Ds. To establish an edge incident to sj, the PEG algorithm first spreads a tree from sj up to maximum depth l and then chooses a check node ci at random from the check nodes of the lowest degree in \(\bar {N}^{l}_{s_{j}}\). In this section, we introduce a modified PEG algorithm to construct large girth LDMCs, which is referred to as PEG-LDMC algorithm and the corresponding codes as PEG-LDMCs in this paper.
Let Dg and De denote the degree sequence associated with Pg and Pe, respectively. The parity-check matrix P of LDMC can be constructed by the PEG-LDMC algorithm with the following steps.
Preprocessing process :
From the optimized degree distribution for the code rate 1−(m−Ngq)/n and code rate 1−q/Ne′, generate the symbol-degree sequences \(\phantom {\dot {i}\!}\mathbf {D}_{g}=\{d_{s_{0}},d_{s_{1}},\ldots,d_{s_{(N_{e}'-1)}}\}\) and \(\phantom {\dot {i}\!}\mathbf {D}_{e}=\{d_{s_{0}},d_{s_{1}},\ldots,d_{s_{(N_{e}'-1)}}\}\), respectively.
Constructing process :
Step 1. Construct q×Ne′ submatrix Pe′ of the form \(\mathbf {P}_{e}'=[\bar {\mathbf {P}}_{e}'~\mathbf {I}]\) with the PEG algorithm and symbol-degree sequence De, where I denotes an identity matrix of size q×q and \(\bar {\mathbf {P}}_{e}'\) is of size q×(Ne′−q).
Step 2. Construct the columns of Pg, which are in the same columns as Pe in P. If the construction of P is not finished, go back to Step 1. Otherwise, stop the construction.
It is worth pointing out that in the PEG-LDMC algorithm, the submatrices Pe and Pg of the parity-check matrix P are constructed simultaneously. Therefore, the girth of P is optimized. A high-level description of the PEG-LDMC algorithm is given in Algorithm 1 and the algorithms for steps 1 and 2 are given in Algorithm 2 and Algorithm 3, respectively.
4 Analysis of detection complexity
In this section, we compare the detection complexity of the LDMC-constrained SD detection in the LDMC coded MIMO system with that of ZF and MMSE detections. To estimate the computational complexity, we use the number of multiplications required in the detection. Rough computational complexity estimations are given in Table 1. The number of additions is relatively small, therefore, it is omitted in the analysis.
Table 1
Number of multiplications in LDMC-constrained SD, ZF, and MMSE detections
Detection technique
Computational complexity
LDMC-constrained SD
\(2^{Q(\sqrt {M_{t}}-1)-q} (M_{t} + 2)\)
Zero forcing
\(2M_{t}^{3}\)
MMSE
\(2M_{t}^{3}\)
Generally, SD is a searching algorithm for detection. It performs an exhaustive search based on setting a radius constraint. This has been proved by Hassibi [11] that the expected total number of points visited by the sphere decoding is proportional to the total number of candidates inside spheres of dimension k=1…m:
where d is radius and Γ(n)=(n−1)! represents the Gamma function. Clearly, ω depends on the radius d. Therefore, the channel state information (CSI) estimation does not impact the complexity in SD.
Specifically, if SD is performed in an LDMC coded MIMO system, the norm ∥y−Hx∥2 in the LDMC-constrained SD detection in (2) needs 2(Mt+2) multiplications. Thus, the total number of multiplications in the LDMC-constrained SD detection is
From the (8) and (9), it is clear that the MMSE and ZF detections consist of a complex inversion of Mt×Mt matrix, and some matrix multiplications and additions. Mt×Mt matrix inverse and matrix multiplication operations are both known to need \(M_{t}^{3}\) multiplications. Consequently, the total number of multiplications in MMSE and ZF detections are both
Note that the computational complexity of linear detector mainly depend on Mt while the computational complexity of LDMC-constrained SD detection depends on Mt, Q, and q. If q is large enough, it is possible that the computational complexity of LDMC-constrained SD detection is lower than that of ZF and MMSE detections. Let \(M_{t}^{3} \geq 2^{Q(\sqrt {M_{t}}-1)-q}2(M_{t} + 2)\), we have
If q satisfies condition (11), the computational complexity of LDMC-constrained SD detection with near-ML performance can be lower than that of ZF and MMSE detections. From Fig. 1, we can see that the complexity of the LDMC-constrained SD detection is lower than that of the MMSE and ZF detections if we choose q properly. Note that a larger q reduces the size of Pg of the LDMC matrix, which is constructed by the PEG algorithm. Among the existing approaches for constructing LDPC codes, the most successful one is the PEG algorithm. The LDPC code constructed by the PEG algorithm is one of the best codes of good error-correcting performance. Therefore, a larger q not only leads to worse error-correcting performance, but also lower SD detection complexity. Hence, there is a trade-off between performance and detection complexity by choosing the value q.
Fig. 1
Complexity comparison of MMSE, ZF, and LDMC-constrained SD detections for varying Mt and q
×
5 Efficient decoding algorithm
In this section, we proposed two new decoding algorithms for LDMCs for high speed decoding and fast convergence decoding. We denote the set of symbol nodes that participate in check node ci by N(i)={j:Pij=1}, and the set of check nodes in which sj participates as M(j)={i:Pij=1}.
The standard belief propagation (BP) decoding algorithm consists of initialization, check-node updating, symbol-node updating, stopping criterion test, and output steps [20]. In the proposed decoding algorithms, the initialization, stopping criterion test, and output steps remain the same as that in the standard BP algorithm, and therefore omitted here.
5.1 High-speed serial decoding
In LDMCs, the code length n can be divided into sub-codes Pe′ of length Ne′. In the high-speed shuffled decoding algorithm, the updating of sub-codes is processed sequential, but the updating of symbol nodes and check nodes corresponding to each sub-code Pe′ remain in parallel. Let \(r_{ij}^{l}\) and \(g_{ij}^{l}\) be the LLRs sent from check node ci to symbol node sj, and sent from the symbol node sj to check node ci, respectively, in the lth iteration.
In the standard BP algorithm, all value \(r_{ij}^{l}\) should be updated before updating all value \(g_{ij}^{l}\). We observe that, since the sub-codes Pe′ in transmission vectors should not be connected to each other as shown by (4), all value \(r_{ij}^{l}\) for updating \(g_{ij}^{(l+1)}\) of kth sub-code have already been updated before updating \(r_{ij}^{l}\) of the (k+1)th sub-code, 1≤k≤(Ng−1). Therefore, the updating of \(g_{ij}^{(l+1)}\) for kth sub-code can be computed in parallel with the updating of \(r_{ij}^{l}\) for (k+1)th sub-code. In the high-speed serial decoding (HSSD), the check-node updating and the symbol-node updating of the HSSD are carried out alternately as follows.
Check-node updating corresponding toPg: for 1≤i≤(m−Ngq) and each j∈N(i), process
where Lj is the LLR of jth bit and initially set Lj=(4/N0)yj.
Note that compared to the serial BP algorithm, our algorithm has higher decoding speed without increasing the complexity.
5.2 Fast convergence shuffled decoding
In the HSSD algorithm, the check-node updating corresponding to Pg should be done for only once in each iteration. To increase the convergence speed, we modified the HSSD and propose the fast convergence shuffled decoding (FCSD) algorithm in this subsection. In this decoding algorithm, the check-node updating corresponding to Pg will be done at each time the check-node updating corresponding to sub-code is done. The check-node updating and the symbol-node updating of the FCSD are carried out as follows. For 1≤g≤Ng, process jointly the following two steps:
Check-node updating: for 1≤i≤(m−Ngq), k·q≤i≤(k+1)·q and each j∈N(i), process (12) and (13).
Symbol-node updating: for k·Ne′≤j≤(k+1)·Ne′ and each i∈M(j), process (14) and (15).
Note that compared to the high-speed serial decoding, this algorithm has faster convergence speed [21].
6 Simulation results
In this section, we compare the bit error rate (BER) performance of the PEG-LDMCs, LDMCs proposed in [17] and original LDMCs [16]. The PEG-LDMCs are constructed with the proposed PEG-LDMCs algorithm. The code rate is R=0.5. The channel matrix H is assumed to remain constant during the transmission of each codeword. We perform three outer-iterations between MIMO detector and LDPC decoder. In each outer-iteration, MIMO detection is performed followed by 40 inner-iterations inside LDPC decoder. The decoding process is halted if the decoder converges to a valid code or a maximum number of outer and inner iterations are reached. Note that in [16, 17], only the physical layer is considered. Therefore, for the sake of fairness, we have only considered the LDMCs of the same length as that of [16, 17], which are transmitted over the physical layer.
Figure 2 shows the BER performance of proposed PEG-LDMCs, LDMCs proposed in [17] and original LDMCs [16]. The transmission is over a 4×4 MIMO channel with 16-QAM and 64-QAM modulations. The first layer Pg is of size 480×1920 and 480×2880 for each modulation, respectively. Therefore, the parity-check matrix P of the corresponding LDMCs is of size 960×1920 and 1440×2880 for 16-QAM and 64-QAM. Thus, the code length is n=1920 for 16-QAM and n=2880 for 64-QAM, respectively. For the proposed PEG-LDMCs, the HSSD and FCSD algorithms are both applied for decoding. It can be seen that our proposed PEG-LDMCs with HSSD and FCSD algorithms have about 0.3 and 0.5 dB performance gain compared to original LDMCs with 16-QAM modulation, and they have about 0.1 and 0.3 dB performance gain compared to LDMCs in [17] with 16-QAM modulation. The proposed PEG-LDMCs with HSSD and FCSD algorithms also have about 0.4dB and 0.6dB performance gain compared to original LDMCs with 64-QAM modulation, and they have about 0.15 and 0.35 dB performance gain compared to LDMCs in [17] with 64-QAM modulation. This is due to the reason that the girth of the PEG-LDMC is optimized globally by the PEG-LDMC algorithm and the FCSD has faster convergence speed. Therefore, the performance of PEG-LDMCs with FCSD algorithm is better than that of PEG-LDMCs with HSSD algorithm and original LDMCs in [16].
Fig. 2
BER performance comparison of PEG-LDMCs, LDMCs proposed in [17] and original LDMCs in [16] with 16-QAM and 64-QAM
×
Figure 3 shows the BER performance of proposed PEG-LDMCs, LDMCs proposed in [17] and original LDMCs. The simulations are under 4×4 MIMO and 16×16 MIMO with 16-QAM modulations. For the proposed PEG-LDMCs, the proposed HSSD and FCSD algorithms are also applied for decoding. It can be seen from Fig. 3 that our proposed PEG-LDMCs with HSSD and FCSD algorithms have about 0.5 and 0.6 dB performance gain compared to original LDMCs over a 16×16 MIMO channel, and they have about 0.1 and 0.3 dB performance gain compared to LDMCs in [17] over a 16×16 MIMO channel. This is due to the reason that the performance of LDMCs depends on the girth, and our proposed new modified PEG algorithm can construct PEG-LDMCs with a girth of 8, which is larger than that of LDMCs proposed in [17].
Fig. 3
BER performance comparison of PEG-LDMCs, LDMCs proposed in [17] and original LDMCs in [16] with 4×4 MIMO and 16×16 MIMO
×
7 Conclusions
In this paper, we have introduced the PEG-LDMC algorithm to construct LDMCs of large girth. In order to reduce the complexity of detection, SD detection has been adopted into LDMC coded MIMO systems. The complexity of LDMC-constrained SD detection has been analyzed and compared to that of MMSE and ZF detections. Two new decoding algorithms have also been proposed for high-speed decoding and fast convergence decoding. The simulation results have shown that the proposed PEG-LDMCs with new decoding algorithms achieved better BER performance than that of LDMCs proposed in [17] and original LDMCs in [16].
8 Methods/Experimental
The purpose of this work is to reduce the detection complexity in the MIMO systems and to achieve a good BER performance. For this purpose, we use the method which is referred to as LDMC-constrained SD detection. Since LDMCs with large girth have good performance, we propose a new modified PEG algorithm to construct large girth LDMCs. In this paper, we analyze the complexity of SD detection in the LDMC coded MIMO systems, and compare it to ZF detection and MMSE detection. Furthermore, we propose high-speed serial decoding and fast convergence shuffled decoding in order to improve the BER performance.
In this paper, the comparison of BER performance among the PEG-LDMCs, original LDMCs [16], and LDMCs proposed in [17] is presented. The PEG-LDMCs are constructed with the proposed PEG-LDMCs algorithm. The function to generate the LDMCs and proposed PEG-LDMCs algorithm for MIMO systems can be made by MATLAB code. Experimental results in this paper had performed by using MATLAB R2016a on Intel Core i7-4790 @ 3.60GHz platform.
Acknowledgements
We gratefully acknowledge the MDMC Lab, Chonbuk National University, Korea and Donghua University, China, which provided the simulation platform.
Funding
This work was supported by National Natural Science Foundation of China (61671143,61631004,61571315), and the Initial Research Funds for Young Teachers of Donghua University.
Availability of data and materials
All data are fully available without restriction.
Competing interests
The authors declare that they have no competing interests.
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
