Gilbert–Varshamov bound for linear codes: Difference between revisions

Revision as of 10:42, 30 January 2019

Revision as of 18:09, 31 January 2019

Line 1:

{{technical|date=January 2019}}

The '''Gilbert-VarshamovGilbert–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 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 [[probabilistic method]], and thus is not constructive.

The Gilbert–Varshamov bound is the best in terms of relative distance for codes over alphabets of size less than 49.{{citation needed|date=May 2013}}

Line 16:

'''''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 randomly by choosing the [[random generator|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 [[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 \backslashsmallsetminus \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:'''''

Line 24:

We know that the linear code is defined using the [[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]], 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) \\

& = \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) \\

&= \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>

Line 38:

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>

Line 50:

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>\text{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]</ref>

Line 60:

: <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==