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|linear codes]]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, [[Goppa code|Goppa codes]]s 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==
Line 69:
==See also==
#* [[Gilbert–Varshamov bound|Gilbert–Varshamov bound due to Gilbert construction for the general code]]
#* [[Hamming bound|Hamming Bound]]
#* [[Probabilistic method]]
==References==
{{Reflist}}
#* [https://web.archive.org/web/20100702120650/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/20131108081414/http://www.cse.buffalo.edu/~atri/courses/coding-theory/lectures/lect9.pdf Lecture 9: Bounds on the Volume of Hamming Ball. Coding Theory Course. Professor Atri Rudra]
#* [https://www.cs.cmu.edu/~venkatg/teaching/codingtheory/ Coding Theory Notes: Gilbert–Varshamov Bound. Venkatesan Guruswami]
{{DEFAULTSORT:Gilbert-Varshamov bound for linear codes}}
