Asymptotic Improvement Of The Gilbert-varshamov Bound On The Size Of Binary Codes | Awesome Learning to Hash Add your paper to Learning2Hash

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 A2(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 A2(n,d)2n/V(n,d1), where V(n,d)=i=0d(ni) is the volume of a Hamming sphere of radius d. We show that, in fact, there exists a positive constant c such that $A2(n,d)c2nV(n,d1)log2V(n,d1)wheneverd/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