Van H. Vu ; Lei Wu

Improving the GilbertVarshamov bound for $q$ary codes
dmtcs:3456 
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

https://doi.org/10.46298/dmtcs.3456
Improving the GilbertVarshamov bound for $q$ary codesArticle
Authors: Van H. Vu ; Lei Wu ^{1}
NULL##NULL
Van H. Vu;Lei Wu
1 Department of Mathematics [Univ California San Diego]
Given positive integers $q$, $n$ and $d$, denote by $A_q(n,d)$ the maximum size of a $q$ary code of length $n$ and minimum distance $d$. The famous GilbertVarshamov bound asserts that $A_q(n,d+1) \geq q^n / V_q(n,d)$, where $V_q(n,d)=\sum_{i=0}^d \binom{n}{i}(q1)^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 $\alpha$ less than $(q1)/q$ there is a positive constant $c$ such that for $d \leq \alpha n, A_q(n,d+1) \geq c \frac{q^n}{ V_q(n,d)}n$. This confirms a conjecture by Jiang and Vardy.