Gilbert–Varshamov bound for linear codes: Difference between revisions

Revision as of 01:06, 9 May 2011

Latest revision as of 16:25, 16 August 2025

(48 intermediate revisions by 37 users not shown)

Line 1:

{{lead missingtechnical|date=MayJanuary 20112019}}

==Introduction==

In [[coding theory]], the bound of parameters such as rate <math>R</math>, 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 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.

==Gilbert-Varshamov Bound Theorem==

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 \ge 2</math>. For every <math>0 \le \delta </math> < <math> 1 - \frac{1}{q}</math>, and 0 < <math> \varepsilon \le 1 - H_q (\delta )</math>, there exists a code with rate <math>R \ge 1 - H_q (\delta ) - \varepsilon </math>, and relative distance <math>\delta</math>.

:'''Theorem:''' Let <math>q \gegeqslant 2</math>. For every <math>0 \leleqslant \delta </math> < <math> 1 - \fractfrac{1}{q}</math>, and <math>0 < <math> \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:

<math>H_q(x) = xlog_q(q-1)-xlog_qx-(1-x)log_q(1-x)</math>.

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

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

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

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

The above result was proved by [[Edgar Gilbert]] for general codecodes using the [[greedy method]] as. [[Gilbert-Rom Varshamov bound|here]]. 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]].

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]] 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 \backslash \left\{ 0 \right\}, 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.

'''''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 20 ⟶ 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 = the minimum weight of the non-zero codeword. This fact is one of the [[Linear_code|properties of linear code]].

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

So <math>P = Pr_{Random G}</math> [linear code generated by <math>G</math> has distance < <math>d</math>] = <math>Pr_{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)</math> < <math>d</math>]

Also if 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_{Random G}</math> [there exists a [[vector]] <math>m \in \mathbb{F}_q^k \backslash \{ 0\}</math> such that <math>wt(mG)</math> < <math>d</math>]

By [[Booles_inequality|Union Bound]], we have:

<math>P \le \sum\limits_{m \in \mathbb{F}_q^k \backslash \{ 0\} } {Pr_{random\;G} } [wt(mG)</math> < <math>d</math>]

NowRecall forthat in a given[[linear messagecode]], <math>mthe \indistance \mathbb{F}_q^kequals \backslashthe \{minimum 0\}</math>,weight weof wanta tononzero computecodeword. Let <math>W = Pr_\operatorname{Random\;Gwt} [wt(mGy)</math> <be the weight of the codeword <math>d]y</math>. So

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

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

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

Then for any message <math>m</math>, we have: <math>wt(m) = \Delta(0,m)</math>.

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

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

: <math>W =P \sumleqslant \limits_sum_{all0 \;neq ym \in \mathbb{F}_q^n s.t.\; \Delta (0,y) \le d - 1k} {\Pr_{random\;text{random }G} [(\operatorname{wt}(mG) =< y]}d)</math>

DueNow tofor thea randomnessgiven ofmessage <math>G</math>,0 <math>mG</math>\neq ism a\in uniformly random vector from <math>\mathbb{F}_q^nk,</math>. we want to compute

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

Let <math>Vol_q\Delta(rm_1,nm_2)</math> isbe a VolumeHamming distance of Hammingtwo ballmessages with<math>m_1</math> the radiusand <math>rm_2</math>. Then for any message <math>m</math>, we have: <math>\operatorname{wt}(m) = \Delta(0,m)</math>. Therefore:

: <math>W = \fracsum_{Vol_q(d-1,n)}\{q^n}y \lein \fracmathbb{Vol_q(F}_q^n |\deltaDelta n(0,ny) \leqslant d - 1\}{q^n} \le Pr_{\fractext{q^{nH_qrandom }G} (\deltamG = y)}}{q^n}</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

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

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

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-VarshamovGilbert–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_algorithmLas 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 Alsoalso==

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

#* [[Hamming_bound|Hamming Boundbound]]

#* [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-VarshamovGilbert–Varshamov Bound. Venkatesan �GuruswamiGuruswami]

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

[[Category:Error Detection and Correction Code]]

[[Category:Coding theory]]