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

Evidence of chaos in the Belief Propagation for LDPC codes

Jean-Christophe Sibel, Sylvain Reynal, David Declercq

Published Jun 12, 2012• 4 citations
OpenAlex

Abstract

Abstract. In this paper, we investigate the behaviors of the Belief Propagation algorithm considered as a dynamic system. In the context of LDPC (Low Density Parity-Check) codes, we use the noise power of the transmission channel as a potentiometer to evaluate the different motions that the BP can follow. The computations of dynamic quantifiers as the bifurcation diagram, the Lyapunov exponent and the reconstructed trajectory enable to bring out four main behaviors. In addition, we propose a novel measure that is the hyperspheres method, which provides the knowledge of the time evolution of the attractor size. The information collected from these different quantifiers helps to better understand the BP evolution and to focus on the noise power values for which the BP suffers from chaos.

Related papers

Experimental Results About The Dynamics Of The Generalized Belief Propagation Used On Ldpc Codes

Jean-Christophe Sibel, Sylvain Reynal, David Declercq

In the context of channel coding, the Generalized Belief Propagation (GBP) is an iterative algorithm used to recover the transmission bits sent through a noisy channel. To ensure a reliable transmission, we apply a map on the bits, that is called a code. This code induces artificial correlations between the bits to send, and it can be modeled by a graph whose nodes are the bits and the edges are the correlations. This graph, called Tanner graph, is used for most of the decoding algorithms like Belief Propagation or Gallager-B. The GBP is based on a non unic transformation of the Tanner graph into a so called region-graph. A clear advantage of the GBP over the other algorithms is the freedom in the construction of this graph. In this article, we explain a particular construction for specific graph topologies that involves relevant performance of the GBP. Moreover, we investigate the behavior of the GBP considered as a dynamic system in order to understand the way it evolves in terms of the time and in terms of the noise power of the channel. To this end we make use of classical measures and we introduce a new measure called the hyperspheres method that enables to know the size of the attractors.

•May 22, 2012•0 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

On the Generalized Belief Propagation and its dynamics

Jean-Christophe Sibel, Sylvain Reynal

Numerous inference problems in statistical physics, computer vision or error-correcting coding theory consist in approximating the marginal probability distributions on Markov Random Fields (MRF). The Belief Propagation (BP) is an accurate solution that is optimal if the MRF is loop free and suboptimal otherwise. In the context of error-correcting coding theory, any Low-Density Parity-Check (LDPC) code has a graphical representation, the Tanner graph, which is a particular MRF. It is used as a media for the BP algorithm to correct the bits, damaged by a noisy channel, by estimating their probability distributions. Though loops and combination thereof in the Tanner graph prevent the BP from being optimal, especially harmful topological structures called the trapping-sets. The BP has been extended to the Generalized Belief Propagation (GBP). This message-passing algorithm runs on a non unique mapping of the Tanner graph, namely the regiongraph, such that its nodes are gatherings of the Tanner graph nodes. Then it appears the possibility to decrease the loops effect, making the GBP more accurate than the BP. In this article, we expose a novel region graph construction suited to the Tanner code, an LDPC code whose Tanner graph is entirely covered by trapping-sets. Furthermore, we investigate the dynamic behavior of the GBP compared with that of the BP to understand its evolution in terms of the Signal-to-Noise Ratio (SNR). To this end we make use of classical estimators and we introduce a new one called the hyperspheres method.

International Conference on Control, Automation and Information Sciences (ICCAIS)•Nov 1, 2012•1 citation

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

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

Another derivation process of belief propagation algorithm

Jingli Lin, Long-jiang Jing, Weile Zhu +1 more

Generally, soft decoding of low-density parity-check codes can be implemented by iterative decoding based on belief propagation (BP) algorithm. In this paper, the BP algorithm is presented and derived in a way which differs from that by Gallager, which helps to understand iterative decoding of LDPC codes more clearly.

International Conference on Communications, Circuits and Systems•Jul 1, 2007•0 citations
Abstract. In this paper, we investigate the behaviors of the Belief Propagation algorithm considered as a dynamic system. In the context of LDPC (Low Density Parity-Check) codes, we use the noise power of the transmission channel as a potentiometer to evaluate the different motions that the BP can follow. The computations of dynamic quantifiers as the bifurcation diagram, the Lyapunov exponent and the reconstructed trajectory enable to bring out four main behaviors. In addition, we propose a novel measure that is the hyperspheres method, which provides the knowledge of the time evolution of the attractor size. The information collected from these different quantifiers helps to better understand the BP evolution and to focus on the noise power values for which the BP suffers from chaos.
In the context of channel coding, the Generalized Belief Propagation (GBP) is an iterative algorithm used to recover the transmission bits sent through a noisy channel. To ensure a reliable transmission, we apply a map on the bits, that is called a code. This code induces artificial correlations between the bits to send, and it can be modeled by a graph whose nodes are the bits and the edges are the correlations. This graph, called Tanner graph, is used for most of the decoding algorithms like Belief Propagation or Gallager-B. The GBP is based on a non unic transformation of the Tanner graph into a so called region-graph. A clear advantage of the GBP over the other algorithms is the freedom in the construction of this graph. In this article, we explain a particular construction for specific graph topologies that involves relevant performance of the GBP. Moreover, we investigate the behavior of the GBP considered as a dynamic system in order to understand the way it evolves in terms of the time and in terms of the noise power of the channel. To this end we make use of classical measures and we introduce a new measure called the hyperspheres method that enables to know the size of the attractors.
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.
Numerous inference problems in statistical physics, computer vision or error-correcting coding theory consist in approximating the marginal probability distributions on Markov Random Fields (MRF). The Belief Propagation (BP) is an accurate solution that is optimal if the MRF is loop free and suboptimal otherwise. In the context of error-correcting coding theory, any Low-Density Parity-Check (LDPC) code has a graphical representation, the Tanner graph, which is a particular MRF. It is used as a media for the BP algorithm to correct the bits, damaged by a noisy channel, by estimating their probability distributions. Though loops and combination thereof in the Tanner graph prevent the BP from being optimal, especially harmful topological structures called the trapping-sets. The BP has been extended to the Generalized Belief Propagation (GBP). This message-passing algorithm runs on a non unique mapping of the Tanner graph, namely the regiongraph, such that its nodes are gatherings of the Tanner graph nodes. Then it appears the possibility to decrease the loops effect, making the GBP more accurate than the BP. In this article, we expose a novel region graph construction suited to the Tanner code, an LDPC code whose Tanner graph is entirely covered by trapping-sets. Furthermore, we investigate the dynamic behavior of the GBP compared with that of the BP to understand its evolution in terms of the Signal-to-Noise Ratio (SNR). To this end we make use of classical estimators and we introduce a new one called the hyperspheres method.
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.
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.