Asymptotic Improvement Of The Gilbert-varshamov Bound On The Size Of Binary Codes

Jiang Tao, Vardy Alexander. IEEE TRANSACTIONS ON INFORMATION THEORY vol. 2004

[Paper]    
Graph Theory

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(\genfrac{}{}{0ex}{}{n}{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)\ge c\frac{2^n}{V(n,d-1)}lo{g}_{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.

Similar Work

• Bounds On Codes Based On Graph Theory
• Uniqueness Of Codes Using Semidefinite Programming
• On Tight Bounds For Binary Frameproof Codes
• De Dictionariis Dynamicis Pauco Spatio Utentibus