Gilbert–Varshamov bound for linear codes: Difference between revisions

Revision as of 13:10, 15 October 2015

Revision as of 22:10, 31 August 2016

Line 8:

==Gilbert–Varshamov bound theorem==

:'''Theorem:''' Let <math>q \gegeqslant 2</math>. For every <math>0 \leleqslant \delta < 1 - \fractfrac{1}{q}</math>, and <math>0 < \varepsilon \leleqslant 1 - H_q (\delta ),</math>, there exists a code with rate <math>R \gegeqslant 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:

Line 26:

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. ThisLet fact<math>wt(y)</math> isbe onethe weight of the [[Linearcodeword code|properties<math>y</math>. of linear code]].So

: <math>

Denote <math>wt(y)</math> be the weight of the codeword <math>y</math>.

So

: <math>

\begin{align}

P & = {\Pr}_Pr_{\text{random }G} [(\text{linear code generated by }G\text{ has distance} < d]) \\

& = {\Pr}_Pr_{\text{random }G} [(\text{there exists a non-zero codeword } y \ne 0\text{ in a linear code generated by }G\text{ such that }\mathrm{wt}(y) < d]) \\

Therefore <math>P &= {\Pr}_Pr_{\text{random }G} [\left (\text{there exists a} vector0 \neq }m \in \mathbb{F}_q^k \backslash \{ 0\}\text{ such that }wt(mG) < d]</math> \right )

\end{align}

</math>

AlsoThe 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>.

Therefore <math>P = {\Pr}_{\text{random }G} [\text{there exists a vector }m \in \mathbb{F}_q^k \backslash \{ 0\}\text{ such that }wt(mG) < d]</math>

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

: <math>P \leleqslant \sumsum_{0 \limits_{neq m \in \mathbb{F}_q^k \backslash \{ 0\} } {{\Pr}_Pr_{\text{random }G} } [(wt(mG) < d])</math>

Now for a given message <math>m \in \mathbb{F}_q^k \backslash \{ 0\}</math>, we want to compute <math>W = {\Pr}_{\text{random }G} [wt(mG) < d]</math>

Denote <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>wt(m) = \Delta(0,m)</math>.

Using this fact, we can come up with the following equality:

Now for a given message <math>0 \neq m \in \mathbb{F}_q^k \backslash \{ 0\},</math>, we want to compute <math>W = {\Pr}_{\text{random }G} [wt(mG) < d]</math>

: <math>W = \sum\limits_{\text{all }y \in \mathbb{F}_q^n \text{s.t. }\Delta (0,y) \le d - 1} {{\Pr}_{\text{random }G} [mG = y]}</math>

So :<math>{W = \Pr}_Pr_{\text{random }G} [(wt(mG) =< y] = q^{ - n}d).</math>

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

DenoteLet <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>wt(m) = \Delta(0,m)</math>. Therefore:

So <math>{\Pr}_{\text{random }G} [mG = y] = q^{ - n}</math>

Let: <math>W = \textsum_{\{y \in \mathbb{VolF}_q^n |\Delta (r0,ny)</math> is\leqslant ad volume- of1\}} Hamming\Pr_{\text{random ball}G} with the(mG radius= <math>ry)</math>. Then:

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>W = \frac{\text{Vol}_q(d-1,n)}{q^n} \le \frac{\text{Vol}_q(\delta n,n)}{q^n} \le \frac{q^{nH_q(\delta)}}{q^n}</math>

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

(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])

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>

Then

: <math> P \leleqslant q^k W = q^k \cdotleft W( \lefrac{\text{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 \leleqslant 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.