IEEE International Symposium on Information Theory (ISIT)

If binary codes existed that exceed Gilbert-Varshamov bound they could not reach the cutoff rate of BSC

T. Beth, D.E. Lazic

Published Nov 19, 2002• 1 citation

Abstract

Binary block codes exceeding the Gilbert-Varshamov bound on the minimum Hamming distance (if such codes exist) have their error exponents below the one of the binary symmetric channel (BSC) in the interval (R/sub crit/, R/sub c/) and they cannot reach the cutoff rate R/sub 0/ and thus the capacity R/sub c/ of the BSC if a maximum likelihood decoder (MLD) is used.

DOI: 10.1109/isit.1995.531336

Related papers

A lower bound on the probability of decoding error over a BSC channel

Osnat Keren, Simon N. Litsyn

For a code C of length n and size |C, we estimate the error probability of the maximum likelihood decoding. In this paper we address this problem for the binary symmetric channel (BSC) defined by its transition probability p. We discuss the case when we know the distance distribution of the code. We also assume that the code is regular in the sense that the distribution of the distances from a codeword to other codewords does not depend on the choice of the initial codeword.

IEEE Convention of Electrical and Electronics Engineers in IsraelNov 11, 20027 citations

On the asymptotic accuracy of the union bound

Alexander Barg

A new lower bound on the error probability of maximum likelihood decoding of a binary code on a binary symmetric channel was proved in Barg and McGregor (2004, cs.IT/0407011). It was observed in that paper that this bound leads to a new region of code rates in which the random coding exponent is asymptotically tight, giving a new region in which the reliability of the BSC is known exactly. The present paper explains the relation of these results to the union bound on the error probability.

arXiv:cs/0412111Dec 24, 20043 citations

To the Question of Almost Maximum-Likelihood Decoding

Mikhail Afanasev, Andrei A. Ovchinnikov

Evseev’s lemma claims that if we use the decoding by a standard array and use coset leaders having the weight not greater than Gilbert-Varshamov distance then the probability of error decoding will become not greater than the probability of error decoding of maximum-likelihood multiplied by two. However, the estimation of tightness of this bound is an open problem. In this work we perform the estimation of the accuracy of Evseev’s lemma on the example of several linear random codes by simulating them in a binary-symmetric channel.

Wave Electronics and its Application in Information and Telecommunication Systems (WECONF)Jun 1, 20201 citation

Low-complexity error correction of Hamming-code-based LDPC codes

Victor Zyablov, Rolf Johannesson, Matea Lončar

Ensembles of binary random LDPC block codes constructed using Hamming codes as constituent codes are studied for communicating over the binary symmetric channel. These ensembles are known to contain codes that asymptotically almost meet the Gilbert-Varshamov bound. It is shown that in these ensembles there exist codes which can correct a number of errors that grows linearly with the code length, when decoded with a low-complexity iterative decoder, which requires a number of iterations that is a logarithmic function of the code length. The results are supported by numerical examples, for various choices of the code parameters.

Problems of Information TransmissionJun 1, 200917 citations

A Gilbert-Varshamov bound for quasi-cycle codes of rate 1/2 (Corresp.)

Tadao Kasami

It is shown that there exist arbitrarily long quasi-cyclic(2k,k)binary codes that meet a bound slightly weaker than the Gilbert-Varshamov bound. This is a refinement of the result of Chen, Peterson, and Weldon [1].

IEEE Transactions on Information TheorySep 1, 1974143 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