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 International Symposium on Information Theory (ISIT)

On the convergence of the iterated decoding algorithm

Giuseppe Caire, Giorgio Taricco, E. Biglieri

Published Nov 19, 2002• 7 citations
Publisher

Abstract

The concept of iterated decoding of concatenated codes has been developed. Successful applications of this concept include turbo-codes and soft-decoding of product codes. After stating the iterated decoding algorithm formally, we provide a conjecture on the convergence and the asymptotic optimality of this algorithm.
DOI
10.1109/isit.1995.550459

Related papers

Convergence analysis of turbo decoding of product codes

Assaf Sella, Yair Be'ery

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.

IEEE Transactions on Information Theory•Jan 1, 2001•39 citations

On iterative soft-decision decoding of linear binary block codes and product codes

R. Lucas, Martin Bossert, Markus Breitbach

Iterative decoding methods have gained interest, initiated by the results of the so-called "turbo" codes. The theoretical description of this decoding, however, seems to be difficult. Therefore, we study the iterative decoding of block codes. First, we discuss the iterative decoding algorithms developed by Gallager (1962), Battail et al. (1979), and Hagenauer et al. (1996). Based on their results, we propose a decoding algorithm which only uses parity check vectors of minimum weight. We give the relation of this iterative decoding to one-step majority-logic decoding, and interpret it as gradient optimization. It is shown that the used parity check set defines the region where the iterative decoding decides on a particular codeword. We make plausible that, in almost all cases, the iterative decoding converges to a codeword after some iterations. We derive a computationally efficient implementation using the minimal trellis representing the used parity check set. Simulations illustrate that our algorithm gives results close to soft decision maximum likelihood (SDML) decoding for many code classes like BCH codes. Reed-Muller codes, quadratic residue codes, double circulant codes, and cyclic finite geometry codes. We also present simulation results for product codes and parallel concatenated codes based on block codes.

IEEE Journal on Selected Areas in Communications•Jan 1, 1998•100 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

On decoding iterated codes

Sudhakar M. Reddy

Algorithms to decode iterated codes when at least one of the "component codes" is majority decodable are given. The decoding algorithms allow the use of the decoders of the component codes and still make it possible to correct all error patterns guaranteed to be correctable by the minimum distance of the iterated code.

IEEE Transactions on Information Theory•Sep 1, 1970•33 citations

Convergence Analysis of Iterative Threshold Decoding Process

Mohammed Lahmer, Mostafa Belkasmi, Abdallah Rhattoy

Today the error correcting codes are present in all the telecom standards, in particular the low density parity check (LDPC) codes. The choice of a good code for a given network is essentially linked to the decoding performance obtained by the bit error rate (BER) curves. This approach requires a significant simulation time proportional to the length of the code, to overcome this problem Exit chart was introduced, as a fast technique to predict the performance of a particular class of codes called Turbo codes. In this paper, we success to apply Exit chart to analyze convergence behavior of iterative threshold decoding of one step majority logic decodable (OSMLD) codes. The iterative decoding process uses a soft-input soft-output threshold decoding algorithm as component decoder. Simulation results for iterative decoding of simple and concatenated codes transmitted over a Gaussian channel have shown that the thresholds obtained are a good indicator of the Bit Error Rate (BER) curves.

Journal of Computer and Communications•Jan 1, 2016•1 citation

On the suboptimality of iterative decoding for finite length codes

Motohiko Isaka, M.P.C. Fossorier, H. Imai

We investigate the property of iterative decoding for finite length codes, and give some insights on the suboptimality of iterative decoding due to the cycles in the graph representation of the codes, for several different types of iteratively decodable codes.

IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2003•3 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.
Iterative decoding methods have gained interest, initiated by the results of the so-called "turbo" codes. The theoretical description of this decoding, however, seems to be difficult. Therefore, we study the iterative decoding of block codes. First, we discuss the iterative decoding algorithms developed by Gallager (1962), Battail et al. (1979), and Hagenauer et al. (1996). Based on their results, we propose a decoding algorithm which only uses parity check vectors of minimum weight. We give the relation of this iterative decoding to one-step majority-logic decoding, and interpret it as gradient optimization. It is shown that the used parity check set defines the region where the iterative decoding decides on a particular codeword. We make plausible that, in almost all cases, the iterative decoding converges to a codeword after some iterations. We derive a computationally efficient implementation using the minimal trellis representing the used parity check set. Simulations illustrate that our algorithm gives results close to soft decision maximum likelihood (SDML) decoding for many code classes like BCH codes. Reed-Muller codes, quadratic residue codes, double circulant codes, and cyclic finite geometry codes. We also present simulation results for product codes and parallel concatenated codes based on block codes.
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.
Today the error correcting codes are present in all the telecom standards, in particular the low density parity check (LDPC) codes. The choice of a good code for a given network is essentially linked to the decoding performance obtained by the bit error rate (BER) curves. This approach requires a significant simulation time proportional to the length of the code, to overcome this problem Exit chart was introduced, as a fast technique to predict the performance of a particular class of codes called Turbo codes. In this paper, we success to apply Exit chart to analyze convergence behavior of iterative threshold decoding of one step majority logic decodable (OSMLD) codes. The iterative decoding process uses a soft-input soft-output threshold decoding algorithm as component decoder. Simulation results for iterative decoding of simple and concatenated codes transmitted over a Gaussian channel have shown that the thresholds obtained are a good indicator of the Bit Error Rate (BER) curves.