Magnetization Performance of LDPC Reduced-Complexity Decoding Algorithms

Manel Abdelhedi, Omessaad Hamdi, Ammar Bouallegue

.

DOI: 10.4236/ijcns.2010.36073                

Abstract

Low-density parity-check (LDPC) codes are very efficient for communicating reliably through a noisy channel. N.Sourlas [1] showed that LDPC codes, which revolutionize the codes domain and used in many communications standards, can be mapped onto an Ising spin systems. Besides, it has been shown that the Belief-Propagation (BP) algorithm, the LDPC codes decoding algorithm, is equivalent to the Thouless- Anderson-Palmer (TAP) approach [2]. Unfortunately, no study has been made for the other decoding algorithms. In this paper, we develop the Log-Likelihood Ratios-Belief Propagation (LLR-BP) algorithm and its simplifications the BP-Based algorithm and the λ-min algorithm with the TAP approach. We present the performance of these decoding algorithms using statistical physics argument i.e., we present the performance as function of the magnetization.

Keywords

LDPC Codes, Ising Spin, LLR-BP Algorithm, BP-Based Algorithm, λ-Min Algorithm, TAP Approach

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	N. Sourlas, “Spin-Glass Models as Error-Correcting Codes,” Nature, Vol. 339, No. 6227, 1989, pp.693-695.
[2]	D. J. Thouless, P. W. Anderson and R. G. Palmer, “Solution of Solvable Model of A Spin Glass,” Philosophical Magazine, Vol. 35, No. 3, 1977, pp. 593-601.
[3]	R. G. Gallager, “Low-Density Parity-Check Codes,” M.I.T. Press, Cambridge, Massachusetts, 1963.
[4]	D. J. C. Mackay and R. M. Neal, “Near Shannon Limit Performance of Low Density Parity Check Codes,” Electronics Letters, Vol. 32, No. 18, 1996, pp.1645-1646.
[5]	D. J. C. Mackay, “Good Error-Correcting Codes Based on Very Sparse Matrices,” IEEE Transactions on Information Theory, Vol. 45, No. 2, 1999, pp. 399-431.
[6]	M. P. C. Fossorier, M. Mihaljevic and I. Imai, “Reduced Complexity Iterative Decoding of Low Density Parity Check Codes Based on Belief Propagation,” IEEE Tran- sactions on Communications, Vol. 47, No. 5, 1999, pp. 673-680.
[7]	F. Guilloud, E. Boutillon and J. L. Danger, “λ-Min Decoding Algorithm of Regular and Irregular LDPC Codes,” Proceedings of 3rd International Symposium on Turbo Codes & Related Topics, Brest, 2003, pp. 451-454.
[8]	Y. Kabashima and D. Saad, “Belief Propagation Vs TAP for Decoding Corrupted Messages,” Europhysics Letters, Vol. 44, No. 5, 1998, pp. 668-674.
[9]	T. Murayama, Y. Kabashima, D. Saad and R. Vicente, “Statistical Physics of Regular Low-Density Parity-Check Error-Correcting Codes,” Physical Review E, Vol. 62, No. 2, 2000, pp. 1577-1591.
[10]	R. Vicente, D. Saad and Y. Kabashima, “Finite-Connec- tivity Systems as Error-Correcting Codes,” Physical Review E, Vol. 60, No. 5, 1999, pp. 5352-5366.
[11]	J. Chen, A. Dholakia, E. Eleftheriou, M. Fossorier and X. Y. Hu, “Reduced-Complexity Decoding of LDPC Codes,” IEEE Transactions on Communications, Vol. 53, No. 8, 2005, pp. 1288-1299.
[12]	M. Mezard and A. Montanari, “Information, Physics and Computation,” Oxford University Press, Oxford, 2008.
[13]	F. Guilloud, “Generic Architecture for LDPC Codes Decoding,” PhD Thesis, ENST Paris, 2004.
[14]	M. Abdelhedi, O. Hamdi and A. Bouallegue, “Magnetization Performance of LDPC Decoding Algorithms,” International Journal of Information and Coding Theory, 18 March 2010.