View source for Gilbert–Varshamov bound for linear codes

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 correction code|error-correcting code]] of a given block length and minimum [[Hamming weight]] over a [[Field (mathematics)|field]] <math>\mathbb{F}_q</math>. 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 code|linear code]]s 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|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.{{citation needed|date=May 2013}}  For larger alphabets, [[Algebraic geometry code|algebraic geometry codes]] sometimes achieve an asymptotically better rate vs. distance tradeoff than is given by the Gilbert–Varshamov bound.<ref>{{cite journal |last1=Tsfasman |first1=M.A. |last2=Vladut |first2=S.G. |last3=Zink |first3=T. |title=Modular curves, Shimura curves, and Goppa codes better than the Varshamov-Gilbert bound |journal=Mathematische Nachrichten |date=1982 |volume=104}}</ref>

==Gilbert–Varshamov bound theorem==

:'''Theorem:''' Let <math>q \geqslant 2</math>. For every <math>0 \leqslant \delta < 1 - \tfrac{1}{q}</math> and <math>0 < \varepsilon  \leqslant 1 - H_q (\delta ),</math> there exists a code with rate <math>R \geqslant 1 - H_q (\delta ) - \varepsilon </math> and relative distance <math>\delta.</math>

Here <math>H_q</math> is the ''q''-ary entropy function defined as follows:

: <math>H_q(x) = x\log_q(q-1)-x\log_qx-(1-x)\log_q(1-x).</math>

The above result was proved by [[Biography:Edgar Gilbert|Edgar Gilbert]] for general code using the greedy method as [[Gilbert–Varshamov bound|here]]. For [[Linear code|linear code]], [[Biography:Rom Varshamov|Rom Varshamov]] proved using the [[Probabilistic method|probabilistic method]] for the random linear code. This proof will be shown in the following part.

'''''High-level proof:'''''

To show the existence of the linear code that satisfies those constraints, the [[Probabilistic method|probabilistic method]] is used to construct the random linear code. Specifically the linear code is chosen randomly by choosing the random generator matrix <math>G</math> in which the element is chosen uniformly over the field <math>\mathbb{F}_q^n </math>. Also the [[Hamming distance]] of the linear code is equal to the minimum weight of the [[Code word (communication)|codeword]]. So to prove that the linear code generated by <math>G</math> has Hamming distance <math>d</math>, we will show that for any <math>m \in \mathbb{F}_q^k \smallsetminus \left\{ 0 \right\}, \operatorname{wt}(mG) \ge d</math> . To prove that, we prove the opposite one; that is, the probability that the linear code generated by <math>G</math> has the Hamming distance less than <math>d</math> is exponentially small in <math>n</math>. Then by probabilistic method, there exists the 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 <math>d</math>, we will show that the [[Probability|probability]] that the random linear code having the distance less than <math>d</math> is exponentially small in <math>n</math>.

We know that the linear code is defined using the [[Generator matrix|generator matrix]]. So we use the "random generator matrix" <math>G</math> as a mean to describe the randomness of the linear code. So a random generator matrix <math>G</math> of size <math>kn</math> contains <math>kn</math> elements which are chosen independently and uniformly over the field <math>\mathbb{F}_q</math>.

Recall that in a [[Linear code|linear code]], the distance equals the minimum weight of the non-zero codeword. Let <math>\operatorname{wt}(y)</math> be the weight of the codeword <math>y</math>. So

:<math>
\begin{align}
P & = \Pr_{\text{random }G} (\text{linear code generated by } G\text{ has distance} < d) \\[6pt]
& = \Pr_{\text{random }G} (\text{there exists a non-zero codeword } y \text{ in a linear code generated by }G\text{ such that } \operatorname{wt}(y) < d) \\[6pt]
&= \Pr_{\text{random }G} \left (\text{there exists } 0 \neq m \in \mathbb{F}_q^k \text{ such that } \operatorname{wt}(mG) < d \right )
\end{align}
</math>

The last equality follows from the definition: if a codeword <math>y</math> belongs to a linear code generated by <math>G</math>, then <math>y = mG</math> for some vector <math>m \in \mathbb{F}_q^k</math>.

By [[Boole's inequality]], we have:

: <math>P \leqslant  \sum_{0 \neq m \in \mathbb{F}_q^k} \Pr_{\text{random }G} (\operatorname{wt}(mG) < d)</math>

Now for a given message <math>0 \neq m \in \mathbb{F}_q^k,</math> we want to compute

:<math>W = \Pr_{\text{random }G} (\operatorname{wt}(mG) < d).</math>

Let <math>\Delta(m_1,m_2)</math> be a Hamming distance of two messages <math>m_1</math> and <math>m_2</math>. Then for any message <math>m</math>, we have: <math>\operatorname{wt}(m) = \Delta(0,m)</math>. Therefore:

: <math>W = \sum_{\{y \in \mathbb{F}_q^n |\Delta (0,y) \leqslant d - 1\}} \Pr_{\text{random }G} (mG = y)</math>

Due to the randomness of <math>G</math>, <math>mG</math> is a uniformly random vector from <math>\mathbb{F}_q^n</math>. So

:<math>\Pr_{\text{random }G} (mG = y) = q^{-n}</math>

Let <math>\operatorname{Vol}_q(r,n)</math> is a volume of Hamming ball with the radius <math>r</math>. Then:<ref>The later inequality comes from [http://www.cse.buffalo.edu/~atri/courses/coding-theory/lectures/lect9.pdf the upper bound of the Volume of Hamming ball] {{Webarchive|url=https://web.archive.org/web/20131108081414/http://www.cse.buffalo.edu/~atri/courses/coding-theory/lectures/lect9.pdf |date=2013-11-08 }}</ref>

: <math> P \leqslant  q^k W  = q^k \left ( \frac{\operatorname{Vol}_q(d-1,n)}{q^n} \right )  \leqslant  q^k \left ( \frac{q^{nH_q(\delta)}}{q^n} \right ) = q^k q^{-n(1-H_q(\delta))}</math>

By choosing <math>k = (1-H_q(\delta)-\varepsilon)n</math>, the above inequality becomes

: <math> P \leqslant  q^{-\varepsilon n}</math>

Finally <math>q^{-\varepsilon n}  \ll 1</math>, which is exponentially small in n, that is what we want before. Then by the probabilistic method, there exists a linear code <math>C</math> with relative distance <math>\delta</math> and rate <math>R</math> at least <math>(1-H_q(\delta)-\varepsilon)</math>, which completes the proof.

==Comments==

# The Varshamov construction above is not explicit; that is, it does not specify the deterministic method to construct the linear code that satisfies the Gilbert–Varshamov bound. A naive approach is to search over all generator matrices <math>G</math> of size <math>kn</math> over the field <math>\mathbb{F}_q</math> to check if the linear code associated to <math>G</math> achieves the predicted Hamming distance. This exhaustive search requires exponential runtime in the worst case.
# There also exists a [[Las Vegas algorithm|Las Vegas construction]] that takes a random linear code and checks if this code has good Hamming distance, but this construction also has an exponential runtime.
#For sufficiently large non-prime q and for certain ranges of the variable δ, the Gilbert–Varshamov bound is surpassed by the Tsfasman–Vladut–Zink bound.<ref>{{Cite journal|last=Stichtenoth|first=H.|date=2006|title=Transitive and self-dual codes attaining the Tsfasman-Vla/spl breve/dut$80-Zink bound|journal=IEEE Transactions on Information Theory|volume=52|issue=5|pages=2218–2224|doi=10.1109/TIT.2006.872986|s2cid=11982763 |issn=0018-9448}}</ref>

==See also==
* [[Gilbert–Varshamov bound|Gilbert–Varshamov bound due to Gilbert construction for the general code]]
* [[Hamming bound]]
* [[Probabilistic method]]

==References==
{{Reflist}}
* [https://web.archive.org/web/20100702120650/http://www.cse.buffalo.edu/~atri/courses/coding-theory/ Lecture 11: Gilbert–Varshamov Bound. Coding Theory Course. Professor Atri Rudra]
* [https://web.archive.org/web/20131108081414/http://www.cse.buffalo.edu/~atri/courses/coding-theory/lectures/lect9.pdf Lecture 9: Bounds on the Volume of Hamming Ball. Coding Theory Course. Professor Atri Rudra]
* [https://www.cs.cmu.edu/~venkatg/teaching/codingtheory/ Coding Theory Notes: Gilbert–Varshamov Bound. Venkatesan Guruswami]

{{DEFAULTSORT:Gilbert-Varshamov bound for linear codes}}
[[Category:Coding theory]]

{{Sourceattribution|Gilbert–Varshamov bound for linear codes}}