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 Convention of Electrical and Electronics Engineers in Israel

Efficient decoding of Low Density Lattice Codes

Yair Yona, Meir Feder

Published Mar 1, 2008• 2 citations
Publisher

Abstract

A New efficient algorithm for implementing the Low Density Lattice Codes belief propagation decoder is presented. In the new algorithm the messages passed over the edges are represented by Gaussian parameters lists, and the decoding algorithm uses the low density lattice codes propagation properties in order to group lists efficiently according to a new criteria. The new algorithm attains the same performance as the quantized decoder, proposed in previous work. The new algorithm advantage in comparison to previous works is its storage requirements and its relatively low computational complexity.

DOI
10.1109/eeei.2008.4736576

Related papers

Efficient parametric decoder of low density lattice codes

Yair Yona, Meir Feder

A new efficient parametric algorithm for implementing the low density lattice codes belief propagation decoder is presented. In the new algorithm the messages passed over the edges are represented by Gaussian parameters lists, and the decoding algorithm uses the low density lattice codes propagation properties in order to group lists efficiently according to a new criteria. The new algorithm attains essentially the same performance as the quantized decoder, proposed in previous work. The new algorithm advantage in comparison to previous works is its smaller storage requirements and its relatively low computational complexity.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2009•48 citations

Single-Gaussian messages and noise thresholds for decoding low-density lattice codes

Brian M. Kurkoski, Kazuhiko Yamaguchi, Kingo Kobayashi

A new method for decoding low-density lattice codes is given, wherein the belief-propagation decoder messages are single Gaussian functions. Since the message can be represented by two numbers, a mean and a variance, the complexity of this decoder is lower than previous decoders, which either quantized the mixture, or used a mixture of Gaussians. The computational complexity at the check node is also lower. The performance of various code designs, under single-Gaussian decoding, is evaluated by noise thresholds. In particular, the proposed decoding algorithm has noise threshold within 0.1 dB of the quantized-message decoder, which is considerably more complex.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2009•18 citations

Belief-Propagation Decoding of Lattices Using Gaussian Mixtures

Brian M. Kurkoski, Justin Dauwels

A belief-propagation decoder for low-density lattice codes is given which represents messages explicitly as a mixture of Gaussians functions. The key component is an algorithm for approximating a mixture of several Gaussians with another mixture with a smaller number of Gaussians. This Gaussian mixture reduction algorithm iteratively reduces the number of Gaussians by minimizing the distance between the original mixture and an approximation with one fewer Gaussians. Error rates and noise thresholds of this decoder are compared with those for the previously-proposed decoder which discretely quantizes the messages. The error rates are indistinguishable for dimension 1000 and 10000 lattices, and the Gaussian-mixture decoder has a 0.2 dB loss for dimension 100 lattices. The Gaussian-mixture decoder has a loss of about 0.03 dB in the noise threshold, which is evaluated via Monte Carlo density evolution. Further, the Gaussian-mixture decoder uses far less storage for the messages.

arXiv:0904.4741•Apr 30, 2009•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

Reduced complexity iterative decoding of low-density parity check codes based on belief propagation

M.P.C. Fossorier, Miodrag J. Mihaljević, Hirotaka Imai

Two simplified versions of the belief propagation algorithm for fast iterative decoding of low-density parity check codes on the additive white Gaussian noise channel are proposed. Both versions are implemented with real additions only, which greatly simplifies the decoding complexity of belief propagation in which products of probabilities have to be computed. Also, these two algorithms do not require any knowledge about the channel characteristics. Both algorithms yield a good performance-complexity trade-off and can be efficiently implemented in software as well as in hardware, with possibly quantized received values.

IEEE Transactions on Communications•May 1, 1999•1,065 citations

Fast quantized belief propagation algorithm for iteratively decoding LDPC codes

Xinmei Wang

A fast quantized belief propagation algorithm is proposed for decoding low-density parity-check(LDPC) codes. With operations performed by addressing tables, the proposed algorithm takes as operands the indices of labels rather than the quantization levels. The intermediate calculations have been contained in operation tables with much higher precision. The required storage can be significantly reduced by applying the symmetry property while keeping low time complexity. Without the increase in time complexity, it is convenient to realize the decoding with uniform quantization or any nonuniform quantizations that is designed for improving the performance. The time-varying decoder also becomes possible. This algorithm makes it possible to apply LDPC codes to practical systems or to realize fast simulation systems. Some simulation results are also given. The 6?bit logarithmic quantization results in gains of about 0.2?dB relative to the uniform one, approaching to the continuous decoding at low signal-to-noise ratios (SNRs) and yielding a loss of about 0.2?dB at high SNRs. Proper quantization of high order can achieve the performance of continuous decoding, and it may be superior to continuous decoding at high SNRs.

Jounal of Xidian University•Jan 1, 2002•0 citations
A New efficient algorithm for implementing the Low Density Lattice Codes belief propagation decoder is presented. In the new algorithm the messages passed over the edges are represented by Gaussian parameters lists, and the decoding algorithm uses the low density lattice codes propagation properties in order to group lists efficiently according to a new criteria. The new algorithm attains the same performance as the quantized decoder, proposed in previous work. The new algorithm advantage in comparison to previous works is its storage requirements and its relatively low computational complexity.
A new efficient parametric algorithm for implementing the low density lattice codes belief propagation decoder is presented. In the new algorithm the messages passed over the edges are represented by Gaussian parameters lists, and the decoding algorithm uses the low density lattice codes propagation properties in order to group lists efficiently according to a new criteria. The new algorithm attains essentially the same performance as the quantized decoder, proposed in previous work. The new algorithm advantage in comparison to previous works is its smaller storage requirements and its relatively low computational complexity.
A new method for decoding low-density lattice codes is given, wherein the belief-propagation decoder messages are single Gaussian functions. Since the message can be represented by two numbers, a mean and a variance, the complexity of this decoder is lower than previous decoders, which either quantized the mixture, or used a mixture of Gaussians. The computational complexity at the check node is also lower. The performance of various code designs, under single-Gaussian decoding, is evaluated by noise thresholds. In particular, the proposed decoding algorithm has noise threshold within 0.1 dB of the quantized-message decoder, which is considerably more complex.
A belief-propagation decoder for low-density lattice codes is given which represents messages explicitly as a mixture of Gaussians functions. The key component is an algorithm for approximating a mixture of several Gaussians with another mixture with a smaller number of Gaussians. This Gaussian mixture reduction algorithm iteratively reduces the number of Gaussians by minimizing the distance between the original mixture and an approximation with one fewer Gaussians. Error rates and noise thresholds of this decoder are compared with those for the previously-proposed decoder which discretely quantizes the messages. The error rates are indistinguishable for dimension 1000 and 10000 lattices, and the Gaussian-mixture decoder has a 0.2 dB loss for dimension 100 lattices. The Gaussian-mixture decoder has a loss of about 0.03 dB in the noise threshold, which is evaluated via Monte Carlo density evolution. Further, the Gaussian-mixture decoder uses far less storage for the messages.
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.
Two simplified versions of the belief propagation algorithm for fast iterative decoding of low-density parity check codes on the additive white Gaussian noise channel are proposed. Both versions are implemented with real additions only, which greatly simplifies the decoding complexity of belief propagation in which products of probabilities have to be computed. Also, these two algorithms do not require any knowledge about the channel characteristics. Both algorithms yield a good performance-complexity trade-off and can be efficiently implemented in software as well as in hardware, with possibly quantized received values.
A fast quantized belief propagation algorithm is proposed for decoding low-density parity-check(LDPC) codes. With operations performed by addressing tables, the proposed algorithm takes as operands the indices of labels rather than the quantization levels. The intermediate calculations have been contained in operation tables with much higher precision. The required storage can be significantly reduced by applying the symmetry property while keeping low time complexity. Without the increase in time complexity, it is convenient to realize the decoding with uniform quantization or any nonuniform quantizations that is designed for improving the performance. The time-varying decoder also becomes possible. This algorithm makes it possible to apply LDPC codes to practical systems or to realize fast simulation systems. Some simulation results are also given. The 6?bit logarithmic quantization results in gains of about 0.2?dB relative to the uniform one, approaching to the continuous decoding at low signal-to-noise ratios (SNRs) and yielding a loss of about 0.2?dB at high SNRs. Proper quantization of high order can achieve the performance of continuous decoding, and it may be superior to continuous decoding at high SNRs.