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)

The least stringent sufficient condition on the optimality of suboptimally decoded codewords

Tadao Kasami, Takuya Koumoto, T. Takata, Toru Fujiwara, Shu Lin

Published Nov 19, 2002• 9 citations
Publisher

Abstract

The number of iterations of an iterative optimal or suboptimal decoding scheme for binary linear block codes without any effect on its error performance can be reduced by testing a sufficient condition on the optimality of a candidate codeword. The least stringent sufficient condition on the optimality of a decoded codeword is investigated under the assumption that the available information on the code is restricted to (1) the minimum weight or the distance profile and (2) for a given positive integer h, h or fewer already generated candidate codewords. The least stringent sufficient conditions of optimality for 1/spl les/h/spl les/3 are presented. Cond/sub 1/ is the same as the one given by Taipale and Pursley (1991), Cond/sub 2/ is less stringent than the one given by Kaneko, Nishijima, Inazumi and Hirasawa (see IEEE Trans. Inform. Theory, vol.IT-40, no.3, p.320, 1994), and Cond/sub 1/ and Cond/sub 2/ are derived from Cond/sub 3/ as special cases. These conditions can be used effectively to save computer simulation time for evaluating the error probability for maximum likelihood decoding.

DOI
10.1109/isit.1995.550457

Related papers

Study on Iterative Soft-Decision Decoding Algorithms for Binary Linear Block Codes

卓也 甲本

For iterative soft-decision decoding algorithms for binary linear block codes, error performance and computational complexity are very important factors.In this thesis, suÆcient conditions of the optimality of decoded codeword and a suÆcient condition which is used for ruling-out some useless iterations of bounded distance decoding which reduces the computational complexity of iterative soft-decision decoding algorithms are shown.New iterative soft-decision decoding algorithms which uses the suÆcient conditions of the optimality of decoded codeword to achievegood error performance with small computational complexity are also shown.First, the suÆcient conditions are derived based on: (1) partial knowledge of the distance pro le of the code, and (2) previously generated candidate codewords.When the numberof previously generated candidate codewords is greater than 1, the conditions presented here are less stringent than those derived by Taipale and Pursley [4] and Kaneko et.al.[5].The condition based on three previously generated candidate codewords is the rst such s u Æ c i e n t condition that has ever been derived.It is shown by computer simulation that these suÆcient condions reduce the computational complexity of iterative decoding algorithms without degradation of error performance.Second, a suÆcient condition to rule-out some useless test error patterns is derived.In an iterative decoding algorithm, such as Chase Type-II decoding algorithm[2] and its improved versions, candidate codewords for a received vector are generated

•Mar 24, 1999•1 citation

An improvement to GMD-like decoding algorithms

H. Tokushiga, Takuya Koumoto, Tadao Kasami

For binary linear block codes, we introduce a multiple generalized minimum distance (GMD) decoding algorithm, where GMD-like decoding is iterated around a few appropriately selected search centers. Compared with the original GMD decoding by Forney (1966), this decoding algorithm provides better error performance by increasing the number of iterations of erasure and error correction moderately. To reduce the number of iterations, we derive new effective sufficient conditions on the optimality of decoded codewords.

IEEE International Symposium on Information Theory (ISIT)•Nov 7, 2002•2 citations

Optimal information bit decoding of linear block codes

Aaron B. Kiely, J.T. Coffey, Mark R. Bell

We consider the problem of decoding a linear block code used over a binary symmetric channel with crossover probability p when the goal of the decoding is to minimize the probability of an information bit error. In general, there will be several different decoding strategies, each corresponding to the optimal rule over some range p/spl isin/[p/sub i-1/, p/sub i/]. Each of these strategies can be implemented by standard array with the appropriate choice of coset leaders that are not in general of minimum weight. We give optimal rules for selecting coset leaders in the first region [0, p/sub 1/] and the region [p/sub max/, 1/2] for any linear mapping between information bits and codewords. The determination of the optimal rule has been an open problem for small p. The rule for p>p/sub max/ is important because for many codes, when p is fixed the optimal rule for any coset corresponds to either the optimal rule for small p, or the optimal rule for p near 1/2. The optimal decoding strategy varies with the generator matrix used in general, but it is demonstrated that the optimal generator matrix is separable when d/sup /spl perp//>2. The results are shown to extend in a natural way to the case where the goal is to minimize the probability that arbitrary collections of information bits are in error. We examine some specific codes, and compare the performance under optimal decoding to the performance of previously suggested strategies.>

IEEE Transactions on Information Theory•Jan 1, 1995•11 citations

A low-weight trellis-based iterative soft-decision decoding algorithm for binary linear block codes

Takuya Koumoto, T. Takata, Tadao Kasami +1 more

This paper presents a new low-weight trellis-based soft-decision iterative decoding algorithm for binary linear block codes. The algorithm is devised based on a set of optimality conditions and the generation of a sequence of candidate codewords for an optimality test. The initial candidate codeword is generated by a simple decoding method. The subsequent candidate codewords, if needed, are generated by a chain of low-weight trellis searches, one at a time. Each search is conducted through a low-weight trellis diagram centered around the latest candidate codeword and results in an improvement over the previous candidate codewords that have been already tested. This improvement is then used as the next candidate codeword for a test of optimality. The decoding iteration stops whenever a candidate codeword is found to satisfy a sufficient condition on optimality or the latest low-weight trellis search results in a repetition of a previously generated candidate codeword. A divide-and-conquer technique is also presented for codes that are not spanned by their minimum-weight codewords. The proposed decoding algorithm has been applied to some well-known codes of lengths 48, 64, and 128. Simulation results show that the proposed algorithm achieves either practically optimal error performance for the example codes of length 48 and 64 or near optimal error performance for the (128, 29, 32) RM code with a significant reduction in computational decoding complexity.

IEEE Transactions on Information Theory•Mar 1, 1999•13 citations

Hierarchies of Local-Optimality Characterizations in Decoding of Tanner Codes

Nissim Halabi, Guy Even

Recent developments in decoding of Tanner codes with maximum-likelihood certificates are based on a sufficient condition called local-optimality. We define hierarchies of locally-optimal codewords with respect to two parameters. One parameter is related to the minimum distance of the local codes in Tanner codes. The second parameter is related to the finite number of iterations used in iterative decoding. We show that these hierarchies satisfy inclusion properties as these parameters are increased. In particular, this implies that a codeword that is decoded with a certificate using an iterative decoder after $h$ iterations is decoded with a certificate after $k\cdot h$ iterations, for every integer $k$.

arXiv:1202.2251•Feb 10, 2012•0 citations

Performance of Error-Control Codes

Richard E. Blahut

In any engineering discipline, one looks for methods of solving a given class of problems and then for methods of quantifying the performance and complexity of those solutions. Accordingly, in this chapter, we shall study performance in terms of the composition structure of block codes, and the probabilities of decoding error and of decoding failure. Later, after satisfactory methods are in hand, one turns to questions of optimality. Are these methods the best methods, and if not, in what ways and by how much are they inferior? To answer such questions, one needs to know how good are the known codes and how good are the best possible codes. Generally, we cannot answer either of these questions satisfactorily. Although for any given rate and blocklength, not too small, the best possible code is not known, a number of bounds are known – bounds beyond which no codes can exist, and bounds within which codes are sure to exist. We shall give some such bounds on the best possible codes later in this chapter. Knowledge of these bounds can deepen our understanding of the subject. Weight distributions of block codes If a linear block code has a minimum distance d min , then we know that at least one codeword of weight d min exists. Sometimes, we are not content with this single piece of information; we wish to know how many codewords have weight d min , and what are the weights of the other codewords.

Cambridge University Press eBooks•Feb 6, 2003•0 citations
The number of iterations of an iterative optimal or suboptimal decoding scheme for binary linear block codes without any effect on its error performance can be reduced by testing a sufficient condition on the optimality of a candidate codeword. The least stringent sufficient condition on the optimality of a decoded codeword is investigated under the assumption that the available information on the code is restricted to (1) the minimum weight or the distance profile and (2) for a given positive integer h, h or fewer already generated candidate codewords. The least stringent sufficient conditions of optimality for 1/spl les/h/spl les/3 are presented. Cond/sub 1/ is the same as the one given by Taipale and Pursley (1991), Cond/sub 2/ is less stringent than the one given by Kaneko, Nishijima, Inazumi and Hirasawa (see IEEE Trans. Inform. Theory, vol.IT-40, no.3, p.320, 1994), and Cond/sub 1/ and Cond/sub 2/ are derived from Cond/sub 3/ as special cases. These conditions can be used effectively to save computer simulation time for evaluating the error probability for maximum likelihood decoding.
For iterative soft-decision decoding algorithms for binary linear block codes, error performance and computational complexity are very important factors.In this thesis, suÆcient conditions of the optimality of decoded codeword and a suÆcient condition which is used for ruling-out some useless iterations of bounded distance decoding which reduces the computational complexity of iterative soft-decision decoding algorithms are shown.New iterative soft-decision decoding algorithms which uses the suÆcient conditions of the optimality of decoded codeword to achievegood error performance with small computational complexity are also shown.First, the suÆcient conditions are derived based on: (1) partial knowledge of the distance pro le of the code, and (2) previously generated candidate codewords.When the numberof previously generated candidate codewords is greater than 1, the conditions presented here are less stringent than those derived by Taipale and Pursley [4] and Kaneko et.al.[5].The condition based on three previously generated candidate codewords is the rst such s u Æ c i e n t condition that has ever been derived.It is shown by computer simulation that these suÆcient condions reduce the computational complexity of iterative decoding algorithms without degradation of error performance.Second, a suÆcient condition to rule-out some useless test error patterns is derived.In an iterative decoding algorithm, such as Chase Type-II decoding algorithm[2] and its improved versions, candidate codewords for a received vector are generated
For binary linear block codes, we introduce a multiple generalized minimum distance (GMD) decoding algorithm, where GMD-like decoding is iterated around a few appropriately selected search centers. Compared with the original GMD decoding by Forney (1966), this decoding algorithm provides better error performance by increasing the number of iterations of erasure and error correction moderately. To reduce the number of iterations, we derive new effective sufficient conditions on the optimality of decoded codewords.
We consider the problem of decoding a linear block code used over a binary symmetric channel with crossover probability p when the goal of the decoding is to minimize the probability of an information bit error. In general, there will be several different decoding strategies, each corresponding to the optimal rule over some range p/spl isin/[p/sub i-1/, p/sub i/]. Each of these strategies can be implemented by standard array with the appropriate choice of coset leaders that are not in general of minimum weight. We give optimal rules for selecting coset leaders in the first region [0, p/sub 1/] and the region [p/sub max/, 1/2] for any linear mapping between information bits and codewords. The determination of the optimal rule has been an open problem for small p. The rule for p>p/sub max/ is important because for many codes, when p is fixed the optimal rule for any coset corresponds to either the optimal rule for small p, or the optimal rule for p near 1/2. The optimal decoding strategy varies with the generator matrix used in general, but it is demonstrated that the optimal generator matrix is separable when d/sup /spl perp//>2. The results are shown to extend in a natural way to the case where the goal is to minimize the probability that arbitrary collections of information bits are in error. We examine some specific codes, and compare the performance under optimal decoding to the performance of previously suggested strategies.>
This paper presents a new low-weight trellis-based soft-decision iterative decoding algorithm for binary linear block codes. The algorithm is devised based on a set of optimality conditions and the generation of a sequence of candidate codewords for an optimality test. The initial candidate codeword is generated by a simple decoding method. The subsequent candidate codewords, if needed, are generated by a chain of low-weight trellis searches, one at a time. Each search is conducted through a low-weight trellis diagram centered around the latest candidate codeword and results in an improvement over the previous candidate codewords that have been already tested. This improvement is then used as the next candidate codeword for a test of optimality. The decoding iteration stops whenever a candidate codeword is found to satisfy a sufficient condition on optimality or the latest low-weight trellis search results in a repetition of a previously generated candidate codeword. A divide-and-conquer technique is also presented for codes that are not spanned by their minimum-weight codewords. The proposed decoding algorithm has been applied to some well-known codes of lengths 48, 64, and 128. Simulation results show that the proposed algorithm achieves either practically optimal error performance for the example codes of length 48 and 64 or near optimal error performance for the (128, 29, 32) RM code with a significant reduction in computational decoding complexity.
Recent developments in decoding of Tanner codes with maximum-likelihood certificates are based on a sufficient condition called local-optimality. We define hierarchies of locally-optimal codewords with respect to two parameters. One parameter is related to the minimum distance of the local codes in Tanner codes. The second parameter is related to the finite number of iterations used in iterative decoding. We show that these hierarchies satisfy inclusion properties as these parameters are increased. In particular, this implies that a codeword that is decoded with a certificate using an iterative decoder after hhh iterations is decoded with a certificate after k⋅hk\cdot hk⋅h iterations, for every integer kkk.
In any engineering discipline, one looks for methods of solving a given class of problems and then for methods of quantifying the performance and complexity of those solutions. Accordingly, in this chapter, we shall study performance in terms of the composition structure of block codes, and the probabilities of decoding error and of decoding failure. Later, after satisfactory methods are in hand, one turns to questions of optimality. Are these methods the best methods, and if not, in what ways and by how much are they inferior? To answer such questions, one needs to know how good are the known codes and how good are the best possible codes. Generally, we cannot answer either of these questions satisfactorily. Although for any given rate and blocklength, not too small, the best possible code is not known, a number of bounds are known – bounds beyond which no codes can exist, and bounds within which codes are sure to exist. We shall give some such bounds on the best possible codes later in this chapter. Knowledge of these bounds can deepen our understanding of the subject. Weight distributions of block codes If a linear block code has a minimum distance d min , then we know that at least one codeword of weight d min exists. Sometimes, we are not content with this single piece of information; we wish to know how many codewords have weight d min , and what are the weights of the other codewords.