DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Improving the Gilbert-Varshamov bound for q-ary codes

Van H. Vu, Lei Wu


Given positive integers q, n and d, denote by Aq(n,d) the maximum size of a q-ary code of length n and minimum distance d. The famous Gilbert-Varshamov bound asserts that Aq(n,d+1) ≥qn / Vq(n,d), where Vq(n,d)=Σi=0dbinom(n, i)(q-1)i is the volume of a q-ary sphere of radius d. Extending a recent work of Jiang and Vardy on binary codes, we show that for any positive constant α less than (q-1)/q there is a positive constant c such that for d ≤αn, Aq(n,d+1)≥cqn / Vq(n,d)n. This confirms a conjecture by Jiang and Vardy.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional