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 Transactions on Information Theory

Mean field and mixed mean field iterative decoding of low-density parity-check codes

Juntan Zhang, M.P.C. Fossorier

Published Jul 1, 2006• 8 citations
Publisher

Abstract

In this paper, the mean field (MF) and mixed mean field (MMF) algorithms for decoding low-density parity-check (LDPC) codes are considered. The MF principle is well established in statistical physics and artificial intelligence. Instead of using a single completely factorized approximated distribution as in the MF approach, the mixed MF algorithm forms a weighted average of several MF distributions as an approximation of the true posterior probability distribution. The MF decoding algorithm for linear block codes is derived and shown to be an approximation of the a posteriori probability (APP) decoding algorithm. The MF approach is then developed in the context of iterative decoding and presented as an approximation of the popular belief propagation decoding method. These results are extended to iterative decoding with the MMF algorithm. Simulation results show that the MF and MMF decoding algorithms yield a good performance-complexity tradeoff, especially when employed for decoding LDPC codes based on finite geometries.

DOI
10.1109/tit.2006.876238

Related papers

Iterative Linear Programming Decoding of Nonbinary LDPC Codes With Linear Complexity

Dina Goldin, David Burshtein

The problem of low-complexity linear programming (LP) decoding of nonbinary low-density parity-check (LDPC) codes is considered, and an iterative LP decoding algorithm is presented. Results that were previously derived for binary LDPC codes are extended to the nonbinary case. Both simple and generalized nonbinary LDPC codes are considered. It is shown how the algorithm can be implemented efficiently using a finite-field fast Fourier transform. Then, the convergence rate of the algorithm is analyzed. The complexity of the algorithm scales linearly in the block length, and it can approximate, up to an arbitrarily small relative error, the objective function of the exact LP solution. When applied to a typical code from an appropriate nonbinary LDPC code ensemble, the algorithm can correct a constant fraction of errors in linear (in the block length) computational complexity. Computer experiments with the new iterative LP decoding algorithm show that, in the error floor region, it can have better performance compared to belief propagation decoding, with similar computational requirements.

IEEE Transactions on Information Theory•Aug 6, 2012•17 citations

Decoding low-density parity check codes with normalized APP-based algorithm

Jinghu Chen, M.P.C. Fossorier

We propose a normalized a posteriori probability (APP) based algorithm for the decoding of low-density parity check (LDPC) codes. The normalized APP-based algorithm utilizes normalization to improve the accuracy of the soft values delivered by the simplified APP-based algorithm from one iteration to another during the iterative decoding, and can achieve very good tradeoff between decoding complexity and performance.

Globecom•Nov 13, 2002•54 citations

Reduced complexity and improved performance decoding algorithm for nonbinary LDPC codes over GF(q)

Xin Chen, Aidong Men

Low-density parity-check (LDPC) codes over finite fields GF(q) have a better performance than those of the binary low-density parity-check codes, at short and medium block lengths, but the decoder of GF(q)-LDPC has more complexity. In this paper, we present a new reduced-complexity belief propagation (BP) decoding algorithm for GF(q)-LDPC codes by analyzing the reliability of code symbols. Instead of update all the variable nodes during iteration, we just update variable nodes which are mostly to be in an error. The algorithm also shows a property to reduce the effects of oscillating on decoding. The simulations prove that we could improve performance and reduce complexity at the same time for short and medium GF(q)-LDPC codes.

IEEE International Conference on Communication Technology (ICCT)•Nov 1, 2008•6 citations

Min-zone selection decoding algorithm for LDPC codes

Zhu Jin-kang

An iterative decoding algorithm for low-density parity-check(LDPC) codes,named min-zone selection(MZS) decoding algorithm,was proposed.The methods of min-zone selecting and approximation were combined in the proposed decoding algorithm in order to deal with the Q(x) function involved in the traditional belief propagation(BP) decoding algorithm.Simulation results show shat the computations in the decoding process of LDPC codes incurred only a little performance degradation.In fact,it is observed that,with proper selection of parameters,the MZS decoding algorithm can provide performance comparable to that of the BP decoding algorithm.

•Jan 1, 2008•0 citations

Near Optimum Majority-Logic Based Decoding of Low-Density Parity-Check Codes

Telex M. N. Ngatched, Attahiru Sule Alfa, Jun Cai

A reliability-based iterative majority-logic decoding algorithm for regular low-density parity-check (LDPC) codes was recently proposed by Huang et al. In this paper we present an improved version of that algorithm by introducing a different reliability measure for each check-sum of the parity-check matrix, and taking it into account in the computation of the extrinsic information that is used to update the reliability measure of each received bit in each iteration. Some simulations results are given, which show that the new algorithm, while requiring very little additional computational complexity, not only achieves a considerable error performance gain over the standard one, but also, importantly, outperforms the iterative decoding based on belief propagation (IDBP), especially for short and medium block length finite-geometry (FG) LDPC codes.

International Conference on Communications•Jun 1, 2011•3 citations

On Gaussian Approximation for Density Evolution of Low-Density Parity-Check Codes

Minyue Fu

This paper is concerned with density evolution for iterative decoding of low-density parity-check (LDPC) codes. We first study the problem of density evolution computation for regular LDPC codes. For this, we propose a simple computational algorithm based on the ergodicity theory. This method is shown to match very well with explicit calculations of density functions. The second problem we study is about the approach of Gaussian approximation to density evolution. We point out that it is inappropriate to use the mean of the density only to model the iterative decoding process. Instead, both the mean and variance are needed for Gaussian approximation. Finally, we consider the problem of density evolution for irregular LDPC codes. For this, we extend the density evolution algorithm for regular LDPC codes to irregular LDPC codes. We then illustrate that Gaussian approximation is also valid provided that the degree distributions are not wide. A dynamic model is also presented based on Gaussian approximation.

International Conference on Communications•Jan 1, 2006•19 citations
In this paper, the mean field (MF) and mixed mean field (MMF) algorithms for decoding low-density parity-check (LDPC) codes are considered. The MF principle is well established in statistical physics and artificial intelligence. Instead of using a single completely factorized approximated distribution as in the MF approach, the mixed MF algorithm forms a weighted average of several MF distributions as an approximation of the true posterior probability distribution. The MF decoding algorithm for linear block codes is derived and shown to be an approximation of the a posteriori probability (APP) decoding algorithm. The MF approach is then developed in the context of iterative decoding and presented as an approximation of the popular belief propagation decoding method. These results are extended to iterative decoding with the MMF algorithm. Simulation results show that the MF and MMF decoding algorithms yield a good performance-complexity tradeoff, especially when employed for decoding LDPC codes based on finite geometries.
The problem of low-complexity linear programming (LP) decoding of nonbinary low-density parity-check (LDPC) codes is considered, and an iterative LP decoding algorithm is presented. Results that were previously derived for binary LDPC codes are extended to the nonbinary case. Both simple and generalized nonbinary LDPC codes are considered. It is shown how the algorithm can be implemented efficiently using a finite-field fast Fourier transform. Then, the convergence rate of the algorithm is analyzed. The complexity of the algorithm scales linearly in the block length, and it can approximate, up to an arbitrarily small relative error, the objective function of the exact LP solution. When applied to a typical code from an appropriate nonbinary LDPC code ensemble, the algorithm can correct a constant fraction of errors in linear (in the block length) computational complexity. Computer experiments with the new iterative LP decoding algorithm show that, in the error floor region, it can have better performance compared to belief propagation decoding, with similar computational requirements.
Low-density parity-check (LDPC) codes over finite fields GF(q) have a better performance than those of the binary low-density parity-check codes, at short and medium block lengths, but the decoder of GF(q)-LDPC has more complexity. In this paper, we present a new reduced-complexity belief propagation (BP) decoding algorithm for GF(q)-LDPC codes by analyzing the reliability of code symbols. Instead of update all the variable nodes during iteration, we just update variable nodes which are mostly to be in an error. The algorithm also shows a property to reduce the effects of oscillating on decoding. The simulations prove that we could improve performance and reduce complexity at the same time for short and medium GF(q)-LDPC codes.
An iterative decoding algorithm for low-density parity-check(LDPC) codes,named min-zone selection(MZS) decoding algorithm,was proposed.The methods of min-zone selecting and approximation were combined in the proposed decoding algorithm in order to deal with the Q(x) function involved in the traditional belief propagation(BP) decoding algorithm.Simulation results show shat the computations in the decoding process of LDPC codes incurred only a little performance degradation.In fact,it is observed that,with proper selection of parameters,the MZS decoding algorithm can provide performance comparable to that of the BP decoding algorithm.
A reliability-based iterative majority-logic decoding algorithm for regular low-density parity-check (LDPC) codes was recently proposed by Huang et al. In this paper we present an improved version of that algorithm by introducing a different reliability measure for each check-sum of the parity-check matrix, and taking it into account in the computation of the extrinsic information that is used to update the reliability measure of each received bit in each iteration. Some simulations results are given, which show that the new algorithm, while requiring very little additional computational complexity, not only achieves a considerable error performance gain over the standard one, but also, importantly, outperforms the iterative decoding based on belief propagation (IDBP), especially for short and medium block length finite-geometry (FG) LDPC codes.
This paper is concerned with density evolution for iterative decoding of low-density parity-check (LDPC) codes. We first study the problem of density evolution computation for regular LDPC codes. For this, we propose a simple computational algorithm based on the ergodicity theory. This method is shown to match very well with explicit calculations of density functions. The second problem we study is about the approach of Gaussian approximation to density evolution. We point out that it is inappropriate to use the mean of the density only to model the iterative decoding process. Instead, both the mean and variance are needed for Gaussian approximation. Finally, we consider the problem of density evolution for irregular LDPC codes. For this, we extend the density evolution algorithm for regular LDPC codes to irregular LDPC codes. We then illustrate that Gaussian approximation is also valid provided that the degree distributions are not wide. A dynamic model is also presented based on Gaussian approximation.