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

Globecom

Noise Thresholds for Discrete LDPC Decoding Mappings

Brian M. Kurkoski, Kazuhiko Yamaguchi, Kingo Kobayashi

Published Jan 1, 2008• 49 citations
Publisher

Abstract

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.

DOI
10.1109/glocom.2008.ecp.214

Related papers

Density Evolution for GF(q) LDPC Codes Via Simplified Message-passing Sets

Brian M. Kurkoski, Kazuhiko Yamaguchi, Kingo Kobayashi

A message-passing decoder for GF(q) low-density parity-check codes is defined, which uses discrete messages from a subset of all possible binary vectors of length q. The proposed algorithm is a generalization to GF(q) of Richardson and Urbanke's decoding "Algorithm E" for binary codes. Density evolution requires a mapping between the probability distribution spaces for the channel, variable and check messages, and under the proposed algorithm, exact density evolution is possible. Symmetries in the message densities permit reduction in the size of the probability distribution space. Noise thresholds are obtained for LDPC codes on discrete memoryless channels, and as with Algorithm E, are remarkably close to noise thresholds under more complex belief propagation decoding.

Information Theory and Applications Workshop (ITA)•Jan 1, 2007•7 citations

Decoding LDPC Codes With Locally Maximum-Likelihood Binary Messages

Chris Winstead, Emmanuel Boutillon

A new low-complexity message passing algorithm is described for decoding low-density parity-check (LDPC) codes by exchanging binary messages. The algorithm computes the local maximum-likelihood binary message (LMLBM) at each symbol node, given the combination of local channel information and partial syndrome components from adjacent parity check nodes. When channel information is quantized, the locally ML messages are pre-computed and stored in a dynamic global lookup table. The proposed algorithm uses memoryless extrinsic messages so that density evolution thresholds can be directly computed. Thresholds are obtained for regular ensembles, predicting good performance on quantized binary-input additive white Gaussian noise (biAWGN) channels.

IEEE Communications Letters•Oct 30, 2014•2 citations

The capacity of low-density parity-check codes under message-passing decoding

Tom Richardson, Rudiger L. Urbanke

We present a general method for determining the capacity of low-density parity-check (LDPC) codes under message-passing decoding when used over any binary-input memoryless channel with discrete or continuous output alphabets. Transmitting at rates below this capacity, a randomly chosen element of the given ensemble will achieve an arbitrarily small target probability of error with a probability that approaches one exponentially fast in the length of the code. (By concatenating with an appropriate outer code one can achieve a probability of error that approaches zero exponentially fast in the length of the code with arbitrarily small loss in rate.) Conversely, transmitting at rates above this capacity the probability of error is bounded away from zero by a strictly positive constant which is independent of the length of the code and of the number of iterations performed. Our results are based on the observation that the concentration of the performance of the decoder around its average performance, as observed by Luby et al. in the case of a binary-symmetric channel and a binary message-passing algorithm, is a general phenomenon. For the particularly important case of belief-propagation decoders, we provide an effective algorithm to determine the corresponding capacity to any desired degree of accuracy. The ideas presented in this paper are broadly applicable and extensions of the general method to low-density parity-check codes over larger alphabets, turbo codes, and other concatenated coding schemes are outlined.

IEEE Transactions on Information Theory•Jan 1, 2001•3,034 citations

A differential binary message-passing LDPC decoder

Nastaran Mobini, A.H. Banihashemi, Saied Hemati

In this paper, we propose a binary message-passing algorithm for decoding low-density parity-check (LDPC) codes. The algorithm substantially improves the performance of purely hard-decision iterative algorithms with a small increase in the memory requirements and the computational complexity. We associate a reliability value to each nonzero element of the code's parity-check matrix, and differentially modify this value in each iteration based on the sum of the extrinsic binary messages from the check nodes. For the tested random and finitegeometry LDPC codes, the proposed algorithm can perform as close as about 1 dB and 0.5 dB to belief propagation (BP) at the error rates of interest, respectively. This is while, unlike BP, the algorithm does not require the estimation of channel signal to noise ratio. Low memory and computational requirements and binary message-passing make the proposed algorithm attractive for high-speed low-power applications.

IEEE Transactions on Communications•Sep 1, 2009•32 citations

Bounds on the Belief Propagation Threshold of Non-Binary LDPC Codes

Leonid Geller, David Burshtein

We consider low-density parity-check (LDPC) code ensembles over non-binary Galois fields when used for transmission over arbitrary discrete memoryless channels. Belief propagation decoding for these codes has been shown to achieve excellent results. However, computing the decoding threshold using density evolution is usually impractical, since one needs to propagate multi-dimensional probability distributions, and Monte Carlo simulations are required instead. By considering the evolution of the message Bhattacharyya parameter and the message expected value parameter, we derive a simple lower bound on the performance of the algorithm. This bound applies for both regular and irregular non-binary LDPC ensembles.

IEEE Transactions on Information Theory•Mar 9, 2016•6 citations

Optimum message mapping LDPC decoders derived from the sum-product algorithm

Jan Lewandowsky, Maximilian Stark, Gerhard Bauch

Starting from a discrete density evolution scheme originally introduced by Brian M. Kurkoski et al. which we improved by applying the Information Bottleneck method, we recently presented results on message passing decoders for Low Density Parity Check codes that have much lower complexity than state of the art decoders. In the decoders all node operations are replaced by discrete message mappings of unsigned integers what yields a great complexity reduction. Anyway the decoders perform very close to belief propagation decoding. New included simulation results prove that using a 4 bit integer architecture these decoders loose only 0.1 dB over Eb/No in comparison to an exact belief propagation decoder applied to the quantized output of a Gaussian channel. The most important contribution of this paper is the derivation of the message mapping decoders from the sum-product algorithm. Until now these decoders are assumed to not be linked to this algorithm. In order to reveal the hidden connection, we explain the decoding principle of the message mapping decoders in general factor graphs.

International Conference on Communications•May 1, 2016•12 citations
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 message-passing decoder for GF(q) low-density parity-check codes is defined, which uses discrete messages from a subset of all possible binary vectors of length q. The proposed algorithm is a generalization to GF(q) of Richardson and Urbanke's decoding "Algorithm E" for binary codes. Density evolution requires a mapping between the probability distribution spaces for the channel, variable and check messages, and under the proposed algorithm, exact density evolution is possible. Symmetries in the message densities permit reduction in the size of the probability distribution space. Noise thresholds are obtained for LDPC codes on discrete memoryless channels, and as with Algorithm E, are remarkably close to noise thresholds under more complex belief propagation decoding.
A new low-complexity message passing algorithm is described for decoding low-density parity-check (LDPC) codes by exchanging binary messages. The algorithm computes the local maximum-likelihood binary message (LMLBM) at each symbol node, given the combination of local channel information and partial syndrome components from adjacent parity check nodes. When channel information is quantized, the locally ML messages are pre-computed and stored in a dynamic global lookup table. The proposed algorithm uses memoryless extrinsic messages so that density evolution thresholds can be directly computed. Thresholds are obtained for regular ensembles, predicting good performance on quantized binary-input additive white Gaussian noise (biAWGN) channels.
We present a general method for determining the capacity of low-density parity-check (LDPC) codes under message-passing decoding when used over any binary-input memoryless channel with discrete or continuous output alphabets. Transmitting at rates below this capacity, a randomly chosen element of the given ensemble will achieve an arbitrarily small target probability of error with a probability that approaches one exponentially fast in the length of the code. (By concatenating with an appropriate outer code one can achieve a probability of error that approaches zero exponentially fast in the length of the code with arbitrarily small loss in rate.) Conversely, transmitting at rates above this capacity the probability of error is bounded away from zero by a strictly positive constant which is independent of the length of the code and of the number of iterations performed. Our results are based on the observation that the concentration of the performance of the decoder around its average performance, as observed by Luby et al. in the case of a binary-symmetric channel and a binary message-passing algorithm, is a general phenomenon. For the particularly important case of belief-propagation decoders, we provide an effective algorithm to determine the corresponding capacity to any desired degree of accuracy. The ideas presented in this paper are broadly applicable and extensions of the general method to low-density parity-check codes over larger alphabets, turbo codes, and other concatenated coding schemes are outlined.
In this paper, we propose a binary message-passing algorithm for decoding low-density parity-check (LDPC) codes. The algorithm substantially improves the performance of purely hard-decision iterative algorithms with a small increase in the memory requirements and the computational complexity. We associate a reliability value to each nonzero element of the code's parity-check matrix, and differentially modify this value in each iteration based on the sum of the extrinsic binary messages from the check nodes. For the tested random and finitegeometry LDPC codes, the proposed algorithm can perform as close as about 1 dB and 0.5 dB to belief propagation (BP) at the error rates of interest, respectively. This is while, unlike BP, the algorithm does not require the estimation of channel signal to noise ratio. Low memory and computational requirements and binary message-passing make the proposed algorithm attractive for high-speed low-power applications.
We consider low-density parity-check (LDPC) code ensembles over non-binary Galois fields when used for transmission over arbitrary discrete memoryless channels. Belief propagation decoding for these codes has been shown to achieve excellent results. However, computing the decoding threshold using density evolution is usually impractical, since one needs to propagate multi-dimensional probability distributions, and Monte Carlo simulations are required instead. By considering the evolution of the message Bhattacharyya parameter and the message expected value parameter, we derive a simple lower bound on the performance of the algorithm. This bound applies for both regular and irregular non-binary LDPC ensembles.
Starting from a discrete density evolution scheme originally introduced by Brian M. Kurkoski et al. which we improved by applying the Information Bottleneck method, we recently presented results on message passing decoders for Low Density Parity Check codes that have much lower complexity than state of the art decoders. In the decoders all node operations are replaced by discrete message mappings of unsigned integers what yields a great complexity reduction. Anyway the decoders perform very close to belief propagation decoding. New included simulation results prove that using a 4 bit integer architecture these decoders loose only 0.1 dB over Eb/No in comparison to an exact belief propagation decoder applied to the quantized output of a Gaussian channel. The most important contribution of this paper is the derivation of the message mapping decoders from the sum-product algorithm. Until now these decoders are assumed to not be linked to this algorithm. In order to reveal the hidden connection, we explain the decoding principle of the message mapping decoders in general factor graphs.