Asymptotic Improvement Of The Gilbert-varshamov Bound On The Size Of Binary Codes
Jiang Tao, Vardy Alexander. IEEE TRANSACTIONS ON INFORMATION THEORY vol. 2004
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.
Similar Work