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

arXiv:0904.4741

Belief-Propagation Decoding of Lattices Using Gaussian Mixtures

Brian M. Kurkoski, Justin Dauwels

Published Apr 30, 2009• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.0904.4741

Related papers

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

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

Noisy belief propagation decoder

Chu-Hsiang Huang, Yao Li, Lara Dolecek

This paper analyzes the fundamental performance limits of an LDPC Belief Propagation (BP) decoder implemented on noisy hardware and proposes a robust decoder implementation to improve the resilience to hardware errors. Assuming that the effects of hardware noise in various computational units, i.e., variable nodes and check nodes, can be approximated by Gaussian noise, we develop a Gaussian approximate density evolution for noisy BP decoders. By the Gaussian approximate density evolution, we find that zero residual error rate is achievable for noisy BP decoders as long as the message representations are of arbitrarily high precision. Noisy BP decoding thresholds are then derived for various regular LDPC codes. These decoding thresholds determine maximum allowable communication and computation noise for reliable communication. Next, we propose an averaging BP decoder implementation by averaging over the messages in all up-to-date iterations to cancel out the computation noise. Simulation results demonstrate that on noisy hardware, the averaging BP decoder significantly reduces the residual error rates when compared to the nominal BP decoder.

Asilomar Conference on Signals, Systems and Computers (ACSSC)•Nov 1, 2014•3 citations

Efficient decoding of Low Density Lattice Codes

Yair Yona, Meir Feder

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.

IEEE Convention of Electrical and Electronics Engineers in Israel•Mar 1, 2008•2 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

Analysis of belief-propagation decoding of LDPC codes over the biAWGN channel using improved Gaussian approximation based on the mutual information measure

E. Sharon

Summary form only given. The capacity of the message-passing decoder for LDPC codes can be computed by the density evolution algorithm by iteratively computing message densities. The infinite-dimensional problem of iteratively calculating the message densities in the case of the binary input AWGN channel and the belief propagation decoder can be simplified to a one-dimensional problem by using a Gaussian approximation. By assuming Gaussian densities the density evolution simplifies to updating means of Gaussian densities. An improved Gaussian approximation algorithm is suggested for computing the capacity of the BP decoder based on the mutual information measure. An analytical method for computing the mutual information of a transmitted bit with the message corresponding to it is proposed. Using this method we can approximate the non-Gaussian message by a Gaussian message that has the same mutual information with the transmitted bit. Computationally, the algorithm is similar to the Gaussian approximation algorithm proposed in Chung (2001). For various regular LDPC codes that were examined, the algorithm computed threshold values within 0.01dB or less from the exact threshold which is an improvement over the Gaussian approximation. Furthermore, additional insight on the convergence process can be gained from EXIT charts that can be derived from the algorithm. This can assist in designing better irregular LDPC codes.

IEEE Convention of Electrical and Electronics Engineers in Israel•Jun 26, 2003•4 citations
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.
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 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.
This paper analyzes the fundamental performance limits of an LDPC Belief Propagation (BP) decoder implemented on noisy hardware and proposes a robust decoder implementation to improve the resilience to hardware errors. Assuming that the effects of hardware noise in various computational units, i.e., variable nodes and check nodes, can be approximated by Gaussian noise, we develop a Gaussian approximate density evolution for noisy BP decoders. By the Gaussian approximate density evolution, we find that zero residual error rate is achievable for noisy BP decoders as long as the message representations are of arbitrarily high precision. Noisy BP decoding thresholds are then derived for various regular LDPC codes. These decoding thresholds determine maximum allowable communication and computation noise for reliable communication. Next, we propose an averaging BP decoder implementation by averaging over the messages in all up-to-date iterations to cancel out the computation noise. Simulation results demonstrate that on noisy hardware, the averaging BP decoder significantly reduces the residual error rates when compared to the nominal BP decoder.
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.
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.
Summary form only given. The capacity of the message-passing decoder for LDPC codes can be computed by the density evolution algorithm by iteratively computing message densities. The infinite-dimensional problem of iteratively calculating the message densities in the case of the binary input AWGN channel and the belief propagation decoder can be simplified to a one-dimensional problem by using a Gaussian approximation. By assuming Gaussian densities the density evolution simplifies to updating means of Gaussian densities. An improved Gaussian approximation algorithm is suggested for computing the capacity of the BP decoder based on the mutual information measure. An analytical method for computing the mutual information of a transmitted bit with the message corresponding to it is proposed. Using this method we can approximate the non-Gaussian message by a Gaussian message that has the same mutual information with the transmitted bit. Computationally, the algorithm is similar to the Gaussian approximation algorithm proposed in Chung (2001). For various regular LDPC codes that were examined, the algorithm computed threshold values within 0.01dB or less from the exact threshold which is an improvement over the Gaussian approximation. Furthermore, additional insight on the convergence process can be gained from EXIT charts that can be derived from the algorithm. This can assist in designing better irregular LDPC codes.