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 Communications Letters

Decoding LDPC Codes With Locally Maximum-Likelihood Binary Messages

Chris Winstead, Emmanuel Boutillon

Published Oct 30, 2014• 2 citations
Publisher

Abstract

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.

DOI
10.1109/lcomm.2014.2366095

Related papers

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•51 citations

Symbol Message Passing Decoding of LDPC Codes for Orthogonal Modulations

Emna Ben Yacoub, Balázs Matuz

A simple decoder for q-ary low-density parity-check codes is studied, termed symbol message passing. The decoder passes hard decisions from a q-ary alphabet. For orthogonal modulations over the additive white Gaussian channel for which the modulation order and the field order q are equal, it is shown that the extrinsic messages can be modelled as observations of a q-ary symmetric channel, allowing to work out density evolution equations. A stability analysis is provided which emphasizes the influence of degree-3 variable nodes. Simulation results show performance gains for increasing q w.r.t. binary low-density parity-check codes with bit-interleaved coded modulation, and potential savings in decoding complexity.

International Symposium on Turbo Codes and Iterative Information Processing•Aug 30, 2021•1 citation

A Differential Binary Message-Passing LDPC Decoder

Nastaran Mobini, Amir 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 finite-geometry LDPC codes, the proposed algorithm can achieve performance as close as 1.3 dB and 0.7 dB to that of 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.

Globecom•Nov 1, 2007•16 citations

Symbol Message Passing Decoding of Nonbinary Low-Density Parity-Check Codes

Francisco Lázaro, Alexandre Graell i Amat, Gianluigi Liva +1 more

We present a novel decoding algorithm for q-ary low-density parity- check codes, termed symbol message passing. The proposed algorithm can be seen as a generalization of Gallager B and the binary message passing algorithm by Lechner et al. to q-ary codes. We derive density evolution equations for the q-ary symmetric channel, compute thresholds for a number of regular low-density parity-check code ensembles, and verify those by Monte Carlo simulations of long channel codes. The proposed algorithm shows performance advantages with respect to an algorithm of comparable complexity from the literature.

arXiv:1906.02537•Globecom•Dec 1, 2019•1 citation

Symbol Message Passing Decoding of Nonbinary Low-Density Parity-Check Codes

Francisco Lázaro, Alexandre Graell i Amat, Gianluigi Liva +1 more

We present a novel decoding algorithm for q-ary low-density parity- check codes, termed symbol message passing. The proposed algorithm can be seen as a generalization of Gallager B and the binary message passing algorithm by Lechner et al. to q-ary codes. We derive density evolution equations for the q-ary symmetric channel, compute thresholds for a number of regular low-density parity-check code ensembles, and verify those by Monte Carlo simulations of long channel codes. The proposed algorithm shows performance advantages with respect to an algorithm of comparable complexity from the literature.

•Jan 1, 2019•9 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•31 citations
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.
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 simple decoder for q-ary low-density parity-check codes is studied, termed symbol message passing. The decoder passes hard decisions from a q-ary alphabet. For orthogonal modulations over the additive white Gaussian channel for which the modulation order and the field order q are equal, it is shown that the extrinsic messages can be modelled as observations of a q-ary symmetric channel, allowing to work out density evolution equations. A stability analysis is provided which emphasizes the influence of degree-3 variable nodes. Simulation results show performance gains for increasing q w.r.t. binary low-density parity-check codes with bit-interleaved coded modulation, and potential savings in decoding complexity.
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 finite-geometry LDPC codes, the proposed algorithm can achieve performance as close as 1.3 dB and 0.7 dB to that of 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 present a novel decoding algorithm for q-ary low-density parity- check codes, termed symbol message passing. The proposed algorithm can be seen as a generalization of Gallager B and the binary message passing algorithm by Lechner et al. to q-ary codes. We derive density evolution equations for the q-ary symmetric channel, compute thresholds for a number of regular low-density parity-check code ensembles, and verify those by Monte Carlo simulations of long channel codes. The proposed algorithm shows performance advantages with respect to an algorithm of comparable complexity from the literature.
We present a novel decoding algorithm for q-ary low-density parity- check codes, termed symbol message passing. The proposed algorithm can be seen as a generalization of Gallager B and the binary message passing algorithm by Lechner et al. to q-ary codes. We derive density evolution equations for the q-ary symmetric channel, compute thresholds for a number of regular low-density parity-check code ensembles, and verify those by Monte Carlo simulations of long channel codes. The proposed algorithm shows performance advantages with respect to an algorithm of comparable complexity from the literature.
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.