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 International Symposium on Information Theory (ISIT)

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

Brian M. Kurkoski, Kazuhiko Yamaguchi, Kingo Kobayashi

Published Jun 1, 2009• 18 citations
Publisher

Abstract

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.

DOI
10.1109/isit.2009.5205680

Related papers

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

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

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

Noise Thresholds for Discrete LDPC Decoding Mappings

Brian M. Kurkoski, Kazuhiko Yamaguchi, Kingo Kobayashi

For decoding low-density parity-check (LDPC) codes on discrete memoryless channels, a method to quantize messages and to find message-passing decoding functions for the variable and check nodes is developed. These are used to obtain noise thresholds by density evolution. The message-passing decoding alphabet is restricted to be discrete with a fixed maximum alphabet size. Discrete quantization is required to obtain this fixed alphabet size; a greedy algorithm which uses the mutual information between the code bit and message is presented. It is argued that using this message-passing decoding framework is more efficient for approaching channel capacity than simply quantizing the belief-propagation algorithm. This method is evaluated using regular LDPC codes on the binary symmetric channel. Using a maximum alphabet size of 16 (4 bits), noise thresholds close to those of belief propagation are obtained.

Globecom•Jan 1, 2008•49 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

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
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.
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.
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.
For decoding low-density parity-check (LDPC) codes on discrete memoryless channels, a method to quantize messages and to find message-passing decoding functions for the variable and check nodes is developed. These are used to obtain noise thresholds by density evolution. The message-passing decoding alphabet is restricted to be discrete with a fixed maximum alphabet size. Discrete quantization is required to obtain this fixed alphabet size; a greedy algorithm which uses the mutual information between the code bit and message is presented. It is argued that using this message-passing decoding framework is more efficient for approaching channel capacity than simply quantizing the belief-propagation algorithm. This method is evaluated using regular LDPC codes on the binary symmetric channel. Using a maximum alphabet size of 16 (4 bits), noise thresholds close to those of belief propagation are obtained.
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.
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.