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

Authors: Jean-Christophe Sibel, Sylvain Reynal, David Declercq

Abstract:

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.

Keywords: iterative decoder, LDPC, region-graph, chaos.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1073267

References:

[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.