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

Decoding with belief propagation

Marc Mézard, Andrea Montanari A

Published Jan 22, 2009• 0 citations
Publisher

Abstract

Abstract This chapter revisits the problem of decoding low density parity check (LDPC) codes. The maximum a posteriori probability (MAP) decoding of a bit is described as a statistical inference problem, and belief propagation is applied to its solution. The corresponding message passing procedure is analyzed in details, and the threshold noise level below which this ‘iterative decoding’ achieves perfect decoding is derived. The chapter ends with a general discussion of the relation between message passing and optimal (exact symbol MAP) decoding.

DOI
10.1093/acprof:oso/9780198570837.003.0015

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

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

Finite alphabet iterative decoders for LDPC codes surpassing floating-point iterative decoders

Shiva Kumar Planjery, David Declercq, Ludovic Danjean +1 more

Introduced is a new type of message-passing (MP) decoders for low-density parity-check (LDPC) codes over the binary symmetric channel. Unlike traditional belief propagation (BP) based MP algorithms which propagate probabilities or log-likelihoods, the new MP decoders propagate messages requiring only a finite number of bits for their representation in such a way that good performance in the error floor region is ensured. Additionally, these messages are not quantised probabilities or log-likelihoods. As examples, MP decoders are provided that require only three bits for message representation, but surpass the floating-point BP (which requires a large number of bits for representation) in the error-floor region.

Electronics Letters•Aug 4, 2011•26 citations

On the Message Passing Efficiency of Polar and Low-Density Parity-Check Decoders

Dawei Yin, Yuan Liy, Xianbin Wang +6 more

This study focuses on the efficiency of message-passing-based decoding algorithms for polar and low-density parity-check (LDPC) codes. Both successive cancellation (SC) and belief propagation (BP) decoding algorithms are studied under the message-passing framework. Counter-intuitively, SC decoding demonstrates the highest decoding efficiency although it was considered a weak decoder regarding error-correction performance. We analyze the complexity-performance tradeoff to dynamically track the decoding efficiency, where the complexity is measured by the number of messages passed (NMP), and the performance is measured by the statistical distance to the maximum a posteriori (MAP) estimate. This study offers new insight into the contribution of each message passing in decoding, and compares various decoding algorithms on a message-by-message level.

arXiv:2206.06897•IEEE Globecom Workshops (GC Wkshps)•Dec 4, 2022•6 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

Iterative decoding beyond belief propagation

Shiva Kumar Planjery, Shashi Kiran Chilappagari, Bane V. Vasic +2 more

At the heart of modern coding theory lies the fact that low-density parity-check (LDPC) codes can be efficiently decoded by belief propagation (BP). The BP is an inference algorithm which operates on a graphical model of a code, and lends itself to low-complexity and high-speed implementations, making it the algorithm of choice in many applications. It has unprecedentedly good error rate performance, so good that when decoded by the BP, LDPC codes approach theoretical limits of channel capacity. However, this capacity approaching property holds only in the asymptotic limit of code length, while codes of practical lengths suffer abrupt performance degradation in the low noise regime known as the error floor phenomenon. Our study of error floor has led to an interesting and surprising finding that it is possible to design iterative decoders which are much simpler yet better than belief propagation! These decoders do not propagate beliefs but a rather different kind of messages that reflect the local structure of the code graph. This has opened a plethora of exciting theoretical problems and applications. This paper introduces this new paradigm.

Information Theory and Applications Workshop (ITA)•Jan 1, 2010•18 citations
Abstract This chapter revisits the problem of decoding low density parity check (LDPC) codes. The maximum a posteriori probability (MAP) decoding of a bit is described as a statistical inference problem, and belief propagation is applied to its solution. The corresponding message passing procedure is analyzed in details, and the threshold noise level below which this ‘iterative decoding’ achieves perfect decoding is derived. The chapter ends with a general discussion of the relation between message passing and optimal (exact symbol MAP) decoding.
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.
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.
Introduced is a new type of message-passing (MP) decoders for low-density parity-check (LDPC) codes over the binary symmetric channel. Unlike traditional belief propagation (BP) based MP algorithms which propagate probabilities or log-likelihoods, the new MP decoders propagate messages requiring only a finite number of bits for their representation in such a way that good performance in the error floor region is ensured. Additionally, these messages are not quantised probabilities or log-likelihoods. As examples, MP decoders are provided that require only three bits for message representation, but surpass the floating-point BP (which requires a large number of bits for representation) in the error-floor region.
This study focuses on the efficiency of message-passing-based decoding algorithms for polar and low-density parity-check (LDPC) codes. Both successive cancellation (SC) and belief propagation (BP) decoding algorithms are studied under the message-passing framework. Counter-intuitively, SC decoding demonstrates the highest decoding efficiency although it was considered a weak decoder regarding error-correction performance. We analyze the complexity-performance tradeoff to dynamically track the decoding efficiency, where the complexity is measured by the number of messages passed (NMP), and the performance is measured by the statistical distance to the maximum a posteriori (MAP) estimate. This study offers new insight into the contribution of each message passing in decoding, and compares various decoding algorithms on a message-by-message level.
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.
At the heart of modern coding theory lies the fact that low-density parity-check (LDPC) codes can be efficiently decoded by belief propagation (BP). The BP is an inference algorithm which operates on a graphical model of a code, and lends itself to low-complexity and high-speed implementations, making it the algorithm of choice in many applications. It has unprecedentedly good error rate performance, so good that when decoded by the BP, LDPC codes approach theoretical limits of channel capacity. However, this capacity approaching property holds only in the asymptotic limit of code length, while codes of practical lengths suffer abrupt performance degradation in the low noise regime known as the error floor phenomenon. Our study of error floor has led to an interesting and surprising finding that it is possible to design iterative decoders which are much simpler yet better than belief propagation! These decoders do not propagate beliefs but a rather different kind of messages that reflect the local structure of the code graph. This has opened a plethora of exciting theoretical problems and applications. This paper introduces this new paradigm.