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

Error-Correction Capability of Binary Linear Codes

Tor Helleseth, Torleiv Kløve, V.I. Levenshtein

Published Apr 1, 2005• 30 citations
Publisher

Abstract

The monotone structure of correctable and uncorrectable errors given by the complete decoding for a binary linear code is investigated. New bounds on the error-correction capability of linear codes beyond half the minimum distance are presented, both for the best codes and for arbitrary codes under some restrictions on their parameters. It is proved that some known codes of low rate are as good as the best codes in an asymptotic sense.

DOI
10.1109/tit.2005.844080

Related papers

On decoding algorithms for binary linear block codes

Bruce L. Montgomery

This dissertation investigates the complexity of minimum-distance decoding (MDD) algorithms for general binary linear block codes, and also investigates the use of such codes in constructing error correcting/detecting codes that are effective against both random and unidirectional errors. A new MDD algorithm is proposed, and its complexity is analyzed and compared to that of other such algorithms. The question of whether all good codes satisfy certain properties required for efficient implementation of the algorithm is also considered. The performance of decoding algorithms, with the information bit error rate as the criterion instead of the block error rate, is also studied. New decoding rules which can yield lower information bit error rates than the MDD rule are proposed and evaluated. A new class of binary codes is developed which corrects random errors and detects all unidirectional errors. These codes are obtained by appending a suffix to each codeword of a linear block code. To evaluate the efficiency of the new codes, a thorough comparison with the best previously obtained codes is made.

•Jan 1, 1987•0 citations

Potential-decoding, error correction beyond the half minimum distance for linear block codes

R. Lohnert

An error correction procedure for linear block codes is presented which corrects errors beyond the half minimum distance. The algorithm is based on minimizing a real valued function, called potential. Since the potential decreases monotonously with decreasing weight of the error vector, minimization of the potential can be done by local search.

IEEE International Symposium on Information Theory (ISIT)•Nov 19, 2002•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

On the Minimum Distance of Non Binary LDPC Codes

Rethnakaran Pulikkoonattu

Minimum distance is an important parameter of a linear error correcting code. For improved performance of binary Low Density Parity Check (LDPC) codes, we need to have the minimum distance grow fast with n, the codelength. However, the best we can hope for is a linear growth in dmin with n. For binary LDPC codes, the necessary and sufficient conditions on the LDPC ensemble parameters, to ensure linear growth of minimum distance is well established. In the case of non-binary LDPC codes, the structure of logarithmic weight codewords is different from that of binary codes. We have carried out a preliminary study on the logarithmic bound on the the minimum distance of non-binary LDPC code ensembles. In particular, we have investigated certain configurations which would lead to low weight codewords. A set of simulations are performed to identify some of these configurations. Finally, we have provided a bound on the logarithmic minimum distance of nonbinary codes, using a strategy similar to the girth bound for binary codes. This bound has the same asymptotic behaviour as that of binary codes.

arXiv:0906.2061•Jun 11, 2009•0 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 quasi-cyclic codes

P. Heijnen, Henk van Tilborg, S. Weijs

Many binary quasi-cyclic codes have a better minimum distance than other known linear codes with the same parameters. We present 43 new quasi-cyclic codes, which improve on the parameters of previously found quasi-cyclic codes. Five of them even improve the lower bound on the minimum distance for linear codes. Furthermore we present a decoding algorithm for the binary quasi-cyclic codes of rate 1/m.

IEEE International Symposium on Information Theory (ISIT)•Nov 27, 2002•6 citations
The monotone structure of correctable and uncorrectable errors given by the complete decoding for a binary linear code is investigated. New bounds on the error-correction capability of linear codes beyond half the minimum distance are presented, both for the best codes and for arbitrary codes under some restrictions on their parameters. It is proved that some known codes of low rate are as good as the best codes in an asymptotic sense.
This dissertation investigates the complexity of minimum-distance decoding (MDD) algorithms for general binary linear block codes, and also investigates the use of such codes in constructing error correcting/detecting codes that are effective against both random and unidirectional errors. A new MDD algorithm is proposed, and its complexity is analyzed and compared to that of other such algorithms. The question of whether all good codes satisfy certain properties required for efficient implementation of the algorithm is also considered. The performance of decoding algorithms, with the information bit error rate as the criterion instead of the block error rate, is also studied. New decoding rules which can yield lower information bit error rates than the MDD rule are proposed and evaluated. A new class of binary codes is developed which corrects random errors and detects all unidirectional errors. These codes are obtained by appending a suffix to each codeword of a linear block code. To evaluate the efficiency of the new codes, a thorough comparison with the best previously obtained codes is made.
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.
Minimum distance is an important parameter of a linear error correcting code. For improved performance of binary Low Density Parity Check (LDPC) codes, we need to have the minimum distance grow fast with n, the codelength. However, the best we can hope for is a linear growth in dmin with n. For binary LDPC codes, the necessary and sufficient conditions on the LDPC ensemble parameters, to ensure linear growth of minimum distance is well established. In the case of non-binary LDPC codes, the structure of logarithmic weight codewords is different from that of binary codes. We have carried out a preliminary study on the logarithmic bound on the the minimum distance of non-binary LDPC code ensembles. In particular, we have investigated certain configurations which would lead to low weight codewords. A set of simulations are performed to identify some of these configurations. Finally, we have provided a bound on the logarithmic minimum distance of nonbinary codes, using a strategy similar to the girth bound for binary codes. This bound has the same asymptotic behaviour as that of binary 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.