In coding theory, the Gilbert–Varshamov bound (due to Edgar Gilbert and independently Rom Varshamov) is a bound on the size of a (not necessarily linear) code. It is occasionally known as the Gilbert–Shannon–Varshamov bound (or the GSV bound), but the name "Gilbert–Varshamov bound" is by far the most popular. Varshamov proved this bound by using the probabilistic method for linear codes. For more about that proof, see Gilbert–Varshamov bound for linear codes.
Statement of the bound Recall that a code has a minimum distance d {\displaystyle d} if any two elements in the code are at least a distance d {\displaystyle d} apart. Let
A q ( n , d ) {\displaystyle A_{q}(n,d)}
denote the maximum possible size of a q-ary code C {\displaystyle C} with length n and minimum Hamming distance d (a q-ary code is a code over the field F q {\displaystyle \mathbb {F} _{q}} of q elements). Then:
A q ( n , d ) ⩾ q n ∑ j = 0 d − 1 ( n j ) ( q − 1 ) j ≥ q n ( 1 − H q ( d / n ) ) {\displaystyle A_{q}(n,d)\geqslant {\frac {q^{n}}{\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}}\geq q^{n(1-H_{q}(d/n))}}
where H q {\displaystyle H_{q}} is the q-ary entropy function,
H q ( x ) = x log q ( q − 1 ) − x log q x − ( 1 − x ) log q ( 1 − x ) . {\displaystyle H_{q}(x)=x\log _{q}(q-1)-x\log _{q}x-(1-x)\log _{q}(1-x).}
Proof Let C {\displaystyle C} be a code of length n {\displaystyle n} and minimum Hamming distance d {\displaystyle d} having maximal size:
| C | = A q ( n , d ) . {\displaystyle |C|=A_{q}(n,d).}
Then for all x ∈ F q n {\displaystyle x\in \mathbb {F} _{q}^{n}} , there exists at least one codeword c x ∈ C {\displaystyle c_{x}\in C} such that the Hamming distance d ( x , c x ) {\displaystyle d(x,c_{x})} between x {\displaystyle x} and c x {\displaystyle c_{x}} satisfies
d ( x , c x ) ⩽ d − 1 {\displaystyle d(x,c_{x})\leqslant d-1}
since otherwise we could add x to the code whilst maintaining the code's minimum Hamming distance d {\displaystyle d} – a contradiction on the maximality of | C | {\displaystyle |C|} . Hence the whole of F q n {\displaystyle \mathbb {F} _{q}^{n}} is contained in the union of all balls of radius d − 1 {\displaystyle d-1} having their centre at some c ∈ C {\displaystyle c\in C} :
F q n = ⋃ c ∈ C B ( c , d − 1 ) . {\displaystyle \mathbb {F} _{q}^{n}=\bigcup _{c\in C}B(c,d-1).}
Now each ball has size
… excerpt ends here. Continue reading the full article.
