Gilbert–Varshamov bound for linear codes: Difference between revisions

Revision as of 04:28, 9 December 2022

Revision as of 11:24, 4 June 2023

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