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

Linear programming bounds for doubly-even self-dual codes

Ilia Krasikov, Simon N. Litsyn

Published Jul 1, 1997• 15 citations
Publisher

Abstract

Using a variant of the linear programming method we derive a new upper bound on the minimum distance d of doubly-even self-dual codes of length n. Asymptotically, for n growing, it gives d/n/spl les/0.166315/spl middot//spl middot//spl middot/+o(1), thus improving on the Mallows-Odlyzko-Sloane bound of 1/6. To establish this, we prove that in any doubly even-self-dual code the distance distribution is asymptotically upper-bounded by the corresponding normalized binomial distribution in a certain interval.

DOI
10.1109/18.605587

Related papers

An improved upper bound on the minimum distance of doubly-even self-dual codes

Ilia Krasikov, Simon N. Litsyn

We derive a new upper bound on the minimum distance d of doubly-even self-dual codes of length n. Asymptotically, for n growing, it gives lim/sub n/spl rarr//spl infin// sup d/n/spl les/(5-5/sup 3/4/)/10<0.165630, thus improving on the Mallows-Odlyzko-Sloane bound of 1/6 and our recent bound of 0.166315.

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

Shadow bounds for self-dual codes

Eric M. Rains

Conway and Sloane (1990) have previously given an upper bound on the minimum distance of a singly-even self-dual binary code, using the concept of the shadow of a self-dual code. We improve their bound, finding that the minimum distance of a self-dual binary code of length n is at most 4[n/24]+4, except when n mod 24=22, when the bound is 4[n/24]+6. We also show that a code of length a multiple of 24 meeting the bound cannot be singly-even. The same technique gives similar results for additive codes over GF(4) (relevant to quantum coding theory).

IEEE Transactions on Information Theory•Jan 1, 1998•237 citations

Performance of extremal codes

Anton Malevich

Assume that a binary linear code is transmitted over a channel with the symbol error probability p and that bounded distance decoding is used. In this case it is known [3] that for sufficiently small p the performance of the code is only a question of the weight distribution (weight enumerators of more efficient codes are lexicographically smaller). Based on this result we study the efficiency of extremal self-dual codes. Extremal doubly-even codes have unique weight enumerators for each length, and at first glance it may seem that these codes should perform worse than other codes with the same minimum distance. However we show that this is not always the case when comparing to singly-even codes. We also show that a doubly-even code may perform better than a non self-dual code. We find the most efficient codes among extremal singly-even codes of length 24m + 8 and 24m + 16. We also consider some families of extremal singly-even codes with uniquely determined weight enumerators (s-extremal codes, codes with minimal shadow). It appears that they always perform better than extremal doublyeven codes of the same length. The results are joint work with Wolfgang Willems (Magdeburg).

•Jan 1, 2006•0 citations

Upper bounds on the rate of LDPC codes as a function of minimum distance

Yael Ben‐Haim, Simon N. Litsyn

New upper bounds on the rate of low-density parity-check (LDPC) codes as a function of the minimum distance of the code are derived. These bounds are based on combinatorial arguments and linear programming. They improve on the previous bounds due to Burshtein et al. It is proved that at least for high rate LDPC codes have worse relative minimum distance than the one guaranteed by the Gilbert-Varshamov bound

IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2005•3 citations

Upper bounds on the rate of LDPC codes as a function of minimum distance

Yael Ben‐Haim, Simon N. Litsyn

New upper bounds on the rate of low-density parity-check (LDPC) codes as a function of the minimum distance of the code are derived. The bounds apply to regular LDPC codes, and sometimes also to right-regular LDPC codes. Their derivation is based on combinatorial arguments and linear programming. The new bounds improve upon the previous bounds due to Burshtein et al. It is proved that at least for high rates, regular LDPC codes with full-rank parity-check matrices have worse relative minimum distance than the one guaranteed by the Gilbert-Varshamov bound.

IEEE Transactions on Information Theory•Apr 28, 2006•24 citations

Bounds for weight distribution of weakly self-dual codes

Vwani Roychowdhury, Farrokh Vatan

Upper bounds are given for the weight distribution of binary weakly self-dual codes. To get these new bounds, we introduce a novel method of utilizing unitary operations on Hilbert spaces. This method is motivated by recent progress on quantum computing. This new approach leads to much simpler proofs for such genre of bounds on the weight distributions of certain classes of codes. Moreover, in some cases, our bounds are improvements on the earlier bounds. These improvements are achieved, either by extending the range of the weights over which the bounds apply, or by extending the class of codes subjected to these bounds.

arXiv:math/0104016•Apr 2, 2001•1 citation
Using a variant of the linear programming method we derive a new upper bound on the minimum distance d of doubly-even self-dual codes of length n. Asymptotically, for n growing, it gives d/n/spl les/0.166315/spl middot//spl middot//spl middot/+o(1), thus improving on the Mallows-Odlyzko-Sloane bound of 1/6. To establish this, we prove that in any doubly even-self-dual code the distance distribution is asymptotically upper-bounded by the corresponding normalized binomial distribution in a certain interval.
Conway and Sloane (1990) have previously given an upper bound on the minimum distance of a singly-even self-dual binary code, using the concept of the shadow of a self-dual code. We improve their bound, finding that the minimum distance of a self-dual binary code of length n is at most 4[n/24]+4, except when n mod 24=22, when the bound is 4[n/24]+6. We also show that a code of length a multiple of 24 meeting the bound cannot be singly-even. The same technique gives similar results for additive codes over GF(4) (relevant to quantum coding theory).
Assume that a binary linear code is transmitted over a channel with the symbol error probability p and that bounded distance decoding is used. In this case it is known [3] that for sufficiently small p the performance of the code is only a question of the weight distribution (weight enumerators of more efficient codes are lexicographically smaller). Based on this result we study the efficiency of extremal self-dual codes. Extremal doubly-even codes have unique weight enumerators for each length, and at first glance it may seem that these codes should perform worse than other codes with the same minimum distance. However we show that this is not always the case when comparing to singly-even codes. We also show that a doubly-even code may perform better than a non self-dual code. We find the most efficient codes among extremal singly-even codes of length 24m + 8 and 24m + 16. We also consider some families of extremal singly-even codes with uniquely determined weight enumerators (s-extremal codes, codes with minimal shadow). It appears that they always perform better than extremal doublyeven codes of the same length. The results are joint work with Wolfgang Willems (Magdeburg).
New upper bounds on the rate of low-density parity-check (LDPC) codes as a function of the minimum distance of the code are derived. The bounds apply to regular LDPC codes, and sometimes also to right-regular LDPC codes. Their derivation is based on combinatorial arguments and linear programming. The new bounds improve upon the previous bounds due to Burshtein et al. It is proved that at least for high rates, regular LDPC codes with full-rank parity-check matrices have worse relative minimum distance than the one guaranteed by the Gilbert-Varshamov bound.
Upper bounds are given for the weight distribution of binary weakly self-dual codes. To get these new bounds, we introduce a novel method of utilizing unitary operations on Hilbert spaces. This method is motivated by recent progress on quantum computing. This new approach leads to much simpler proofs for such genre of bounds on the weight distributions of certain classes of codes. Moreover, in some cases, our bounds are improvements on the earlier bounds. These improvements are achieved, either by extending the range of the weights over which the bounds apply, or by extending the class of codes subjected to these bounds.