Jump to content

Gilbert–Varshamov bound

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Deacon Vorbis (talk | contribs) at 15:39, 15 July 2017 (Proof: LaTeX spacing clean up, replaced: \, </math> → </math> using AWB). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In coding theory, the Gilbert–Varshamov bound (due to Edgar Gilbert[1] and independently Rom Varshamov[2]) is a limit on the parameters of a (not necessarily linear) code. It is occasionally known as the Gilbert–Shannon–Varshamov bound (or the GSV bound), but the name "Gilbert–Varshamov bound" is by far the most popular. Varshamov proved this bound by using the probabilistic method for linear codes. For more about that proof, see: GV-linear-code.

Statement of the bound

Let

denote the maximum possible size of a q-ary code with length n and minimum Hamming weight d (a q-ary code is a code over the field of q elements).

Then:

Proof

Let be a code of length and minimum Hamming distance having maximal size:

Then for all  , there exists at least one codeword such that the Hamming distance between and satisfies

since otherwise we could add x to the code whilst maintaining the code's minimum Hamming distance – a contradiction on the maximality of .

Hence the whole of is contained in the union of all balls of radius having their centre at some  :

Now each ball has size

since we may allow (or choose) up to of the components of a codeword to deviate (from the value of the corresponding component of the ball's centre) to one of possible other values (recall: the code is q-ary: it takes values in ). Hence we deduce

That is:

An improvement in the prime power case

For q a prime power, one can improve the bound to where k is the greatest integer for which

See also

References

  1. ^ Gilbert, E. N. (1952), "A comparison of signalling alphabets", Bell System Technical Journal, 31: 504–522, doi:10.1002/j.1538-7305.1952.tb01393.x.
  2. ^ Varshamov, R. R. (1957), "Estimate of the number of signals in error correcting codes", Dokl. Acad. Nauk SSSR, 117: 739–741.