Skip to Main content Skip to Navigation
Conference papers

Improving the Gilbert-Varshamov bound for $q$-ary codes

Abstract : 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 Gilbert-Varshamov 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}(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 $\alpha$ less than $(q-1)/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.
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184445
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, August 14, 2015 - 2:59:16 PM
Last modification on : Wednesday, August 7, 2019 - 12:18:06 PM
Long-term archiving on: : Sunday, November 15, 2015 - 11:13:26 AM

File

dmAE0156.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

van H. Vu, Lei Wu. Improving the Gilbert-Varshamov bound for $q$-ary codes. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.285-288, ⟨10.46298/dmtcs.3456⟩. ⟨hal-01184445⟩

Share

Metrics

Record views

98

Files downloads

563