Gilbert–Varshamov bound for linear codes: Difference between revisions

Revision as of 04:28, 9 December 2022

Latest revision as of 16:25, 16 August 2025

(6 intermediate revisions by 6 users not shown)

Line 2:

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.

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, [[GoppaAlgebraic geometry code|algebraic geometry codes]]s sometimes achieve an asymptotically better rate vs. distance tradeoff than is given by the Gilbert-VarshamovGilbert–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 <math>q</math>-ary linear 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:

Line 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–Varshamov bound|here]]. For [[linear code]], [[Rom Varshamov]] proved usingrefined the [[probabilisticresult method]]to forshow the randomexistence of a 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 [[random generator|random]]a 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 \smallsetminus \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 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. Let <math>\operatorname{wt}(y)</math> be the weight of the codeword <math>y</math>. So

:<math>

Line 52:

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

Let <math>\operatorname{Vol}_q(r,n)</math> isbe athe volume of a [[Hamming ball]] with the radius <math>r</math>. Then:<ref>The later inequality comes from [httphttps://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>

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

Line 66:

# 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-VarshamovGilbert–Varshamov bound is improvedsurpassed by the [[Tsfasman-Vladut-ZinkTsfasman–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|Hamming Bound]]

* [[Probabilistic method]]