© 1999 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

IEEE Transactions on Communications
Volume 47 Number 5, May 1999

Table of Contents for this issue

Complete paper in PDF format

Reduced Complexity Iterative Decoding of Low-Density Parity Check Codes Based on Belief Propagation

Marc P. C. Fossorier, Member, IEEE, Miodrag Mihaljevic, and Hideki Imai, Fellow, IEEE

Page 673.

Abstract:

In this paper, two simplified versions of the belief propagation algorithm for fast iterative decoding of low-density parity check codes on the additive white Gaussian noise channel are proposed. Both versions are implemented with real additions only, which greatly simplifies the decoding complexity of belief propagation in which products of probabilities have to be computed. Also, these two algorithms do not require any knowledge about the channel characteristics. Both algorithms yield a good performance-complexity tradeoff and can be efficiently implemented in software as well as in hardware, with possibly quantized received values.

References

  1. R. G. Gallager, "Low-density parity-check codes," IRE Trans. Inform. Theory, vol. IT-8, pp. 21-28, Jan. 1968.
  2. --, Low-Density Parity-Check Codes.Cambridge, MA: M.I.T. Press, 1963.
  3. J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference.San Mateo, CA: Morgan Kaufmann, 1988.
  4. J. L. Massey, Threshold Decoding.Cambridge, MA: M.I.T. Press, 1963.
  5. F. R. Kschischang and B. J. Frey, "Iterative decoding of compound codes by probability propagation in graphical models," IEEE J. Select. Areas Commun., vol. 16, pp. 219-230, Feb. 1998.
  6. D. J. C. MacKay and R. M. Neal, "Near shannon limit performance of low density parity check codes," Electron. Lett., vol. 33, pp. 457-458, Mar. 1997.
  7. D. J. C. MacKay, "Good error-correcting codes based on very sparse matrices," IEEE Trans. Inform. Theory, vol. 45, pp. 399-431, Mar. 1999.
  8. R. J. McEliece, D. J. C. MacKay, and J.-F. Cheng, "Turbo decoding as an instance of Pearl's `Belief Propagation' algorithm," IEEE J. Select. Areas Commun., vol. 16, pp. 140-152, Feb. 1998.
  9. G. Battail, "A conceptual framework for understanding turbo codes," IEEE J. Select. Areas Commun., vol. 16, pp. 245-254, Feb. 1998.
  10. J. Hagenauer, E. Offer, and L. Papke, "Iterative decoding of block and convolutional codes," IEEE Trans. Inform. Theory, vol. 42, pp. 429-445, Mar. 1997.
  11. P. Jung, "Novel low complexity decoder for turbo-codes," Electron. Lett., vol. 31, pp. 86-87, Jan. 1995.
  12. R. Lucas, M. Bossert, and M. Breitbach, "On iterative soft-decision decoding of linear binary block codes and product codes," IEEE J. Select. Areas Commun., vol. 16, pp. 276-298, Feb. 1998.
  13. W. Meier and O. Staffelbach, "Fast correlation attacks on certain stream ciphers," J. Cryptol., vol. 1, pp. 159-176, 1989.
  14. M. Mihaljevic, "An iterative probabilistic decoding algorithm for binary linear block codes beyond the half minimum distance," Lecture Notes in Computer Science, Applied Algebra, Algorithms and Error Correcting Codes--AAECC 12, vol. 1255, pp. 237-249, 1997.
  15. H. Nickl, J. Hagenauer, and F. Burkert, "Approaching Shannon's capacity limit by 0.27 dB using simple Hamming codes," IEEE Commun. Lett., vol. 1, pp. 130-132, Sept. 1997.
  16. B. Radosavljevic, E. Arikan, and B. Hajek, "Sequential decoding of low-density parity-check codes by adaptive reordering of parity checks," IEEE Trans. Inform. Theory, vol. 38, pp. 1833-1839, Nov. 1992.
  17. M. Sipser and D. A. Spielman, "Expander codes," IEEE Trans. Inform. Theory, vol. 42, pp. 1710-1722, Nov. 1996.
  18. R. M. Tanner, "A recursive approach to low complexity codes," IEEE Trans. Inform. Theory, vol. IT-27, pp. 533-547, Sept. 1981.
  19. V. D. Kolesnik, "Probability decoding of majority codes," Prob. Peredachi Inform., vol. 7, pp. 3-12, July 1971.
  20. D. J. C. MacKay and C. P. Hesketh, "Performance of low density parity check codes as a function of actual and assumed noise levels," IEEE Trans. Commun., to be published.
  21. J. Snyders, "Reduced lists of error patterns for maximum likelihood soft decoding," IEEE Trans. Inform. Theory, vol. IT-37, pp. 1194-1200, July 1991.
  22. B. G. Dorsch, "A decoding algorithm for binary block codes and J-ary output channels," IEEE Trans. Inform. Theory, vol. IT-20, pp. 391-394, May 1974.
  23. S. S. Pietrobon, "Implementation and performance of a serial MAP decoder for use in an iterative turbo decoder," in Proc. IEEE Int. Symp. Information Theory, Whistler, B.C., Canada, Sept. 1995, p. 471.
  24. P. Robertson, E. Villebrun, and P. Hoeher, "A comparison of optimal and sub-optimal decoding algorithms in the log domain," in Proc. ICC, Seattle, USA, June 1995, pp. 1009-1013.
  25. A. J. Viterbi, "An intuitive justification and a simplified implementation of the MAP decoder for convolutional codes," IEEE J. Select. Areas Commun., vol. 16, pp. 260-264, Feb. 1998.