Experimental Results about the Dynamics of the Generalized Belief Propagation Used on LDPC Codes

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.

• Jean-Christophe Sibel
• Sylvain Reynal
• David Declercq

• iterative decoder
• LDPC
• region-graph
• chaos.

[1] R.G. Gallager, "Low-Density Parity-Check Codes," Ph.D. dissertation, MIT, 1963.
[2] F.R. Kschischang, B. J. Frey eand H.A. Loeliger, "Factor Graphs and
the Sum-Product Algorithm," IEEE Trans. on Inf. Theory, vol. 47, 2001, NO. 2.
[3] J. Pearl, Probablistic Reasoning in Intelligent Systems: Networks of
Plausible Inference. Morgan Kaufmann, 1988.
[4] T.J. Richardson, "Error floors of LDPC codes," in Proc. 41st Annual
Allerton Conf. on Comm. Cont. and Comp., 2003.
[5] S.Y Chung, T.J. Richardson and R.L. Urbanke, "Analysis of Sum-
Product Decoding of Low-Density Parity-Check Codes Using a Gaussian
Approximation," IEEE Trans. on Inf. Theory, vol. 47, 2001, NO. 2.
[6] T.J. Richardson and R.L. Urbanke, "The Capacity of Low-Density Parity-Check Codes Under Message-Passing Decoding," IEEE Trans. on Inf. Theory, vol. 47, 2001, N0. 2.
[7] K.P. Murphy, Y. Weiss and M.I. Jordan, "Loopy belef propagation for
approximate inference: an empirical study," in Proc. Uncertainty in AI, 1999.
[8] J.S. Yedidia, W.T. Freeman and Y. Weiss, "Constructing free energy
approximations and Generalized Belief Propagation algorithms," IEEE
Trans. on Inf. Theory, vol. 51, pp. 2282-2313, 2004.
[9] P. Pakzad et V. Anantharam, "Estimation and marginalization using
Kikuchi approximation methods," Neural Computation, vol. 17, pp.
1836-1873, 2003.
[10] H.A. Bethe, "Statistical Theory of Superlattices," in Proc. Roy. Soc. London, 1935.
[11] R. Kikuchi, "A Theory of Cooperative Phenomena," Phys. Rev, vol. 81,
pp. 988-1003, 1951.
[12] R.M. Tanner, R. Michael, D. Sridhara and T. Fuja, "A Class of Group-Structured LDPC Codes," 2001.
[13] S. Sankaranarayanan, S. K. Chilappagari, R. Radhakrishnan and B.
Vasic, "Failures of the Gallager B Decoder: Analysis and Applications,"
in ITA Workshop UCSD, 2006.
[14] X. Zheng, F.C.M. Lau, C.K. Tse and S.C. Wong, “Study of bifurcation
behavior of LDPC decoders,” Int. Journal of Bifurcation and Chaos,
vol. 16, pp. 3435–3449, 2005.
[15] R. Hilborn, Chaos and Nonlinear Dynamics: An Introduction for Scientists
and Engineers. Oxford University Press, 2000.
[16] M.T. Rosenstein, J.J. Collins and C.J. De Luca, “A practical method for
calculating largest Lyapunov exponents from small data sets,” Physica
D, vol. 65, pp. 117–134, 1993.
[17] A. Wolf, J.B. Swift, H.L. Swinney and J.A. Vastano, “Determining
Lyapunov Exponents from a Time Series,” Physica, pp. 285–317, 1985.