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

Abstract

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)\ge 2^n/V(n,d-1)$, where $V(n,d)={\sum }_{i=0}^d\left(\genfrac{}{}{0ex}{}{n}{i}\right)$ 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)\ge 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.

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

References in corpus (2)

• Still better nonlinear codes from modular curves
• A Lower Bound on the Density of Sphere Packings via Graph Theory

Cited by in corpus (14)

• On the hard sphere model and sphere packings in high dimensions
• Asymptotic improvement of the Gilbert-Varshamov bound for linear codes
• Primitive Rateless Codes
• Equilateral sets in finite-dimensional normed spaces
• Cavity approach to sphere packing in Hamming space
• Cumulative Distance Enumerators of Random Codes and their Thresholds
• Proof of a conjecture of Kløve on permutation codes under the Chebychev distance
• Duality between Packings and Coverings of the Hamming Space
• On quadratic residue codes and hyperelliptic curves
• A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble
• Improving the Gilbert-Varshamov Bound by Graph Spectral Method
• Wide-Sense 2-Frameproof Codes
• Distribution of the minimal distance of random linear codes
• New Theoretical Bounds and Constructions of Permutation Codes under Block Permutation Metric