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

An updated table of minimum-distance bounds for binary linear codes

T Tom Verhoeff

Published Sep 1, 1987• 289 citations
Publisher

Abstract

In 1973 Helgert and Sfinaff published a table of upper and lower bounds on the maximum minimum-distance for binary linear error-correcting codes up to length127. This article presents an updated table incorporating numerous improvements that have appeared since then. To simplify the updating task the author has developed a computer program that systematically investigates the consequences of each improvement by applying several well-known general code-construction techniques. This program also made it possible to check the original table. Furthermore, it offers a quick and reliable update service for future improvements.

DOI
10.1109/tit.1987.1057356

Related papers

Upper bounds on codes correcting asymmetric errors (Corresp.)

Torleiv Kløve

A Survey is given of known upper bounds on codes correcting asymmetric errors. The bounds are improved by introducing new Ideas. By solving a linear programming problem an upper bound is given that is easy to compute for all codelengths and all minimum asymmetric distances.

IEEE Transactions on Information Theory•Jan 1, 1981•35 citations

New binary linear codes

Thomas Aaron Gulliver, Patric R. J. Östergård

In this paper, nineteen new binary linear codes are presented which improve the bounds on the maximum possible minimum distance. These codes belong to the class of quasi-cyclic (QC) codes, and have been constructed using a stochastic optimization algorithm, tabu search. Six of the new codes meet the upper bound on minimum distance and so are optimal.

Ars Combinatoria•Jan 1, 2000•10 citations

Upper bounds on minimum distance of nonbinary quantum stabilizer codes

Santosh Kumar

The most popular class of quantum error correcting codes is stabilizer codes. Binary quantum stabilizer codes have been well studied, and Calderbank, Rains, Shor and Sloane (July 1998) have constructed a table of upper bounds on the minimum distance of these codes using linear programming methods. However, not much is known in the case of nonbinary stabilizer codes. In this thesis, we establish a bridge between selforthogonal classical codes over the finite field containing q2 elements and quantum codes, extending and unifying previous work by Matsumoto and Uyematsu (2000), Ashikhmin and Knill (November 2001), Kim and Walker (2004). We construct a table of upper bounds on the minimum distance of the stabilizer codes using linear programming methods that are tighter than currently known bounds. Finally, we derive code construction techniques that will help us find new codes from existing ones. All these results help us to gain a better understanding of the theory of nonbinary stabilizer codes.

•Nov 1, 2005•0 citations

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

Improved linear programming decoding and bounds on the minimum distance of LDPC codes

David Burshtein, Idan Goldenberg

We propose a technique for improving LP decoding, based on the merging of check nodes. This technique can be applied to standard as well as generalized LDPC codes. Furthermore, we show how a recently-discovered linear-complexity LP decoder can be used to derive non-trivial lower bounds on the minimum distance of specific LDPC codes, with complexity that exhibits quadratic growth with respect to the block length. This bound can be refined using the check node merging technique. The lower bound on the minimum distance is shown to be an upper bound on the fractional distance of the code.

IEEE Information Theory Workshop (ITW)•Aug 1, 2010•8 citations

New results on binary quasi-cyclic codes

Zhi Chen

Twelve new binary quasi-cyclic codes, which improve the lower bounds on minimum distances for binary linear codes, are presented, and a Web database on best-known binary quasi-cyclic codes is constructed for public access.

IEEE International Symposium on Information Theory (ISIT)•Nov 7, 2002•4 citations
In 1973 Helgert and Sfinaff published a table of upper and lower bounds on the maximum minimum-distance for binary linear error-correcting codes up to length127. This article presents an updated table incorporating numerous improvements that have appeared since then. To simplify the updating task the author has developed a computer program that systematically investigates the consequences of each improvement by applying several well-known general code-construction techniques. This program also made it possible to check the original table. Furthermore, it offers a quick and reliable update service for future improvements.
The most popular class of quantum error correcting codes is stabilizer codes. Binary quantum stabilizer codes have been well studied, and Calderbank, Rains, Shor and Sloane (July 1998) have constructed a table of upper bounds on the minimum distance of these codes using linear programming methods. However, not much is known in the case of nonbinary stabilizer codes. In this thesis, we establish a bridge between selforthogonal classical codes over the finite field containing q2 elements and quantum codes, extending and unifying previous work by Matsumoto and Uyematsu (2000), Ashikhmin and Knill (November 2001), Kim and Walker (2004). We construct a table of upper bounds on the minimum distance of the stabilizer codes using linear programming methods that are tighter than currently known bounds. Finally, we derive code construction techniques that will help us find new codes from existing ones. All these results help us to gain a better understanding of the theory of nonbinary stabilizer codes.
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.
We propose a technique for improving LP decoding, based on the merging of check nodes. This technique can be applied to standard as well as generalized LDPC codes. Furthermore, we show how a recently-discovered linear-complexity LP decoder can be used to derive non-trivial lower bounds on the minimum distance of specific LDPC codes, with complexity that exhibits quadratic growth with respect to the block length. This bound can be refined using the check node merging technique. The lower bound on the minimum distance is shown to be an upper bound on the fractional distance of the code.