Abstract

July 3 - 10.50-11.40
S.Ikeda, T. Tanaka, S. Amari - Information Geometry of Turbo Codes and Low-density Parity-Check Codes

Since the proposal of turbo codes in 1993, many studies have appeared on this simple and new error correcting codes which give a powerful and practical method for error correction. The essential point of turbo codes is their iterative decoding algorithm, however, the main properties of the decoding algorithm which have been so far obtained are mostly empirical. The essence of the turbo decoding has not been fully understood theoretically. Except for the experimental studies, a clue has been sought in other iterative methods, which are closely related to turbo codes. One of the methods is another class of error correcting codes called low-density parity-check (LDPC) codes, which was originally proposed by Gallager in 1960's. Related ideas are found even in different fields, one is in artificial intelligence and another in statistical physics. McEliece et al. showed that the turbo decoding algorithm is equivalent to the belief propagation, applied to a belief diagram with loops, MacKay showed that LDPC codes are also equivalent to the belief propagation, while Kabashima and Saad showed that the iterative process of Bethe approximation in statistical physics is the same as that of the belief propagation. However, the efficiencies of these methods are also a sort of mystery, and they didn't help us clarify the mathematical structure of turbo codes. In this presentation, we focus on the turbo and the LDPC decoding and investigate the mathematical structure of the iterative decoding methods from the information geometrical viewpoint. We first formulate the problem of the error correcting codes as an m--projection of a given distribution to an e--flat submanifold which consists of factorizable distributions. Since the exact m--projection is usually computationally intractable, it is approximated through iterative algorithms. We also express the turbo and the LDPC decoding algorithm as the combination of an m--projection and an e--projection. [an error occurred while processing this directive]