IEEE Transactions on Information Theory

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

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

Published Jun 1, 2004• 70 citations

Abstract

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.

DOI: 10.1109/tit.2004.828072

Related papers

Information geometry of turbo and LDPC codes

Shiro Ikeda

Turbo and LDPC (low-density parity check) codes are simple and new types of error correction codes which give a powerful and practical performance of error correction. Although experimental results show their efficacy, further theoretical analysis is necessary, which is not straightforward. We have built a unified framework of turbo and LDPC codes based on information geometry. The framework helps our intuitive understanding of the codes and opens a new prospect of further analysis. We have revealed some properties of these codes in the proposed framework. This paper summarizes the results.

IEEE International Conference on Acoustics Speech and Signal ProcessingOct 4, 20063 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 JapanJan 1, 20042 citations

The Decoding Algorithms For Error-Correcting Product Codes Based On Project Geometry Low-Density Parity-Check Codes

Назаров Лев Евгеньевич

The focus of this paper is directed towards the investigation of the characteristics of symbol-by-symbol iterative decoding algorithms for error-correcting block product-codes (block turbo-codes) which enable to reliable information transfer at relatively low received signal/noise and provide high power efficiency. Specific feature of investigated product codes is construction with usage of low-density parity-check codes (LDPC) and these code constructions are in the class of LDPC too. According to this fact the considered code constructions have symbol-by-symbol decoding algorithms developed for total class LDPC codes, namely BP (belief propagation) and its modification MIN_SUM_BP. The BP decoding algorithm is iterative and for implementation the signal/noise is required, for implementation of MIN_SUM_BP decoding algorithm the signal/noise is not required. The resulted characteristics of product codes constructed with usage of LDPC based on project geometry (length of code words, information volume, code rate, error performances) are presented in this paper. These component LDPC codes are cyclic and have encoding and decoding algorithms with low complexity implementation. The computer simulations for encoding and iterative symbol-by-symbol decoding algorithms for the number of turbo-codes with different code rate and information volumes are performed. The results of computer simulations have shown that MIN_SUM_BP decoding algorithm is more effective than BP decoding algorithm for channel with additive white gaussian noise concerning error-performances.

Radioelectronics Nanosystems Information TechnologiesOct 30, 20200 citations

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

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

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.

IEEE Journal on Selected Areas in CommunicationsJan 1, 1998905 citations

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, 20000 citations

Comparative Analysis of Belief Propagation and Layered Decoding Algorithms for LDPC Codes

E Channaveeramma, K. M. Palaniswamy

Wireless digital communication enables instantaneous connections and conversations between people all over the world. In a digital communication system, the channel code is used to detect and fix errors. The most widely used error-correcting codes are LDPC channel codes, which are represented by a sparse parity-check matrix and have performance close to the Shannon limit. The sophistication and versatility of decoders determines the error-correcting codes' efficacy. LDPC codes are used in a wide variety of broadcasting, satellite communication, LAN, and PAN applications because of their capacity-approaching properties. Sparsity allows for the use of LDPC codes; however, simplified decoding algorithms play a crucial role in achieving high-speed, error-free communication. In this work, we focus on locating a decoding algorithm with the lowest possible complexity and the fewest possible iterations. The belief propagation algorithm and layered decoding or turbo decoding algorithms are with the code rates ½, ¾,5/8, and 13/16, which are compatible with the WLAN (IEEE Std 802.11™-2016 (Revision of IEEE Std 802.11-2012, 2012) standard. In terms of bit error rate, layered decoding or turbo decoding of the message forwarding method performs better. It is also seen that performance improves with an increase in the number of iterations.

Advances in computational intelligence and robotics book seriesMay 20, 20240 citations