This paper proposes reliability-based parametric decoding of low-density lattice codes (LDLC). We define the reliability of the check-to-variable messages for two purposes. The first one is to choose to approximate the infinite Gaussian mixtures by one or two Gaussians. The reliability of each check-to-variable message is calculated. If there is higher reliability than a fixed threshold value, one Gaussian will be selected; otherwise two Gaussians will be used. The other purpose is for the updating sequence of variable nodes of the parametric shuffled BP (SBP) decoding algorithm. The parametric SBP increases the convergence speed. The updating sequence of SBP follows the order of reliability of the check-to-variable messages from high to low. The numerical results show that the proposed algorithm gives superior performance and lower complexity compared to two or three Gaussian decoding algorithm. At a probability of symbol error equal 10-4and n = 100 and 1000, the proposed algorithm gains 0.25 and 0.2 dB, respectively. Moreover, the proposed algorithm provides lower decoding time, fewer number of iterations for convergence and lower memory requirement.
This paper proposes reliability-based parametric decoding of low-density lattice codes (LDLC). We define the reliability of the check-to-variable messages for two purposes. The first one is to choose to approximate the infinite Gaussian mixtures by one or two Gaussians. The reliability of each check-to-variable message is calculated. If there is higher reliability than a fixed threshold value, one Gaussian will be selected; otherwise two Gaussians will be used. The other purpose is for the updating sequence of variable nodes of the parametric shuffled BP (SBP) decoding algorithm. The parametric SBP increases the convergence speed. The updating sequence of SBP follows the order of reliability of the check-to-variable messages from high to low. The numerical results show that the proposed algorithm gives superior performance and lower complexity compared to two or three Gaussian decoding algorithm. At a probability of symbol error equal 10-4and n = 100 and 1000, the proposed algorithm gains 0.25 and 0.2 dB, respectively. Moreover, the proposed algorithm provides lower decoding time, fewer number of iterations for convergence and lower memory requirement.
Low density lattice codes (LDLC) can be decoded efficiently using iterative decoding, and approach the capacity of the AWGN channel. In the iterative LDLC decoder the messages are Gaussian mixtures. In any implementation, the Gaussian mixtures must be approximated. This work describes a three/two Gaussian parametric LDLC decoder. Internally at the variable node the periodic Gaussian mixtures are approximated with three or two Gaussians, while the messages between nodes are single Gaussians. The proposed approximation is more accurate than the previously-proposed approximation. Numerical results shows that for moderate dimension, e.g. n = 1, 000, the two Gaussian approximation is sufficient for accurate performance. But for large dimension, e.g. n = 10, 000, three Gaussians are needed.
Low density lattice codes (LDLC) are a family of lattice codes that can be decoded efficiently using a message-passing algorithm. In the original LDLC decoder, the message exchanged between variable nodes and check nodes are continuous functions, which must be approximated in practice. A promising method is Gaussian approximation (GA), where the messages are approximated by Gaussian functions. However, current GA-based decoders share two weaknesses: firstly, the convergence of these approximate decoders is unproven; secondly, the best known decoder requires O(2d) operations at each variable node, where d is the degree of LDLC. It means that existing decoders are very slow for long codes with large d. The contribution of this paper is twofold: firstly, we prove that all GA-based LDLC decoders converge sublinearly (or faster) in the high signal-to-noise ratio (SNR) region; secondly, we propose a novel GA-based LDLC decoder which requires only O(d) operations at each variable node. Simulation results confirm that the error correcting performance of proposed decoder is the same as the best known decoder, but with a much lower decoding complexity.
Low density lattice codes (LDLCs) have been shown to approach the AWGN channel capacity and can be decoded by a message passing decoder. The messages passed between check nodes and variable nodes are probability density functions, which are approximated by Gaussian mixtures in existing LDLC decoders. However, in the best-known M-Gaussian decoder, the Gaussian mixtures for approximating variable node messages still contain unnecessary Gaussian components, resulting in exponential decoding complexity in the LDLC degree d. In this paper, an efficient LDLC decoder is proposed from the lattice viewpoint, which only finds out important Gaussian components for approximating the variable node messages. The decoding complexity for the proposed decoder is linear in d. Numerical results show that the proposed decoder can achieve significant complexity saving without degrading the performance compared with the M-Gaussian decoder. In particular, the runtime saving is 75.3% when the code length is 10000 and d is 7.
Low-density lattice codes (LDLCs) achieve near-capacity performance on additive white Gaussian noise (AWGN) channels. TheM-Gaussian decoder is the state-of-the-art message passing decoder for LDLCs in terms of the error performance. However, this decoder has complexityO(Md−1)with messages represented by Gaussian mixtures, wheredis the degree of an LDLC andMis the number of Gaussian functions for approximating each check node message. In this paper, we establish the correspondence between Gaussian functions for approximating a variable node message and points of a certain lattice. Based on this lattice viewpoint, the problem of approximating a variable node message is formulated as a lattice point enumeration (LPE) problem. Then, an LPE decoder with linear complexityO(d)is proposed. Our simulation results validate that the LPE decoder achieves almost the same error performance as theM-Gaussian decoder.
The recent work of Sommer, Feder and Shalvi presented a new family of codes called low density lattice codes (LDLC) that can be decoded efficiently and approach the capacity of the AWGN channel. A linear time iterative decoding scheme which is based on a message-passing formulation on a factor graph is given. In the current work we report our theoretical findings regarding the relation between the LDLC decoder and belief propagation. We show that the LDLC decoder is an instance of non-parametric belief propagation and further connect it to the Gaussian belief propagation algorithm. Our new results enable borrowing knowledge from the non-parametric and Gaussian belief propagation domains into the LDLC domain. Specifically, we give more general convergence conditions for convergence of the LDLC decoder (under the same assumptions of the original LDLC convergence analysis). We discuss how to extend the LDLC decoder from Latin square to full rank, non-square matrices. We propose an efficient construction of sparse generator matrix and its matching decoder. We report preliminary experimental results which show our decoder has comparable symbol to error rate compared to the original LDLC decoder.
In order to improve the error correction performance of Low-Density Parity-Check (LDPC) codes, In this paper, we propose a Reliability Profile (RP) Based Low-Complexity Dynamic Schedule, called RPD. In terms of dynamic scheduling, the new RPD method is distinct from the existing residual belief propagation (RBP) and its variations, since RPD is based on residual criterion. Reliability divides nodes message into two categories: reliable and unreliable. By using as many messages as possible from the latest available current iteration instead of the previous iteration to update unreliable messages multiple times to speed up the convergence speed and increase the total number of updates of effective nodes message, so as to improve the Bit Error Rate (BER) performance. By not updating the reliable message, the number of ineffective nodes message updates is reduced, thereby reducing the decoding complexity. Besides, the more iterations increase, the fewer calculations of these reliable nodes. Moreover, based on reliability profile, RPD has an advantage over RBP for dynamic scheduling in that the former only needs integer operations, while the latter requires float operations. Therefore, the RPD algorithm not only accelerates the convergence speed of LDPC decoding and but also improves the BER performance while reducing the complexity.The analysis and simulation results show that the RPD strategy not only retains the fast-convergence advantage of RBP, but also has a better convergence BER performance compared to that of node-wise residual belief propagation (NW RBP). Furthermore, the simulation results show that the RPD can significantly improve the convergence speed of protograph LDPC decoding.