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)

Bounds on the performance of belief propagation decoding

D. Burshtein, G. Miller

Published Nov 13, 2002• 2 citations
Publisher

Abstract

We consider Gallager's (1963) soft decoding (belief propagation) algorithm for decoding low density parity check (LDPC) codes, when applied to an arbitrary binary-input symmetric-output channel. By considering the expected values of the messages, we derive both lower and upper bounds on the performance of the algorithm. We also derive various properties of the decoding algorithm, such as robustness to the initial values of the messages. Our results apply both to regular and irregular LDPC codes.

DOI
10.1109/isit.2001.935866

Related papers

Bounds on the performance of belief propagation decoding

David Burshtein, G. Miller

We consider Gallager's (1963) soft-decoding (belief propagation) algorithm for decoding low-density parity-check (LDPC) codes, when applied to an arbitrary binary-input symmetric-output channel. By considering the expected values of the messages, we derive both lower and upper bounds on the performance of the algorithm. We also derive various properties of the decoding algorithm, such as a certain robustness to the details of the channel noise. Our results apply both to regular and irregular LDPC codes.

IEEE Transactions on Information Theory•Jan 1, 2002•42 citations

Performance Study of a Class of Irregular LDPC Codes through Low Complexity Bounds on Their Belief-Propagation Decoding Thresholds

F. Vatta, Alessandro Soranzo, Massimiliano Comisso +2 more

This paper investigates about the usefulness of some recently published low complexity upper bounds on belief-propagation decoding thresholds for irregular low-density parity-check (LDPC) codes to analyze their performance on memoryless binary input - additive white Gaussian noise (BI-AWGN) channels, with sum-product decoding. Irregular LDPC codes are known to perform better than regular ones, and to exhibit, like them, the so called “threshold phenomenon”, being the threshold defined as the maximum noise level such that an arbitrarily small bit-error probability can be achieved as the block length tends to infinity. We use a simplified analysis of the belief-propagation decoding algorithm, i.e., consider a Gaussian approximation for message densities under density evolution, and a simple algorithmic method, defined recently, to estimate the decoding thresholds for regular and irregular LDPC codes on BI-AWGN channels.

AEIT International Annual Conference•Sep 1, 2019•11 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•7 citations

Properties of Optimum Binary Message-Passing Decoders

Masoud Ardakani, Frank R. Kschischang

We consider a class of message-passing decoders for low-density parity-check (LDPC) codes whose messages are binary valued. We prove that if the channel is symmetric and all codewords are equally likely to be transmitted, an optimum decoding rule (in the sense of minimizing message error rate) should satisfy certain symmetry and isotropy conditions. Using this result, we prove that Gallager's Algorithm B achieves the optimum decoding threshold among all binary message-passing decoding algorithms for regular codes. For irregular codes, we argue that when the nodes of the message-passing decoder do not exploit knowledge of their decoding neighborhood, optimality of Gallager's Algorithm B is preserved. We also consider the problem of designing irregular LDPC codes and find a bound on the achievable rates with Gallager's Algorithm B. Using this bound, we study the case of low error-rate channels and analytically find good degree distributions for them.

IEEE Transactions on Information Theory•Sep 26, 2005•14 citations

Measure on the Performance of Belief Propagation Decoding Algorithm

He Yu

Formulas for updated rules of the belief propagation algorithm applied to low density parity check (LDPC) codes are systematically derived based on the tree and the finite state machine (FSM).The probability measure on the continuous message space is introduced to evaluate the evolution of message densities within iterative decoding rounds,and derivations of the output distributions of common binary symmetric channels and the message density evolution are given in detail.The parameterized estimation of the performance of the algorithm is also discussed.The analytic and calculable means can be used to make systematical analysis for the convergence of BP algorithms independent of channels,and can be of help in designing LDPC codes and analyzing quantization effects for the fast decoding on the purpose of practical applications of LDPC codes to real time communication systems.

Dianzi xuebao•Jan 1, 2002•0 citations

Bounds on the belief propagation threshold of non-binary LDPC codes

Leonid Geller, David Burshtein

We consider LDPC code ensembles over non-binary Galois fields, when used for transmission over arbitrary 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 Information Theory Workshop (ITW)•Sep 1, 2012•1 citation
We consider Gallager's (1963) soft decoding (belief propagation) algorithm for decoding low density parity check (LDPC) codes, when applied to an arbitrary binary-input symmetric-output channel. By considering the expected values of the messages, we derive both lower and upper bounds on the performance of the algorithm. We also derive various properties of the decoding algorithm, such as robustness to the initial values of the messages. Our results apply both to regular and irregular LDPC codes.
We consider Gallager's (1963) soft-decoding (belief propagation) algorithm for decoding low-density parity-check (LDPC) codes, when applied to an arbitrary binary-input symmetric-output channel. By considering the expected values of the messages, we derive both lower and upper bounds on the performance of the algorithm. We also derive various properties of the decoding algorithm, such as a certain robustness to the details of the channel noise. Our results apply both to regular and irregular LDPC codes.
This paper investigates about the usefulness of some recently published low complexity upper bounds on belief-propagation decoding thresholds for irregular low-density parity-check (LDPC) codes to analyze their performance on memoryless binary input - additive white Gaussian noise (BI-AWGN) channels, with sum-product decoding. Irregular LDPC codes are known to perform better than regular ones, and to exhibit, like them, the so called “threshold phenomenon”, being the threshold defined as the maximum noise level such that an arbitrarily small bit-error probability can be achieved as the block length tends to infinity. We use a simplified analysis of the belief-propagation decoding algorithm, i.e., consider a Gaussian approximation for message densities under density evolution, and a simple algorithmic method, defined recently, to estimate the decoding thresholds for regular and irregular LDPC codes on BI-AWGN channels.
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.
We consider a class of message-passing decoders for low-density parity-check (LDPC) codes whose messages are binary valued. We prove that if the channel is symmetric and all codewords are equally likely to be transmitted, an optimum decoding rule (in the sense of minimizing message error rate) should satisfy certain symmetry and isotropy conditions. Using this result, we prove that Gallager's Algorithm B achieves the optimum decoding threshold among all binary message-passing decoding algorithms for regular codes. For irregular codes, we argue that when the nodes of the message-passing decoder do not exploit knowledge of their decoding neighborhood, optimality of Gallager's Algorithm B is preserved. We also consider the problem of designing irregular LDPC codes and find a bound on the achievable rates with Gallager's Algorithm B. Using this bound, we study the case of low error-rate channels and analytically find good degree distributions for them.
Formulas for updated rules of the belief propagation algorithm applied to low density parity check (LDPC) codes are systematically derived based on the tree and the finite state machine (FSM).The probability measure on the continuous message space is introduced to evaluate the evolution of message densities within iterative decoding rounds,and derivations of the output distributions of common binary symmetric channels and the message density evolution are given in detail.The parameterized estimation of the performance of the algorithm is also discussed.The analytic and calculable means can be used to make systematical analysis for the convergence of BP algorithms independent of channels,and can be of help in designing LDPC codes and analyzing quantization effects for the fast decoding on the purpose of practical applications of LDPC codes to real time communication systems.
We consider LDPC code ensembles over non-binary Galois fields, when used for transmission over arbitrary 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.