CaltechAUTHORS
  A Caltech Library Service

Turbo decoding as an instance of Pearl's “belief propagation” algorithm

McEliece, Robert J. and MacKay, David J. C. and Cheng, Jung-Fu (1998) Turbo decoding as an instance of Pearl's “belief propagation” algorithm. IEEE Journal on Selected Areas in Communications, 16 (2). pp. 140-152. ISSN 0733-8716. http://resolver.caltech.edu/CaltechAUTHORS:MCEieeejsac98

[img]
Preview
PDF
See Usage Policy.

491Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:MCEieeejsac98

Abstract

We describe the close connection between the now celebrated iterative turbo decoding algorithm of Berrou et al. (1993) and an algorithm that has been well known in the artificial intelligence community for a decade, but which is relatively unknown to information theorists: Pearl's (1982) belief propagation algorithm. We see that if Pearl's algorithm is applied to the “belief network” of a parallel concatenation of two or more codes, the turbo decoding algorithm immediately results. Unfortunately, however, this belief diagram has loops, and Pearl only proved that his algorithm works when there are no loops, so an explanation of the experimental performance of turbo decoding is still lacking. However, we also show that Pearl's algorithm can be used to routinely derive previously known iterative, but suboptimal, decoding algorithms for a number of other error-control systems, including Gallager's (1962) low-density parity-check codes, serially concatenated codes, and product codes. Thus, belief propagation provides a very attractive general methodology for devising low-complexity iterative decoding algorithms for hybrid coded systems.


Item Type:Article
Additional Information:© Copyright 1998 IEEE. Reprinted with permission. Manuscript received September 27, 1996; revised May 3, 1997. This work was supported by NSF Grant NCR-9505975, AFOSR Grant 5F49620-97-1-0313, and a grant from Qualcomm, Inc. A portion of R. J. McEliece’s contribution was done while he was visiting the Sony Corporation in Tokyo. The collaboration between D. J. C. MacKay and R. J. McEliece was begun at, and partially supported by, the Newton Institute for Mathematical Sciences, Cambridge, U.K. The authors wish to thank P. Smyth for apprising them about the “post-Pearl” developments in the belief propagation algorithm, and one of the referees for supplying them with much of the history of the forward–backward algorithm that appears in Section IV.
Subject Keywords:Belief propagation, error-correcting codes, iterative decoding, Pearl’s Algorithm, probabilistic inference, turbo codes
Record Number:CaltechAUTHORS:MCEieeejsac98
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:MCEieeejsac98
Alternative URL:http://dx.doi.org/10.1109/49.661103
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6938
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:03 Jan 2007
Last Modified:26 Dec 2012 09:27

Repository Staff Only: item control page