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

On robust stability of the belief propagation algorithm for LDPC decoding

Björn S. Rüffer, Peter M. Dower, Christopher M. Kellett, Steven R. Weller

Published Jan 1, 2010• 1 citation
OpenAlex

Abstract

Abstract — The exact nonlinear loop gain of the belief propagation algorithm (BPA) in its log-likelihood ratio (LLR) formulation is computed. The nonlinear gains for regular lowdensity parity-check (LDPC) error correcting codes can be computed exactly using a simple formula. It is shown that in some neighborhood of the origin this gain is actually much smaller than the identity. Using a small-gain argument, this implies that the BPA is in fact locally input-to-state stable and produces bounded outputs for small-in-norm input LLR vectors. In a larger domain the algorithm produces at least bounded trajectories. Further it is shown that, as the block length increases, these regions exponentially shrink. Index Terms — iterative decoding; LDPC codes; dynamical system; convergence; belief propagation; small-gain theorem I.

Related papers

Modified Belief Propagation Decoding Algorithm for Low-Density Parity Check Code Based on Oscillation

Satoshi Gounai, Tomoaki Otsuki Ohtsuki, T. Kaneko

A low-density parity check (LDPC) code with the belief propagation (BP) or the log-likelihood ratio belief propagation (LLR-BP) can achieve good bit error rate (BER) performance approaching the Shannon limit. When a parity check matrix of the LDPC code has the cycle, the BP and LLR-BP decoding algorithms achieve approximate maximum a posterior probability (MAP) decoding. Although the decoding algorithms are approximate MAP decoding, LDPC codes can achieve very good BER. For the short and middle length LDPC codes, BER and block error rate (BLER) performances are affected by cycle largely. In each iteration, the magnitudes of a posterior LLRs of some bits oscillate owing to cycles. The oscillation is the dominant error factor in the high Eb/Noregion for short and middle length LDPC codes. In this paper, we extend the definition of oscillation to extrinsic LLR (ex-LLR) derived in the bit node process and propose the modified LLR-BP and the modified UMP-BP decoding algorithms. To reduce effects of oscillating ex-LLRs on decoding, for oscillating ex-LLRs, we add the previous ex-LLR to the current ex-LLR. From the computer simulation, we show that for short and middle length LDPC codes, with a simple modification, our proposed decoding algorithms can improve the conventional LLR-BP and UMP-BP decoding algorithms. In particular, we show that the modified UMP-BP decoding algorithm with low complexity can achieve better BER and BLER than the conventional LLR-BP decoding algorithm

IEEE Vehicular Technology Conference•Sep 8, 2006•15 citations

Comments on successive relaxation for decoding of LDPC codes

Hua Xiao, Amir H. Banihashemi

The application of successive relaxation (SR) to the fixed-point problem associated with the iterative decoding of low-density parity-check (LDPC) codes was proposed by Hemati et al.. The simulation results presented by Hemati et al. for the SR version of belief propagation (BP) in the likelihood ratio (LR) domain and that of min-sum (MS) in the log-likelihood ratio (LLR) domain are based on the assumption of all-zero codeword transmission. This assumption however results in erroneous error rates when SR is applied in the LR domain. Here, we correct the simulation results reported by Hemati et al. for SR-BP in the LR domain. Furthermore, we investigate the performance of SR-BP and SR-MS in the LLR and LR domains, respectively. The results for a binary input additive white Gaussian noise (BIAWGN) channel show that for both BP and MS, the application of SR in the two domains of LR and LLR results in different error correcting performance. In particular, for the tested codes, it is shown that among the four algorithms, SR-MS-LLR has the best performance. It outperforms standard MS and BP by up to about 0.6 dB and 0.3 dB, respectively, offering an attractive solution in terms of performance/complexity tradeoff.

IEEE Transactions on Communications•Oct 1, 2009•4 citations

Belief-propagation with information correction: improved near maximum-likelihood decoding of low-density parity-check codes

Nedeljko Varnica, M.P.C. Fossorier

We propose an improved belief-propagation (BP) decoder for low-density parity-check (LDPC) codes based on channel information correction. We show that our algorithm achieves sizeable performance gains (in waterfall and error floor regions) compared to the standard BP decoder. We verify by examples that the proposed decoder almost achieves the maximum-likelihood decoding performance for short LDPC codes

IEEE International Symposium on Information Theory (ISIT)•Dec 23, 2004•18 citations

An Improved Decoding Algorithm for Finite-Geometry LDPC Codes

Yin-bing BIAN, Yuanqing Wang, Jie Wang

In this letter, we propose a new modification to the belief propagation (BP) decoding algorithm for Finite-Geometry low-density parity-check (LDPC) codes. The modification is based on introducing into the iterative process, which can break the oscillations of bit log-likelihood ratio (LLR) values. Simulations show that, with a given maximum iteration, the feedback BP (FBP) algorithm can achieve better performance than the conventional belief propagation algorithm.

IEICE Transactions on Communications•Apr 1, 2007•1 citation

Successive relaxation for decoding of LDPC codes

Hua Xiao, Sina Tolouei, Amir H. Banihashemi

The application of successive relaxation (SR) to the fixed-point problem associated with the iterative decoding of low-density parity-check (LDPC) codes is studied. We consider finite-length codes decoded by belief propagation (BP) and a well-known approximation of it, referred to as min-sum (MS), over a binary input additive white Gaussian noise (BIAWGN) channel. For both algorithms, we show that the application of SR in different domains results in different error correcting performance. In particular, the performances of SR in log-likelihood ratio (LLR) and LR domains for BP and MS are compared, and it is shown that SR-MS-LLR has the best performance. For the tested codes, SR-MS-LLR outperforms standard BP by up to about 0.5dB, offering an attractive solution in terms of performance/complexity tradeoff. We also investigate the effects of quantization on SR-MS-LLR and demonstrate that at least 6–7 bits of quantization is required to capture close to floating-point performance.

Biennial Symposium on Communications•Jun 1, 2008•13 citations

Reduced-Complexity Decoding of LDPC Codes

J. Chen, Ajay Dholakia, Evangelos S. Eleftheriou +2 more

Various log-likelihood-ratio-based belief-propagation (LLR-BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representations of the decoding computations are shown to achieve a reduction in complexity by simplifying the check-node update, or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from performance, latency, computational-complexity, and memory-requirement perspectives.

IEEE Transactions on Communications•Aug 1, 2005•952 citations
Abstract — The exact nonlinear loop gain of the belief propagation algorithm (BPA) in its log-likelihood ratio (LLR) formulation is computed. The nonlinear gains for regular lowdensity parity-check (LDPC) error correcting codes can be computed exactly using a simple formula. It is shown that in some neighborhood of the origin this gain is actually much smaller than the identity. Using a small-gain argument, this implies that the BPA is in fact locally input-to-state stable and produces bounded outputs for small-in-norm input LLR vectors. In a larger domain the algorithm produces at least bounded trajectories. Further it is shown that, as the block length increases, these regions exponentially shrink. Index Terms — iterative decoding; LDPC codes; dynamical system; convergence; belief propagation; small-gain theorem I.
A low-density parity check (LDPC) code with the belief propagation (BP) or the log-likelihood ratio belief propagation (LLR-BP) can achieve good bit error rate (BER) performance approaching the Shannon limit. When a parity check matrix of the LDPC code has the cycle, the BP and LLR-BP decoding algorithms achieve approximate maximum a posterior probability (MAP) decoding. Although the decoding algorithms are approximate MAP decoding, LDPC codes can achieve very good BER. For the short and middle length LDPC codes, BER and block error rate (BLER) performances are affected by cycle largely. In each iteration, the magnitudes of a posterior LLRs of some bits oscillate owing to cycles. The oscillation is the dominant error factor in the high Eb/Noregion for short and middle length LDPC codes. In this paper, we extend the definition of oscillation to extrinsic LLR (ex-LLR) derived in the bit node process and propose the modified LLR-BP and the modified UMP-BP decoding algorithms. To reduce effects of oscillating ex-LLRs on decoding, for oscillating ex-LLRs, we add the previous ex-LLR to the current ex-LLR. From the computer simulation, we show that for short and middle length LDPC codes, with a simple modification, our proposed decoding algorithms can improve the conventional LLR-BP and UMP-BP decoding algorithms. In particular, we show that the modified UMP-BP decoding algorithm with low complexity can achieve better BER and BLER than the conventional LLR-BP decoding algorithm
The application of successive relaxation (SR) to the fixed-point problem associated with the iterative decoding of low-density parity-check (LDPC) codes was proposed by Hemati et al.. The simulation results presented by Hemati et al. for the SR version of belief propagation (BP) in the likelihood ratio (LR) domain and that of min-sum (MS) in the log-likelihood ratio (LLR) domain are based on the assumption of all-zero codeword transmission. This assumption however results in erroneous error rates when SR is applied in the LR domain. Here, we correct the simulation results reported by Hemati et al. for SR-BP in the LR domain. Furthermore, we investigate the performance of SR-BP and SR-MS in the LLR and LR domains, respectively. The results for a binary input additive white Gaussian noise (BIAWGN) channel show that for both BP and MS, the application of SR in the two domains of LR and LLR results in different error correcting performance. In particular, for the tested codes, it is shown that among the four algorithms, SR-MS-LLR has the best performance. It outperforms standard MS and BP by up to about 0.6 dB and 0.3 dB, respectively, offering an attractive solution in terms of performance/complexity tradeoff.
The application of successive relaxation (SR) to the fixed-point problem associated with the iterative decoding of low-density parity-check (LDPC) codes is studied. We consider finite-length codes decoded by belief propagation (BP) and a well-known approximation of it, referred to as min-sum (MS), over a binary input additive white Gaussian noise (BIAWGN) channel. For both algorithms, we show that the application of SR in different domains results in different error correcting performance. In particular, the performances of SR in log-likelihood ratio (LLR) and LR domains for BP and MS are compared, and it is shown that SR-MS-LLR has the best performance. For the tested codes, SR-MS-LLR outperforms standard BP by up to about 0.5dB, offering an attractive solution in terms of performance/complexity tradeoff. We also investigate the effects of quantization on SR-MS-LLR and demonstrate that at least 6–7 bits of quantization is required to capture close to floating-point performance.
Various log-likelihood-ratio-based belief-propagation (LLR-BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representations of the decoding computations are shown to achieve a reduction in complexity by simplifying the check-node update, or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from performance, latency, computational-complexity, and memory-requirement perspectives.