Principles and applications of iterative decoding

Abstract

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.