Gilbert–Varshamov bound for linear codes: Difference between revisions

Revision as of 02:52, 28 May 2011

Latest revision as of 16:25, 16 August 2025

(40 intermediate revisions by 32 users not shown)

Line 1:

{{technical|date=January 2019}}

{{nointro}}

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]]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]], and thus is not constructive.

In [[coding theory]], the bound of parameters such as rate ''R'', relative distance, [[block length]], etc. is usually concerned. Here [[Gilbert–Varshamov bound|Gilbert–Varshamov bound theorem]] claims the lower bound of the rate of the general code. More interestingly, Gilbert–Varshamov bound is the best in term of relative distance for codes over alphabets of size less than 49.

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 \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 <math>q</math>-ary linear 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 11 ⟶ 12:

: <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 [[Edgar Gilbert]] for general codecodes using the [[greedy method]] as. [[Gilbert–VarshamovRom bound|hereVarshamov]]. Forrefined [[linearthe code]],result Varshamovto proved usingshow the [[probabilisticexistence method]]of for the randoma linear code. ThisThe proof will be shown inuses the following[[probabilistic partmethod]].

'''''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 choosingpicking the [[randoma generator]] matrix <math>G \in \mathbb{F}_q^{k \times n}</math> inwhose whichentries theare element israndomly chosen uniformlyelements over the fieldof <math>\mathbb{F}_q^n </math>. AlsoThe theminimum [[Hamming distance]] of thea linear code is equal to the minimum weight of thea nonzero [[codeword]]., Soso in order to prove that the linear code generated by <math>G</math> has Hammingminimum distance <math>d</math>, weit willsuffices to show that for any <math>m \in \mathbb{F}_q^k \backslashsmallsetminus \left\{ 0 \right\}, \operatorname{wt}(mG) \ge d</math> . ToWe prove that, wewill prove the opposite one; that is, the probability that thethere linearexists codea generatednonzero bycodeword <math>G</math>of has the Hamming distanceweight less than <math>d</math> is exponentially small in <math>n</math>. Then by the probabilistic method, there exists thea linear code satisfying the theorem.

'''''Formal proof:'''''

Line 21 ⟶ 22:

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]] that the random linear code having the distance less than <math>d</math> is exponentially small in <math>n</math>.

We know that theThe linear code is defined usingby theits [[generator matrix]]., Sowhich we usechoose theto "randombe generatora matrix"random <math>Gk \times n</math> asgenerator amatrix; meanthat to describe the randomness of the linear code. Sois, 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 thea non-zerononzero codeword. ThisLet fact<math>\operatorname{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>.

\begin{align}

So <math>P = \Pr_{\text{Random }G} [\text{linear code generated by }G\text{ has distance} < d] = \Pr_{\text{Random }G}</math> [there exists a codeword <math>y \ne 0</math> in a linear code generated by <math>G</math> such that <math>wt(y) < d</math>]

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]

Therefore <math>P &= \Pr_{\text{Randomrandom }G} [\left (\text{there exists a} vector0 \neq }m \in \mathbb{F}_q^k \backslash \{ 0\}\text{ such that } \operatorname{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_{\text{random }G} } [(\operatorname{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>W =0 \sum\limits_{\text{allneq }ym \in \mathbb{F}_q^n \text{s.t. }\Delta (0k,y)</math> \lewe dwant -to 1} {\Pr_{\text{random }G} [mG = y]}</math>compute

So :<math>W = \Pr_{\text{random }G} [(\operatorname{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>\operatorname{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>\operatorname{Vol}_q(r,n)</math> be the volume of a [[Hamming ball]] with the radius <math>r</math>. Then:<ref>The later inequality comes from [https://www.cse.buffalo.edu/faculty/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>

Then

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

==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. TheA naive way that we can doapproach is to gosearch over all the generator matrices <math>G</math> of size <math>kn</math> over the field <math>\mathbb{F}_q</math> andto check if thatthe linear code hasassociated to <math>G</math> achieves the satisfiedpredicted Hamming distance. ThatThis leadsexhaustive tosearch therequires exponential timeruntime algorithmin tothe implementworst itcase.

# WeThere also haveexists a [[Las Vegas algorithm|Las Vegas construction]] that takes a random linear code and checks if this code has good Hamming distance. Nevertheless, but this construction also has thean exponential running timeruntime.

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

#* [http://en.wikipedia.org/wiki/Gilbert%E2%80%93Varshamov_bound[Gilbert–Varshamov bound|Gilbert–Varshamov bound due to Gilbert construction for the general code]]

#* [[Hamming bound|Hamming Bound]]

#* [http://en.wikipedia.org/wiki/Probabilistic_method [Probabilistic method]]

==References==

{{Reflist}}

# [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/20100702120650/http://www.cse.buffalo.edu/~atri/courses/coding-theory/lectures/lect9.pdf Lecture 911: Bounds on the Volume of HammingGilbert–Varshamov BallBound. Coding Theory Course. Professor Atri Rudra]

(The later inequality comes from* [https://web.archive.org/web/20131108081414/http://www.cse.buffalo.edu/~atri/courses/coding-theory/lectures/lect9.pdf theLecture upper9: boundBounds ofon the Volume of Hamming ballBall. Coding Theory Course. Professor Atri Rudra])

#* [httphttps://www.cs.cmu.edu/~venkatg/teaching/codingtheory/ Coding Theory's Notes: Gilbert–Varshamov Bound. Venkatesan �GuruswamiGuruswami]

{{DEFAULTSORT:Gilbert-Varshamov bound for linear codes}}

[[Category:Coding theory]]