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 and , let denote the maximum size
of a binary code of length and minimum distance . The well-known
Gilbert-Varshamov bound asserts that , where
is the volume of a Hamming sphere of
radius . We show that, in fact, there exists a positive constant such
that $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