Gilbert–Varshamov bound for linear codes: Difference between revisions

Revision as of 18:49, 15 August 2018

Revision as of 18:57, 15 August 2018

Line 4:

}}

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]] asserts the existence of ''q''-ary linear codes for any rate and relative minimum distance less than the given boundsbound that simultaneously has high rate. The existence proof uses [[probabilistic method]], and thus is not constructive.

The Gilbert–Varshamov bound is the best in terms of relative distance for codes over alphabets of size less than 49.{{citation needed|date=May 2013}}