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

Simple item page
dc.creatorJiang, Tao
dc.creatorVardy, Alexander
dc.date2004-04-19
dc.date.accessioned2026-07-07T08:18:16Z
dc.date.available2026-07-07T08:18:16Z
dc.descriptionGiven 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.
dc.description10 pages, 3 figures; to appear in the IEEE Transactions on Information Theory, submitted August 12, 2003, revised March 28, 2004
dc.identifierhttps://arxiv.org/abs/math/0404325
dc.identifierhttp://arxiv.org/abs/math/0404325
dc.identifierIEEE TRANSACTIONS ON INFORMATION THEORY, vol. 50, No. 8, pp. 1655-1664, August 2004 (http://www.ieeexplore.ieee.org/iel5/18/29198/01317112.pdf)
dc.identifierdoi:10.1109/TIT.2004.831751
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/134371
dc.subjectCombinatorics
dc.subjectInformation Theory
dc.subjectCommutative Algebra
dc.subject05C90, 94B65 (Primary) 05A16, 05C69 (secondary)
dc.titleAsymptotic Improvement of the Gilbert-Varshamov Bound on the Size of Binary Codes
dc.typetext

Files

Collections

arXiv