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 Transactions on Information Theory

Convergence analysis of turbo decoding of product codes

Assaf Sella, Yair Be'ery

Published Jan 1, 2001• 39 citations
Publisher

Abstract

Geometric interpretation of turbo decoding has founded an analytical basis, and provided tools for the analysis of this algorithm. We focus on turbo decoding of product codes, and based on the geometric framework, we extend the analytical results and show how analysis tools can be practically adapted for this case. Specifically, we investigate the algorithm's stability and its convergence rate. We present new results concerning the structure and properties of stability matrices of the algorithm, and develop upper bounds on the algorithm's convergence rate. We prove that for any 2/spl times/2 (information bits) product codes, there is a unique and stable fixed point. For the general case, we present sufficient conditions for stability. The interpretation of these conditions provides an insight to the behavior of the decoding algorithm. Simulation results, which support and extend the theoretical analysis, are presented for Hamming [(7,4,3)]/sup 2/ and Golay [(24,12,8)]/sup 2/ product codes.

DOI
10.1109/18.910584

Related papers

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

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

A method for convergence analysis of iterative probabilistic decoding

Miodrag J. Mihaljević, Jovan Dj. Golić

A novel analytical approach to performance evaluation of soft-decoding algorithms for binary linear block codes based on probabilistic iterative error correction is presented. A convergence condition establishing the critical noise rate below which the expected bit-error probability tends to zero is theoretically derived. It explains the capability of iterative probabilistic decoding of binary linear block codes with sparse parity-check matrices to correct, with probability close to one, error patterns with the number of errors (far) beyond half the code minimum distance. Systematic experiments conducted on truncated simplex codes seem to agree well with the convergence condition. The method may also be interesting for the theoretical analysis of the so-called turbo codes.

IEEE Transactions on Information Theory•Jan 1, 2000•15 citations

Iterative decoding and pseudo-codewords

Gavin Bernard Horn

In the last six years, we have witnessed an explosion of interest in the coding theory community, in iterative decoding and graphical models, due primarily to the invention of turbo codes. While the structural properties of turbo codes and low density parity check codes have now been put on a firm theoretical footing, what is still lacking is a satisfactory theoretical explanation as to why iterative decoding algorithms perform as well as they do. In this thesis we make a first step by discussing the behavior of various iterative decoders for the graphs of tail-biting codes and cycle codes. By increasing our understanding of the behavior of the iterative min-sum (MSA) and sum-product (SPA) algorithms on graphs with cycles, we can design codes which achieve better performance. Much of this thesis is devoted to the analysis of the performance of the MSA and SPA on the graphs for tail-biting codes and cycle codes. We give sufficient conditions for the MSA to converge to the maximum likelihood codeword after a finite number of iterations. We also use the familiar union bound argument to characterize the performance of the MSA after many iterations. For a cycle code, we show that the performance of the MSA decoder is asymptotically as good as maximum likelihood. For tail-biting codes this will depend on our choice of trellis.

•Jan 1, 1999•17 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 Technologies•Oct 30, 2020•0 citations

Decoding Turbo Codes Based on Their Parity-Check Matrices

Fan Jiang, Eric T. Psota, Lance C. Pérez

The turbo iterative decoding algorithm only performs well for turbo codes with relatively small memories. Moreover, its decoding complexity becomes prohibitively large when the turbo encoders have very large memories. The sum-product and linear programming decoding algorithms are based on the parity-check matrices of the codes. They are widely used to decode low-density parity-check codes. These algorithms do not suffer the limitations of the turbo iterative decoding algorithm. In order to apply them to the turbo codes, the parity-check matrices of turbo codes must be found. By treating turbo codes as serially concatenated codes, the generator and parity-check matrices of the turbo codes are derived in this paper. Turbo codes with low-density parity-check matrices are then designed based on the derived results. Provided these matrices, turbo codes are decoded using the sum-product algorithms. Preliminary results show that the sum-product decoding of turbo codes performs slightly worse than sum-product decoding of conventional low-density parity-check codes. However, since the encoding of turbo codes has less complexity than the straightforward encoding of low-density parity-check codes, this loss in performance may be justified by the drastically decreased encoding complexity. The availability of the parity-check matrices of turbo codes also makes them ready to be decoded by the linear programming decoding algorithm which is optimum for the given linear constraints.

Southeastern Symposium on System Theory (SSST)•Mar 1, 2007•2 citations
Geometric interpretation of turbo decoding has founded an analytical basis, and provided tools for the analysis of this algorithm. We focus on turbo decoding of product codes, and based on the geometric framework, we extend the analytical results and show how analysis tools can be practically adapted for this case. Specifically, we investigate the algorithm's stability and its convergence rate. We present new results concerning the structure and properties of stability matrices of the algorithm, and develop upper bounds on the algorithm's convergence rate. We prove that for any 2/spl times/2 (information bits) product codes, there is a unique and stable fixed point. For the general case, we present sufficient conditions for stability. The interpretation of these conditions provides an insight to the behavior of the decoding algorithm. Simulation results, which support and extend the theoretical analysis, are presented for Hamming [(7,4,3)]/sup 2/ and Golay [(24,12,8)]/sup 2/ product codes.
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
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.
A novel analytical approach to performance evaluation of soft-decoding algorithms for binary linear block codes based on probabilistic iterative error correction is presented. A convergence condition establishing the critical noise rate below which the expected bit-error probability tends to zero is theoretically derived. It explains the capability of iterative probabilistic decoding of binary linear block codes with sparse parity-check matrices to correct, with probability close to one, error patterns with the number of errors (far) beyond half the code minimum distance. Systematic experiments conducted on truncated simplex codes seem to agree well with the convergence condition. The method may also be interesting for the theoretical analysis of the so-called turbo codes.
In the last six years, we have witnessed an explosion of interest in the coding theory community, in iterative decoding and graphical models, due primarily to the invention of turbo codes. While the structural properties of turbo codes and low density parity check codes have now been put on a firm theoretical footing, what is still lacking is a satisfactory theoretical explanation as to why iterative decoding algorithms perform as well as they do. In this thesis we make a first step by discussing the behavior of various iterative decoders for the graphs of tail-biting codes and cycle codes. By increasing our understanding of the behavior of the iterative min-sum (MSA) and sum-product (SPA) algorithms on graphs with cycles, we can design codes which achieve better performance. Much of this thesis is devoted to the analysis of the performance of the MSA and SPA on the graphs for tail-biting codes and cycle codes. We give sufficient conditions for the MSA to converge to the maximum likelihood codeword after a finite number of iterations. We also use the familiar union bound argument to characterize the performance of the MSA after many iterations. For a cycle code, we show that the performance of the MSA decoder is asymptotically as good as maximum likelihood. For tail-biting codes this will depend on our choice of trellis.
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.
The turbo iterative decoding algorithm only performs well for turbo codes with relatively small memories. Moreover, its decoding complexity becomes prohibitively large when the turbo encoders have very large memories. The sum-product and linear programming decoding algorithms are based on the parity-check matrices of the codes. They are widely used to decode low-density parity-check codes. These algorithms do not suffer the limitations of the turbo iterative decoding algorithm. In order to apply them to the turbo codes, the parity-check matrices of turbo codes must be found. By treating turbo codes as serially concatenated codes, the generator and parity-check matrices of the turbo codes are derived in this paper. Turbo codes with low-density parity-check matrices are then designed based on the derived results. Provided these matrices, turbo codes are decoded using the sum-product algorithms. Preliminary results show that the sum-product decoding of turbo codes performs slightly worse than sum-product decoding of conventional low-density parity-check codes. However, since the encoding of turbo codes has less complexity than the straightforward encoding of low-density parity-check codes, this loss in performance may be justified by the drastically decreased encoding complexity. The availability of the parity-check matrices of turbo codes also makes them ready to be decoded by the linear programming decoding algorithm which is optimum for the given linear constraints.