Improving the Gilbert-Varshamov bound for q-ary codes
Van H. Vu, Lei Wu
Abstract
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