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

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

Construction of structured low density lattice codes based on finite fields

Jiayun Li, Shu‐Tao Xia, Xinji Liu

Finite fields were successfully used to construct algebraic low-density parity-check (LDPC) codes, especially Quasi-Cyclic LDPC codes. These LDPC codes with large minimum distances have lower error floor, linear complexity of encoding and are more practical for hard-decision algebraic decoding. In this paper, we show that finite fields can also be successfully used to construct algebraic low-density lattice codes (LDLC), denoted by structured LDLC. A general framework to construct algebraic LDLC is presented. LDLC constructed by this general framework have comparable performance to the corresponding random codes over addition white Gaussian noise (AWGN) channel with iterative soft-decision decoding in terms of symbol-error probability. Furthermore, the general framework is extended to complex low-density lattice codes (CLDLC) and results in algebraic CLDLC which perform very well for small dimensions.

IEEE Symposium on Computers and Communications (ISCC)•Jul 1, 2015•0 citations

Quantum low-density lattice codes

Timo Hillmann, Jens Eisert, Francesco Arzani

Gottesman-Kitaev-Preskill (GKP) codes provide a family of promising schemes for encoding discrete quantum information (qudits) into infinite-dimensional bosonic modes based on mathematical lattices. While such codes, when concatenated with discrete-variable codes, are relatively well studied, the construction and decoding of native GKP codes has largely remained open due to the computationally hard problems encountered. To address this challenge, we advocate a strategy of co-designing the decoder and the quantum error-correcting code itself by constructing lattices for which decoding is feasible: The requirement of efficient decoding effectively determines the quantum error-correcting code. This construction is built on classical low-density lattice codes (LDLCs), a lattice analogue of low-density parity-check codes, here lifted to families of GKP codes. Concretely, we introduce quantum versions of classical, randomly constructed LDLCs. We show that after suitable dimensionality reduction these codes have code properties comparable to or better than concatenated GKP-surface codes of equal number of modes. However, the GKP-LDLCs constructed here do not have a strictly sparse parity check matrix, which motivates our study of the performance of natively analog message-passing decoders originally developed for LDLCs when applied to concatenated GKP-LDPC codes. We show that the fully analog, linear-time decoder achieves performances close to state-of-the-art hybrid qubit-analog decoders. To facilitate future research on the structure and performance of general GKP codes, the relevant source code will be released in open-source Julia packages LatticeDecoder.jl and SymplecticGKP.jl.

quant-pharXiv:2609.03021•Sep 4, 2026•1 citation

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•18 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.
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.
Finite fields were successfully used to construct algebraic low-density parity-check (LDPC) codes, especially Quasi-Cyclic LDPC codes. These LDPC codes with large minimum distances have lower error floor, linear complexity of encoding and are more practical for hard-decision algebraic decoding. In this paper, we show that finite fields can also be successfully used to construct algebraic low-density lattice codes (LDLC), denoted by structured LDLC. A general framework to construct algebraic LDLC is presented. LDLC constructed by this general framework have comparable performance to the corresponding random codes over addition white Gaussian noise (AWGN) channel with iterative soft-decision decoding in terms of symbol-error probability. Furthermore, the general framework is extended to complex low-density lattice codes (CLDLC) and results in algebraic CLDLC which perform very well for small dimensions.
Gottesman-Kitaev-Preskill (GKP) codes provide a family of promising schemes for encoding discrete quantum information (qudits) into infinite-dimensional bosonic modes based on mathematical lattices. While such codes, when concatenated with discrete-variable codes, are relatively well studied, the construction and decoding of native GKP codes has largely remained open due to the computationally hard problems encountered. To address this challenge, we advocate a strategy of co-designing the decoder and the quantum error-correcting code itself by constructing lattices for which decoding is feasible: The requirement of efficient decoding effectively determines the quantum error-correcting code. This construction is built on classical low-density lattice codes (LDLCs), a lattice analogue of low-density parity-check codes, here lifted to families of GKP codes. Concretely, we introduce quantum versions of classical, randomly constructed LDLCs. We show that after suitable dimensionality reduction these codes have code properties comparable to or better than concatenated GKP-surface codes of equal number of modes. However, the GKP-LDLCs constructed here do not have a strictly sparse parity check matrix, which motivates our study of the performance of natively analog message-passing decoders originally developed for LDLCs when applied to concatenated GKP-LDPC codes. We show that the fully analog, linear-time decoder achieves performances close to state-of-the-art hybrid qubit-analog decoders. To facilitate future research on the structure and performance of general GKP codes, the relevant source code will be released in open-source Julia packages LatticeDecoder.jl and SymplecticGKP.jl.
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.