Asymptotic Improvement of the Gilbert-Varshamov Bound on the Size of Binary Codes

Details Asymptotic Improvement of the Gilbert-Varshamov Bound on the Size of Binary Codes Asymptotic Improvement of the Gilbert-Varshamov Bound on the Size of Binary Codes

2004-04-19

arxiv.org/abs/math/0404325v1

IEEE TRANSACTIONS ON INFORMATION THEORY, vol. 50, No. 8, pp. 1655-1664, August 2004 (http://www.ieeexplore.ieee.org/iel5/18/

Mathematics

Combinatorics

10 pages, 3 figures; to appear in the IEEE Transactions on Information Theory, submitted August 12, 2003, revised March 28, 20

Scientific paper

10.1109/TIT.2004.831751

Given positive integers $n$ and $d$, let $A_2(n,d)$ denote the maximum size of a binary code of length $n$ and minimum distance $d$. The well-known Gilbert-Varshamov bound asserts that $A_2(n,d) \geq 2^n/V(n,d-1)$, where $V(n,d) = \sum_{i=0}^{d} {n \choose i}$ is the volume of a Hamming sphere of radius $d$. We show that, in fact, there exists a positive constant $c$ such that $$ A_2(n,d) \geq c \frac{2^n}{V(n,d-1)} \log_2 V(n,d-1) $$ whenever $d/n \le 0.499$. The result follows by recasting the Gilbert- Varshamov bound into a graph-theoretic framework and using the fact that the corresponding graph is locally sparse. Generalizations and extensions of this result are briefly discussed.

Affiliated with

Also associated with

No associations

Rating

Asymptotic Improvement of the Gilbert-Varshamov Bound on the Size of Binary Codes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Asymptotic Improvement of the Gilbert-Varshamov Bound on the Size of Binary Codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asymptotic Improvement of the Gilbert-Varshamov Bound on the Size of Binary Codes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-382518