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

International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON)

Low-Density Lattice Codes Based on Golomb Rulers

Anna A. Fominykh, Daria Ustinova, Pavel S. Rybin, Alexey Frolov

Published Sep 30, 2024• 0 citations
Publisher

Abstract

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

DOI
10.1109/sibircon63777.2024.10758537

Related papers

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

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

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

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

On the Nested Family of LDPC Codes Based on Golomb Rulers

Fedor I. Ivanov, Pavel S. Rybin

In this paper we present a new ensemble of Low- Density Parity-Check codes (LDPC Codes) based on modular Golomb rulers and permutation matrices. We suggest a designing rule for these codes that allows obtaining a nested family of LDPC codes with wide range of rates from one matrix of lowest rate code. Moreover, the regular way that we apply to construct our codes allows describing parity-check matrices with minimal number of parameters. The simulation results in the case of transmission via AWGN channel with QAM-4 modulation are presented.

International Conference on Engineering and Telecommunication (EnT)•Nov 1, 2017•2 citations

Multilevel LDPC Lattices With Efficient Encoding and Decoding and a Generalization of Construction $\text{D}'$

Paulo Ricardo Branco da Silva, Danilo Silva

Lattice codes are elegant and powerful structures that not only achieve the capacity of the additive white Gaussian noise (AWGN) channel but are also a key ingredient to many multiterminal schemes that exploit linearity properties. However, constructing lattice codes that can realize these benefits with low complexity is still a challenging problem. In this paper, efficient encoding and decoding algorithms are proposed for multilevel binary low-density parity-check (LDPC) lattices constructed via Construction D' whose complexity is linear in the total number of coded bits. Moreover, a generalization of Construction D' is proposed, which relaxes some of the nesting constraints on the parity-check matrices of the component codes, leading to a simpler and improved design. Based on this construction, low-complexity multilevel LDPC lattices are designed whose performance under multistage decoding is comparable to that of polar lattices and close to that of low-density lattice codes on the power-unconstrained AWGN channel.

arXiv:1712.08201•IEEE Transactions on Information Theory•Nov 23, 2018•20 citations
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.
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.
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.
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.
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.
In this paper we present a new ensemble of Low- Density Parity-Check codes (LDPC Codes) based on modular Golomb rulers and permutation matrices. We suggest a designing rule for these codes that allows obtaining a nested family of LDPC codes with wide range of rates from one matrix of lowest rate code. Moreover, the regular way that we apply to construct our codes allows describing parity-check matrices with minimal number of parameters. The simulation results in the case of transmission via AWGN channel with QAM-4 modulation are presented.
Multilevel LDPC Lattices With Efficient Encoding and Decoding and a Generalization of Construction D′\text{D}'D′
Lattice codes are elegant and powerful structures that not only achieve the capacity of the additive white Gaussian noise (AWGN) channel but are also a key ingredient to many multiterminal schemes that exploit linearity properties. However, constructing lattice codes that can realize these benefits with low complexity is still a challenging problem. In this paper, efficient encoding and decoding algorithms are proposed for multilevel binary low-density parity-check (LDPC) lattices constructed via Construction D' whose complexity is linear in the total number of coded bits. Moreover, a generalization of Construction D' is proposed, which relaxes some of the nesting constraints on the parity-check matrices of the component codes, leading to a simpler and improved design. Based on this construction, low-complexity multilevel LDPC lattices are designed whose performance under multistage decoding is comparable to that of polar lattices and close to that of low-density lattice codes on the power-unconstrained AWGN channel.