Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Information Theory Workshop (ITW)

Message variance convergence condition for generalizations of LDLC lattices

Brian M. Kurkoski, Ricardo Antonio Parrao Hernandez

Published Nov 1, 2014• 0 citations
Publisher

Abstract

For low-density lattice codes (LDLC), there is a condition for convergence of the messages under belief-propagation decoding, specifically a condition on the inverse generator matrix for the variances in the Gaussian mixture to converge. It offers guidance on the design of Latin square LDLC lattices. This paper revisits this condition, and then describes two other constructions, a modified Latin square construction and a triangular array code construction. We illustrate how the condition can be applied, demonstrating the validity of the condition for more general LDLC lattices.

DOI
10.1109/itw.2014.6970784

Related papers

A low density lattice decoder via non-parametric belief propagation

Danny Bickson, Alexander Ihler, Harel Avissar +1 more

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.

arXiv:0901.3197•Allerton Conference on Communication, Control, and Computing•Sep 1, 2009•5 citations

A Low Density Lattice Decoder via Non-parametric Belief Propagation

Danny Bickson, Alexander Ihler, Harel Avissar +1 more

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

•Jan 1, 2009•18 citations

Fast Decoding of Low Density Lattice Codes

Shuiyin Liu, Yi Hong, Emanuele Viterbo +2 more

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(2^d)$ 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.

arXiv:1806.05524•Jun 14, 2018•1 citation

Efficient Decoder Design for Low-Density Lattice Codes From the Lattice Viewpoint

Xuebo Wang, Wai Ho Mow

Low-density lattice codes (LDLCs) achieve near-capacity performance on additive white Gaussian noise (AWGN) channels. The$M$-Gaussian decoder is the state-of-the-art message passing decoder for LDLCs in terms of the error performance. However, this decoder has complexity$O(M^{d-1})$with messages represented by Gaussian mixtures, where$d$is the degree of an LDLC and$M$is 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 complexity$O(d)$is proposed. Our simulation results validate that the LPE decoder achieves almost the same error performance as the$M$-Gaussian decoder.

IEEE Open Journal of the Communications Society•Jan 1, 2023•0 citations

Efficient LDLC Decoder Design from the Lattice Viewpoint

Xuebo Wang, Wai Ho Mow

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.

Globecom•Dec 1, 2019•3 citations

Low-Density Lattice Codes Based on Golomb Rulers

Anna A. Fominykh, Daria Ustinova, Pavel S. Rybin +1 more

Low-density lattice codes (LDLC) are a new type of lattice codes that can be decoded effectively and achieve performance levels near the capacity of the additive white Gaussian noise (AWGN) channel. Earlier designs of LDLC, such as those utilizing Latin squares, relied on high-complexity computer searches to eliminate short cycles. The proposed code construction offers a systematic representation and inherently avoids these issues. This study presents a design for LDLC that is based on Golomb rulers. This approach is deterministic and results in a parity-check matrix that is free of short cycles. In all scenarios examined, the LDLC built on Golomb rulers demonstrated superior frame error rate performance compared to those based on Latin squares. For instance, there is a 1.5 dB improvement observed for a dimension of$\mathrm{n}=73$.

International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON)•Sep 30, 2024•0 citations
For low-density lattice codes (LDLC), there is a condition for convergence of the messages under belief-propagation decoding, specifically a condition on the inverse generator matrix for the variances in the Gaussian mixture to converge. It offers guidance on the design of Latin square LDLC lattices. This paper revisits this condition, and then describes two other constructions, a modified Latin square construction and a triangular array code construction. We illustrate how the condition can be applied, demonstrating the validity of the condition for more general LDLC lattices.
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.
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. I.
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)O(2^d)O(2d) operations at each variable node, where ddd is the degree of LDLC. It means that existing decoders are very slow for long codes with large ddd. 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)O(d)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) achieve near-capacity performance on additive white Gaussian noise (AWGN) channels. TheMMM-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)O(M^{d-1})O(Md−1)with messages represented by Gaussian mixtures, wheredddis the degree of an LDLC andMMMis 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)O(d)O(d)is proposed. Our simulation results validate that the LPE decoder achieves almost the same error performance as theMMM-Gaussian decoder.
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 (LDLC) are a new type of lattice codes that can be decoded effectively and achieve performance levels near the capacity of the additive white Gaussian noise (AWGN) channel. Earlier designs of LDLC, such as those utilizing Latin squares, relied on high-complexity computer searches to eliminate short cycles. The proposed code construction offers a systematic representation and inherently avoids these issues. This study presents a design for LDLC that is based on Golomb rulers. This approach is deterministic and results in a parity-check matrix that is free of short cycles. In all scenarios examined, the LDLC built on Golomb rulers demonstrated superior frame error rate performance compared to those based on Latin squares. For instance, there is a 1.5 dB improvement observed for a dimension ofn=73\mathrm{n}=73n=73.