© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

Performance of extremal codes

Anton Malevich

Published Jan 1, 2006• 0 citations

Abstract

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).

Related papers

On maximum likelihood soft decoding of some binary self dual codes

Moshe Ran, Jakov Snyders

The authors present and compare the performance of maximum likelihood (ML) soft decoding algorithms for binary linear self-dual (SD) codes. The codes considered have a minimum distance of 4, but due to their different weight distributions they differ in their coding gain. Remarkably, there is a code, denoted F/sub 24/, which has a decoder nearly 4 times faster than the fastest published decoder (6) for the (24,12,8) Golay code. Nontheless, these two codes have almost equal coding gains. Simulation results are given to compare between the codes. An analytical discussion of the results appears in an Appendix.>

IEEE Convention of Electrical and Electronics Engineers in Israel•Dec 9, 2002•1 citation

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

Projection Decoding of Some Binary Optimal Linear Codes of Lengths 36 and 40

Lucky Galvez, Jon-Lark Kim

Practically good error-correcting codes should have good parameters and efficient decoding algorithms. Some algebraically defined good codes, such as cyclic codes, Reed–Solomon codes, and Reed–Muller codes, have nice decoding algorithms. However, many optimal linear codes do not have an efficient decoding algorithm except for the general syndrome decoding which requires a lot of memory. Therefore, a natural question to ask is which optimal linear codes have an efficient decoding. We show that two binary optimal [ 36 , 19 , 8 ] linear codes and two binary optimal [ 40 , 22 , 8 ] codes have an efficient decoding algorithm. There was no known efficient decoding algorithm for the binary optimal [ 36 , 19 , 8 ] and [ 40 , 22 , 8 ] codes. We project them onto the much shorter length linear [ 9 , 5 , 4 ] and [ 10 , 6 , 4 ] codes over G F ( 4 ) , respectively. This decoding algorithm, called projection decoding, can correct errors of weight up to 3. These [ 36 , 19 , 8 ] and [ 40 , 22 , 8 ] codes respectively have more codewords than any optimal self-dual [ 36 , 18 , 8 ] and [ 40 , 20 , 8 ] codes for given length and minimum weight, implying that these codes are more practical.

arXiv:1911.07212•Mathematics•Dec 19, 2019•1 citation

A criterion for decoding on the binary symmetric channel

Anup Rao, Oscar Sprumont

We present an approach to showing that a linear code is resilient to random errors. We use this approach to obtain decoding results for both transitive and doubly transitive codes. We give three kinds of results about linear codes in general, and transitive linear codes in particular.1. We give a tight bound on the weight distribution of every transitive linear code $ C \subseteq \mathbb{F}_2^N $:$ \mathop {\Pr }\limits_{c \in C}[ \text{wt}(c) = \alpha N] \leq 2^{-(1-h(\alpha)) \mathsf{dim}(C)}. $2. We give a criterion that certifies that a linear code $ C $ can be decoded on the binary symmetric channel. Let $ K_s(x) $ denote the Krawtchouk polynomial of degree $ s $, and let $ C^\perp $ denote the dual code of $ C $. We show that bounds on $ \mathbb{E}_{c \in C^{\perp}}[ K_{\epsilon N}( \text{wt}(c))^2] $ imply that $ C $ recovers from errors on the binary symmetric channel with parameter $ \epsilon $. Weaker bounds can be used to obtain list-decoding results using similar methods. One consequence of our criterion is that whenever the weight distribution of $ C^\perp $ is sufficiently close to the binomial distribution in some interval around $ \frac{N}{2} $, $ C $ is resilient to $ \epsilon $-errors.3. We combine known estimates for the Krawtchouk polynomials with our weight bound for transitive codes, and with known weight bounds for doubly transitive codes, to obtain list-decoding results for both these families of codes. In some regimes, our bounds for doubly transitive codes achieve the information-theoretic optimal trade-off between rate and list size.

Advances in Mathematics of Communications•Feb 28, 2024•2 citations

Soft decoding performance of extremal self-dual codes

V.K. Bhargava

Performance of soft decoded extremal self-dual codes of lengths 8 to 72 are obtained over the Gaussian channel. The results indicate that for decoded bit-error rates below 10-3, which is the main region of interest for coding application, substantial coding gains can be obtained by using extremal self-dual codes.

Proceedings of the IEEE•Jan 1, 1983•0 citations

Linear programming bounds for doubly-even self-dual codes

Ilia Krasikov, Simon N. Litsyn

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.

IEEE Transactions on Information Theory•Jul 1, 1997•15 citations

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).

The authors present and compare the performance of maximum likelihood (ML) soft decoding algorithms for binary linear self-dual (SD) codes. The codes considered have a minimum distance of 4, but due to their different weight distributions they differ in their coding gain. Remarkably, there is a code, denoted F/sub 24/, which has a decoder nearly 4 times faster than the fastest published decoder (6) for the (24,12,8) Golay code. Nontheless, these two codes have almost equal coding gains. Simulation results are given to compare between the codes. An analytical discussion of the results appears in an Appendix.>

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).

Practically good error-correcting codes should have good parameters and efficient decoding algorithms. Some algebraically defined good codes, such as cyclic codes, Reed–Solomon codes, and Reed–Muller codes, have nice decoding algorithms. However, many optimal linear codes do not have an efficient decoding algorithm except for the general syndrome decoding which requires a lot of memory. Therefore, a natural question to ask is which optimal linear codes have an efficient decoding. We show that two binary optimal [ 36 , 19 , 8 ] linear codes and two binary optimal [ 40 , 22 , 8 ] codes have an efficient decoding algorithm. There was no known efficient decoding algorithm for the binary optimal [ 36 , 19 , 8 ] and [ 40 , 22 , 8 ] codes. We project them onto the much shorter length linear [ 9 , 5 , 4 ] and [ 10 , 6 , 4 ] codes over G F ( 4 ) , respectively. This decoding algorithm, called projection decoding, can correct errors of weight up to 3. These [ 36 , 19 , 8 ] and [ 40 , 22 , 8 ] codes respectively have more codewords than any optimal self-dual [ 36 , 18 , 8 ] and [ 40 , 20 , 8 ] codes for given length and minimum weight, implying that these codes are more practical.

We present an approach to showing that a linear code is resilient to random errors. We use this approach to obtain decoding results for both transitive and doubly transitive codes. We give three kinds of results about linear codes in general, and transitive linear codes in particular.1. We give a tight bound on the weight distribution of every transitive linear code $ C \subseteq \mathbb{F}_2^N

:

\mathop {\Pr }\limits_{c \in C}[ \text{wt}(c) = \alpha N] \leq 2^{-(1-h(\alpha)) \mathsf{dim}(C)}. $2. We give a criterion that certifies that a linear code $ C $ can be decoded on the binary symmetric channel. Let $ K_s(x) $ denote the Krawtchouk polynomial of degree $ s $, and let $ C^\perp $ denote the dual code of $ C $. We show that bounds on $ \mathbb{E}_{c \in C^{\perp}}[ K_{\epsilon N}( \text{wt}(c))^2] $ imply that $ C $ recovers from errors on the binary symmetric channel with parameter $ \epsilon $. Weaker bounds can be used to obtain list-decoding results using similar methods. One consequence of our criterion is that whenever the weight distribution of $ C^\perp $ is sufficiently close to the binomial distribution in some interval around $ \frac{N}{2} $, $ C $ is resilient to $ \epsilon $-errors.3. We combine known estimates for the Krawtchouk polynomials with our weight bound for transitive codes, and with known weight bounds for doubly transitive codes, to obtain list-decoding results for both these families of codes. In some regimes, our bounds for doubly transitive codes achieve the information-theoretic optimal trade-off between rate and list size.

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.