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.
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.
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.
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.
Since the invention of turbo codes, there has been an explosion of interest in iterative decoding and graphical representation of codes. This thesis examines the iterative decoding of codes defined on graphs with cycles, which appears to be an efficient means of achieving the Shannon limit. Much of this analysis is on the iterative min-sum decoding of tail-biting codes and cycle codes. We have identified the pseudocodeword as the cause of the suboptimal performance of the iterative decoder, and we have obtained a union bound for the performance of the iterative decoder on both AWGN and BSC channels. Using the union bound argument, for cycle codes, we have shown that the performance of the iterative decoder is asymptotically as good as that of the ML decoder. As for tail-biting codes, the same thing is true if the lowest weight pseudocodeword is at least the minimum weight of the code. Unfortunately, the analysis of tail-biting codes and cycle codes does not extend to turbo codes and low density parity check codes in general. Our next approach is to determine the average behavior of message passing algorithms by studying the evolution of their "message" densities. For the class of "repeat and accumulate" serially concatenated turbo-like codes, we have devised an algorithm for determining their "threshold" values. When the signal-to-noise ratio is larger than the threshold value, the error probabilities of message passing algorithms approach zero, whereas if the signal-to-noise ratio is less than the threshold value, the error probability stays bounded away from zero. Some message passing algorithms and graphical representation of codes are efficient means of devising ML or MAP decoding algorithms. We have proposed a junction tree representation for linear block codes, and we have shown that the minimum junction tree can be less complex than the minimal trellis.
At the heart of modern coding theory lies the fact that low-density parity-check (LDPC) codes can be efficiently decoded by belief propagation (BP). The BP is an inference algorithm which operates on a graphical model of a code, and lends itself to low-complexity and high-speed implementations, making it the algorithm of choice in many applications. It has unprecedentedly good error rate performance, so good that when decoded by the BP, LDPC codes approach theoretical limits of channel capacity. However, this capacity approaching property holds only in the asymptotic limit of code length, while codes of practical lengths suffer abrupt performance degradation in the low noise regime known as the error floor phenomenon. Our study of error floor has led to an interesting and surprising finding that it is possible to design iterative decoders which are much simpler yet better than belief propagation! These decoders do not propagate beliefs but a rather different kind of messages that reflect the local structure of the code graph. This has opened a plethora of exciting theoretical problems and applications. This paper introduces this new paradigm.