{"title":"Experimental Results about the Dynamics of the Generalized Belief Propagation Used on LDPC Codes","authors":"Jean-Christophe Sibel, Sylvain Reynal, David Declercq","volume":65,"journal":"International Journal of Physical and Mathematical Sciences","pagesStart":564,"pagesEnd":573,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/9701","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.<\/p>\r\n","references":"[1] R.G. Gallager, \"Low-Density Parity-Check Codes,\" Ph.D. dissertation, MIT, 1963.\r\n[2] F.R. Kschischang, B. J. Frey eand H.A. Loeliger, \"Factor Graphs and\r\nthe Sum-Product Algorithm,\" IEEE Trans. on Inf. Theory, vol. 47, 2001, NO. 2.\r\n[3] J. Pearl, Probablistic Reasoning in Intelligent Systems: Networks of\r\nPlausible Inference. Morgan Kaufmann, 1988.\r\n[4] T.J. Richardson, \"Error floors of LDPC codes,\" in Proc. 41st Annual\r\nAllerton Conf. on Comm. Cont. and Comp., 2003.\r\n[5] S.Y Chung, T.J. Richardson and R.L. Urbanke, \"Analysis of Sum-\r\nProduct Decoding of Low-Density Parity-Check Codes Using a Gaussian\r\nApproximation,\" IEEE Trans. on Inf. Theory, vol. 47, 2001, NO. 2.\r\n[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.\r\n[7] K.P. Murphy, Y. Weiss and M.I. Jordan, \"Loopy belef propagation for\r\napproximate inference: an empirical study,\" in Proc. Uncertainty in AI, 1999.\r\n[8] J.S. Yedidia, W.T. Freeman and Y. Weiss, \"Constructing free energy\r\napproximations and Generalized Belief Propagation algorithms,\" IEEE\r\nTrans. on Inf. Theory, vol. 51, pp. 2282-2313, 2004.\r\n[9] P. Pakzad et V. Anantharam, \"Estimation and marginalization using\r\nKikuchi approximation methods,\" Neural Computation, vol. 17, pp.\r\n1836-1873, 2003.\r\n[10] H.A. Bethe, \"Statistical Theory of Superlattices,\" in Proc. Roy. Soc. London, 1935.\r\n[11] R. Kikuchi, \"A Theory of Cooperative Phenomena,\" Phys. Rev, vol. 81,\r\npp. 988-1003, 1951.\r\n[12] R.M. Tanner, R. Michael, D. Sridhara and T. Fuja, \"A Class of Group-Structured LDPC Codes,\" 2001.\r\n[13] S. Sankaranarayanan, S. K. Chilappagari, R. Radhakrishnan and B.\r\nVasic, \"Failures of the Gallager B Decoder: Analysis and Applications,\"\r\nin ITA Workshop UCSD, 2006.\r\n[14] X. Zheng, F.C.M. Lau, C.K. Tse and S.C. Wong, \u201cStudy of bifurcation\r\nbehavior of LDPC decoders,\u201d Int. Journal of Bifurcation and Chaos,\r\nvol. 16, pp. 3435\u20133449, 2005.\r\n[15] R. Hilborn, Chaos and Nonlinear Dynamics: An Introduction for Scientists\r\nand Engineers. Oxford University Press, 2000.\r\n[16] M.T. Rosenstein, J.J. Collins and C.J. De Luca, \u201cA practical method for\r\ncalculating largest Lyapunov exponents from small data sets,\u201d Physica\r\nD, vol. 65, pp. 117\u2013134, 1993.\r\n[17] A. Wolf, J.B. Swift, H.L. Swinney and J.A. Vastano, \u201cDetermining\r\nLyapunov Exponents from a Time Series,\u201d Physica, pp. 285\u2013317, 1985.","publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 65, 2012"}