IEEE Transactions on Information Theory

The Simplex Codes and Other Even-Weight Binary Linear Codes for Error Correction

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

Published Oct 26, 2004• 7 citations

Abstract

The probability of correct decoding on the binary-symmetric channel is studied. In particular, a class of codes with the same lengths and dimensions as the linear simplex codes, but with larger probability of correct decoding for all parameters p, 0 < p < 1/2, is given.

DOI: 10.1109/tit.2004.836708

Related papers

The simplex codes are not optimal for binary symmetric channels

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

It is shown that the [2/sup K/-1,k] simplex codes are not optimal for error correction on the binary symmetric channel with bit error probability p, where 0<p<;1/2 (for k/spl ges/3).

IEEE International Symposium on Information Theory (ISIT)Jan 1, 20030 citations

A coset weight count that proves that the simplex codes are not optimal for error correction

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

The number of cosets of weight 2/sup k-2/ or less are determined for the [2/sup k/-1, k, 2/sup k-1/] simplex code and a [2/sup k/-1, k, 2/sup k-1/-1] code obtained by a simple modification of the simplex code. The result proves that the [2/sup k/-1, k] simplex codes are not optimal for error correction on the binary symmetric channel with small bit error probability, p, (for k/spl ges/3). A proof that the modified code is better for all p, 0<p<1/2, is sketched.

IEEE Information Theory Workshop (ITW)Mar 1, 20042 citations

On the complete decoding of binary linear codes (Corresp.)

Michele Elia, G. Prati

IEEE Transactions on Information TheoryJul 1, 19858 citations

Bounds on the undetected error probabilities of linear codes for both error correction and detection

Mao‐Chao Lin

The author investigates the (n, k, d>or=2t+1) binary linear codes, which are used for correcting error patterns of weight at most t and detecting other error patterns over a binary symmetric channel. In particular, for t=1, it is shown that there exists one code whose probability of undetected errors is upper-bounded by (n+1) (2/sup n-k/-n)/sup -1/ when used on a binary symmetric channel with transition probability less than 2/n.>

IEEE Transactions on Information TheoryJan 1, 19900 citations

An algorithm for calculating the exact bit error probability of a binary linear code over the binary symmetric channel

T. Wadayama

An efficient algorithm for calculating the i-th bit error probability of a binary linear code over the binary symmetric channel (BSC) are presented. It is proved that the exact i-th bit error probability of maximum likelihood (ML) decoding, bounded distance decoding, symbolwise maximum a posteriori probability (MAP) decoding and symbolwise MAP decoding with erasure can be obtained with time complexity O(n2/sup n-k/), where n, k denote length and dimension of the target code.

IEEE International Symposium on Information Theory (ISIT)Jun 25, 20030 citations

A criterion for decoding on the binary symmetric channel

Anup Rao, Oscar Sprumont

Advances in Mathematics of CommunicationsFeb 28, 20242 citations

IEEE Transactions on Information Theory

The Simplex Codes and Other Even-Weight Binary Linear Codes for Error Correction

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

Published Oct 26, 2004• 7 citations

Publisher

Abstract

DOI: 10.1109/tit.2004.836708

Related papers

The simplex codes are not optimal for binary symmetric channels

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

It is shown that the [2/sup K/-1,k] simplex codes are not optimal for error correction on the binary symmetric channel with bit error probability p, where 0<p<;1/2 (for k/spl ges/3).

IEEE International Symposium on Information Theory (ISIT)Jan 1, 20030 citations

A coset weight count that proves that the simplex codes are not optimal for error correction

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

IEEE Information Theory Workshop (ITW)Mar 1, 20042 citations

On the complete decoding of binary linear codes (Corresp.)

Michele Elia, G. Prati

Complete decoding of systematic linear block codes by standard arrays with coset leaders not necessarily of minimal weight gives, in several interesting cases on the binary symmetric channel with error probabilityp, a smaller symbol error probability than decoding using the coset leaders of minimum weight. The proposed choice of the coset leaders allows for the classes of uniformly packed and nearly perfect binary codes to achieve a lower information bit error probability, at least forpsufficiently near zero.Complete decoding of systematic linear block codes by standard arrays with coset leaders not necessarily of minimal weight gives, in several interesting cases on the binary symmetric channel with error probabilityp, a smaller symbol error probability than decoding using the coset leaders of minimum weight. The proposed choice of the coset leaders allows for the classes of uniformly packed and nearly perfect binary codes to achieve a lower information bit error probability, at least forpsufficiently near zero.

IEEE Transactions on Information TheoryJul 1, 19858 citations

Bounds on the undetected error probabilities of linear codes for both error correction and detection

Mao‐Chao Lin

IEEE Transactions on Information TheoryJan 1, 19900 citations

An algorithm for calculating the exact bit error probability of a binary linear code over the binary symmetric channel

T. Wadayama

IEEE International Symposium on Information Theory (ISIT)Jun 25, 20030 citations

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.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 CommunicationsFeb 28, 20242 citations

:

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