The Gilbert–Varshamov bound for linear codes is related to the general Gilbert–Varshamov bound, which gives a lower bound on the maximal number of elements in an error-correcting code of a given block length and minimum Hamming weight over a field F q {\displaystyle \mathbb {F} _{q}} . This may be translated into a statement about the maximum rate of a code with given length and minimum distance. The Gilbert–Varshamov bound for linear codes asserts the existence of q-ary linear codes for any relative minimum distance less than the given bound that simultaneously have high rate. The existence proof uses the probabilistic method, and thus is not constructive. The Gilbert–Varshamov bound is the best known in terms of relative distance for codes over alphabets of size less than 49. For larger alphabets, algebraic geometry codes sometimes achieve an asymptotically better rate vs. distance tradeoff than is given by the Gilbert–Varshamov bound.
Gilbert–Varshamov bound theorem Theorem: Let q ⩾ 2 {\displaystyle q\geqslant 2} . For every 0 ⩽ δ < 1 − 1 q {\displaystyle 0\leqslant \delta <1-{\tfrac {1}{q}}} and 0 < ε ⩽ 1 − H q ( δ ) , {\displaystyle 0<\varepsilon \leqslant 1-H_{q}(\delta ),} there exists a q {\displaystyle q} -ary linear code with rate R ⩾ 1 − H q ( δ ) − ε {\displaystyle R\geqslant 1-H_{q}(\delta )-\varepsilon } and relative distance δ . {\displaystyle \delta .}
Here H q {\displaystyle H_{q}} is the q-ary entropy function defined as follows:
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).}
The above result was proved by Edgar Gilbert for general codes using the greedy method. Rom Varshamov refined the result to show the existence of a linear code. The proof uses the probabilistic method. High-level proof: To show the existence of the linear code that satisfies those constraints, the probabilistic method is used to construct the random linear code. Specifically, the linear code is chosen by picking a generator matrix G ∈ F q k × n {\displaystyle G\in \mathbb {F} _{q}^{k\times n}} whose entries are randomly chosen elements of F q {\displaystyle \mathbb {F} _{q}} . The minimum Hamming distance of a linear code is equal to the minimum weight of a nonzero codeword, so in order to prove that the code generated by G {\displaystyle G} has minimum distance d {\displaystyle d} , it suffices to show that for any m ∈ F q k ∖ { 0 } , wt ( m G ) ≥ d {\displaystyle m\in \mathbb {F} _{q}^{k}\smallsetminus \left\{0\right\},\operatorname {wt} (mG)\geq d} . We will prove that the probability that there exists a nonzero codeword of weight less than d {\displaystyle d} is exponentially small in n {\displaystyle n} . Then by the probabilistic method, there exists a linear code satisfying the theorem. Formal proof: By using the probabilistic method, to show that there exists a linear code that has a Hamming distance greater than d {\displaystyle d} , we will show that the probability that the random linear code having the distance less than d {\displaystyle d} is exponentially small in n {\displaystyle n} . The linear code is defined by its generator matrix, which we choose to be a random k × n {\displaystyle k\times n} generator matrix; that is, a matrix of k n {\displaystyle kn} elements which are chosen independently and uniformly over the field F q {\displaystyle \mathbb {F} _{q}} . Recall that in a linear code, the distance equals the minimum weight of a nonzero codeword. Let wt ( y ) {\displaystyle \operatorname {wt} (y)} be the weight of the codeword y {\displaystyle y} . So
… excerpt ends here. Continue reading the full article.
