Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Journal on Selected Areas in Communications

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

Robert J. McEliece, David Mackay, Jung-Fu Thomas Cheng

Published Jan 1, 1998• 905 citations
Publisher

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.

DOI
10.1109/49.661103

Related papers

Principles and applications of iterative decoding

K.C. Chew

This thesis presents the newly discovered technique to decode a Turbo code. This technique is known to the artificial intelligence community as belief propagation developed by Judea Pearl, but is relatively unknown to the information theorists. It was only recently that researchers found that turbo decoding, or equivalently iterative decoding, is an instance of Pearl's belief propagation algorithm. Literatures have shown that Pearl's algorithm can be used to derive effective iterative decoding algorithms for a number of error control systems like Gallager's low-density parity-check codes, the low-density generator matrix codes, serially concatenated codes and product codes. Belief propagation provides an attractive general method for devising low-complexity iterative decoding algorithms for hybrid systems because of the simplicity in Bayesian network representations of these systems. Coincidentally, the performance of Turbo codes has attained to a level where it is difficult to improvement any much further. More viable is the challenge to devise low-complexity codes that could achieve near capacity performance. Therefore, the study of making used of single-parity check-based tree (SPCT) codes and belief propagation algorithm was motivated. The recently introduced low-complexity "zigzag" codes can be viewed as a subclass of SPCT codes, whose Bayesian networks have the most unbalanced tree structures. This thesis involves preliminary study of other subclasses of SPCT codes. Interesting observations suggest that performance improvement without increasing decoding complexity is theoretically possible.

•Jan 1, 2000•0 citations

Message-Passing Algorithm

Bane Vasic, Erozan M. Kurtas

A growing interest in the theory and application of iterative decoding algorithms was ignited by the impressive bit-error rate performance of the turbo-decoding algorithm demonstrated by Berrou et al. [3]. In the last several years, the turbo decoding algorithm has been generalized and mathematically formulated using a graph-theoretic approach. Such iterative decoding algorithms operate by “messagepassing” in graphs associated with codes and hence, they are referred to as the message-passing algorithms. The theory of codes on graphs has helped to improve the error performance of low-complexity decoding schemes. Also, it has opened new research avenues for investigating alternative suboptimal decoding schemes. One of the key results in the theory of codes on graphs comes from Kschischang et al. [8,9]. They generalized the concept of codes on graphs by introducing the idea of general functions on graphs. They derived a general distributed marginalization algorithm for function described by factor graphs. The theory of factor graphs and the sum-product algorithm generalizes a variety of algorithms developed in computer science and engineering. The belief propagation algorithm, developed by Pearl [14], operating on Bayesian networks is an instance of the sum-product algorithm operating on an appropriate factor graph.

CRC Press eBooks•Nov 9, 2004•2 citations

Information Geometry of Turbo and Low-Density Parity-Check Codes

Shiro Ikeda, Toshiyuki Tanaka, Шун-ичи Амари

Since the proposal of turbo codes in 1993, many studies have appeared on this simple and new type of codes which give a powerful and practical performance of error correction. Although experimental results strongly support the efficacy of turbo codes, further theoretical analysis is necessary, which is not straightforward. It is pointed out that the iterative decoding algorithm of turbo codes shares essentially similar ideas with low-density parity-check (LDPC) codes, with Pearl's belief propagation algorithm applied to a cyclic belief diagram, and with the Bethe approximation in statistical physics. Therefore, the analysis of the turbo decoding algorithm will reveal the mystery of those similar iterative methods. In this paper, we recapture and extend the geometrical framework initiated by Richardson to the information geometrical framework of dual affine connections, focusing on both of the turbo and LDPC decoding algorithms. The framework helps our intuitive understanding of the algorithms and opens a new prospect of further analysis. We reveal some properties of these codes in the proposed framework, including the stability and error analysis. Based on the error analysis, we finally propose a correction term for improving the approximation.

IEEE Transactions on Information Theory•Jun 1, 2004•70 citations

Turbo-Gallager Codes: The Emergence of an Intelligent Coding Scheme

PC Catherine, K. S. Soyjaudah

In 1948, C. Shannon developed fundamental limits on the efficiency of communication over noisy channels. However it is only in 1993 (about half a century later) that Berrou, Glavieux and Thitimajshima developed turbo codes and demonstrated performance close to that limit. Overnight, much of the  algebraic coding techniques of the pre-turbo era were rendered obsolete. Turbo codes employ iterative algorithms and focus on exchange of soft (or probabilistic) information. Shortly after, it was recognised that another class of codes developed by Gallager in 1963 shared all the essential features of turbo codes, including sparse graph-based codes and iterative message-passing decoders. Today, both turbo codes and low-density parity-check codes are largely superior to other code families and are being used in an increasing number of modern communication systems including 3G standards, satellite and deep space communications. However, the two codes have certain distinctive characteristics that differentiate them. This work proposes a blend of the two technologies, yielding a code that we nicknamed Turbo-Gallager or TG Code. The code has additional “intelligence” compared to its parents. It detects and corrects the so-called “undetected errors” and recovers from individual decoder failure by making use of a network of decoders. Keywords : TG codes, message-passing algorithms, low-density parity-check codes, turbo codes, bipartite graphs

University of Mauritius Research Journal•Jan 1, 2007•0 citations

Information geometry for turbo decoding

Shiro Ikeda, Toshiyuki Tanaka, Шун-ичи Амари

Turbo codes are known as a class of error-correcting codes which have high error-correcting performance with efficient decoding algorithm. Characteristics of the iterative decoding algorithm have been studied in detail through a variety of numerical experiments, but theoretical results are still insufficient. In this paper, this issue is addressed from the information geometrical viewpoint. As a result, a mathematical framework for analyzing turbo codes is obtained, and some of the fundamental properties of turbo decoding are elucidated based on this framework. Recently, it has been pointed out that the turbo decoding algorithm is related to the decoding algorithm of low-density parity check codes, the computation method of Bethe approximation in statistical physics, and the belief propagation algorithm of Bayesian networks. The mathematical framework given in the present paper can also be used to analyze these wide classes of iterative computation methods, and hence represent a new analysis tool. © 2004 Wiley Periodicals, Inc. Syst Comp Jpn, 36(1): 79–87, 2005; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.10359

Systems and Computers in Japan•Jan 1, 2004•2 citations

Iterative Decoding of Complex-rotary Codes

Wen Hong, Jin Fan, Fei Hu

Due to its near-optimum decoding for low-density parity check (LDPC) codes and turbo codes, the belief propagation (BP) algorithm has recently received a lot of attention in the coding community. In this paper, the iterative decoding of complex-rotary codes (CRC) based on the belief propagation is researched. The decoding performance of CRC is as good as those of the finite geometry codes and the difference set cyclic codes. A modest performance gain is made over the low density parity check codes with similar parameters. Two new low complexity algorithms for decoding complex-rotary codes are developed. The complexity of the new algorithms is remarkably low in comparison with the BP algorithm.

Journal of the China Railway Society•Jan 1, 2005•0 citations
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.
This thesis presents the newly discovered technique to decode a Turbo code. This technique is known to the artificial intelligence community as belief propagation developed by Judea Pearl, but is relatively unknown to the information theorists. It was only recently that researchers found that turbo decoding, or equivalently iterative decoding, is an instance of Pearl's belief propagation algorithm. Literatures have shown that Pearl's algorithm can be used to derive effective iterative decoding algorithms for a number of error control systems like Gallager's low-density parity-check codes, the low-density generator matrix codes, serially concatenated codes and product codes. Belief propagation provides an attractive general method for devising low-complexity iterative decoding algorithms for hybrid systems because of the simplicity in Bayesian network representations of these systems. Coincidentally, the performance of Turbo codes has attained to a level where it is difficult to improvement any much further. More viable is the challenge to devise low-complexity codes that could achieve near capacity performance. Therefore, the study of making used of single-parity check-based tree (SPCT) codes and belief propagation algorithm was motivated. The recently introduced low-complexity "zigzag" codes can be viewed as a subclass of SPCT codes, whose Bayesian networks have the most unbalanced tree structures. This thesis involves preliminary study of other subclasses of SPCT codes. Interesting observations suggest that performance improvement without increasing decoding complexity is theoretically possible.
A growing interest in the theory and application of iterative decoding algorithms was ignited by the impressive bit-error rate performance of the turbo-decoding algorithm demonstrated by Berrou et al. [3]. In the last several years, the turbo decoding algorithm has been generalized and mathematically formulated using a graph-theoretic approach. Such iterative decoding algorithms operate by “messagepassing” in graphs associated with codes and hence, they are referred to as the message-passing algorithms. The theory of codes on graphs has helped to improve the error performance of low-complexity decoding schemes. Also, it has opened new research avenues for investigating alternative suboptimal decoding schemes. One of the key results in the theory of codes on graphs comes from Kschischang et al. [8,9]. They generalized the concept of codes on graphs by introducing the idea of general functions on graphs. They derived a general distributed marginalization algorithm for function described by factor graphs. The theory of factor graphs and the sum-product algorithm generalizes a variety of algorithms developed in computer science and engineering. The belief propagation algorithm, developed by Pearl [14], operating on Bayesian networks is an instance of the sum-product algorithm operating on an appropriate factor graph.
Since the proposal of turbo codes in 1993, many studies have appeared on this simple and new type of codes which give a powerful and practical performance of error correction. Although experimental results strongly support the efficacy of turbo codes, further theoretical analysis is necessary, which is not straightforward. It is pointed out that the iterative decoding algorithm of turbo codes shares essentially similar ideas with low-density parity-check (LDPC) codes, with Pearl's belief propagation algorithm applied to a cyclic belief diagram, and with the Bethe approximation in statistical physics. Therefore, the analysis of the turbo decoding algorithm will reveal the mystery of those similar iterative methods. In this paper, we recapture and extend the geometrical framework initiated by Richardson to the information geometrical framework of dual affine connections, focusing on both of the turbo and LDPC decoding algorithms. The framework helps our intuitive understanding of the algorithms and opens a new prospect of further analysis. We reveal some properties of these codes in the proposed framework, including the stability and error analysis. Based on the error analysis, we finally propose a correction term for improving the approximation.
In 1948, C. Shannon developed fundamental limits on the efficiency of communication over noisy channels. However it is only in 1993 (about half a century later) that Berrou, Glavieux and Thitimajshima developed turbo codes and demonstrated performance close to that limit. Overnight, much of the  algebraic coding techniques of the pre-turbo era were rendered obsolete. Turbo codes employ iterative algorithms and focus on exchange of soft (or probabilistic) information. Shortly after, it was recognised that another class of codes developed by Gallager in 1963 shared all the essential features of turbo codes, including sparse graph-based codes and iterative message-passing decoders. Today, both turbo codes and low-density parity-check codes are largely superior to other code families and are being used in an increasing number of modern communication systems including 3G standards, satellite and deep space communications. However, the two codes have certain distinctive characteristics that differentiate them. This work proposes a blend of the two technologies, yielding a code that we nicknamed Turbo-Gallager or TG Code. The code has additional “intelligence” compared to its parents. It detects and corrects the so-called “undetected errors” and recovers from individual decoder failure by making use of a network of decoders. Keywords : TG codes, message-passing algorithms, low-density parity-check codes, turbo codes, bipartite graphs
Turbo codes are known as a class of error-correcting codes which have high error-correcting performance with efficient decoding algorithm. Characteristics of the iterative decoding algorithm have been studied in detail through a variety of numerical experiments, but theoretical results are still insufficient. In this paper, this issue is addressed from the information geometrical viewpoint. As a result, a mathematical framework for analyzing turbo codes is obtained, and some of the fundamental properties of turbo decoding are elucidated based on this framework. Recently, it has been pointed out that the turbo decoding algorithm is related to the decoding algorithm of low-density parity check codes, the computation method of Bethe approximation in statistical physics, and the belief propagation algorithm of Bayesian networks. The mathematical framework given in the present paper can also be used to analyze these wide classes of iterative computation methods, and hence represent a new analysis tool. © 2004 Wiley Periodicals, Inc. Syst Comp Jpn, 36(1): 79–87, 2005; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.10359
Due to its near-optimum decoding for low-density parity check (LDPC) codes and turbo codes, the belief propagation (BP) algorithm has recently received a lot of attention in the coding community. In this paper, the iterative decoding of complex-rotary codes (CRC) based on the belief propagation is researched. The decoding performance of CRC is as good as those of the finite geometry codes and the difference set cyclic codes. A modest performance gain is made over the low density parity check codes with similar parameters. Two new low complexity algorithms for decoding complex-rotary codes are developed. The complexity of the new algorithms is remarkably low in comparison with the BP algorithm.