Everipedia Logo
Everipedia is now IQ.wiki - Join the IQ Brainlist and our Discord for early access to editing on the new platform and to participate in the beta testing.
Gilbert–Varshamov bound

Gilbert–Varshamov bound

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: Gilbert–Varshamov bound for linear codes.

Statement of the bound

Let

denote the maximum possible size of a q-ary codewith length n and minimumHamming weightd (a q-ary code is a code over thefieldof q elements).

Then:

Proof

Letbe a code of lengthand minimumHamming distancehaving maximal size:
Then for all , there exists at least one codewordsuch that the Hamming distancebetweenandsatisfies
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 ofis contained in theunionof allballsof radiushaving theircentreat some :

Now each ball has size

since we may allow (orchoose) up toof thecomponents of a codeword to deviate (from the value of the corresponding component of the ball'scentre) to one ofpossible 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 towhere k is the greatest integer for which

See also

  • Singleton bound

  • Hamming bound

  • Johnson bound

  • Plotkin bound

  • Griesmer bound

  • Grey–Rankin bound

  • Gilbert–Varshamov bound for linear codes

  • Elias-Bassalygo bound

References

[1]
Citation Link//doi.org/10.1002%2Fj.1538-7305.1952.tb01393.xGilbert, E. N. (1952), "A comparison of signalling alphabets", Bell System Technical Journal, 31: 504–522, doi:10.1002/j.1538-7305.1952.tb01393.x.
Sep 26, 2019, 1:53 AM
[2]
Citation Linkopenlibrary.orgVarshamov, R. R. (1957), "Estimate of the number of signals in error correcting codes", Dokl. Akad. Nauk SSSR, 117: 739–741.
Sep 26, 2019, 1:53 AM
[3]
Citation Linkdoi.org10.1002/j.1538-7305.1952.tb01393.x
Sep 26, 2019, 1:53 AM
[4]
Citation Linken.wikipedia.orgThe original version of this page is from Wikipedia, you can edit the page right here on Everipedia.Text is available under the Creative Commons Attribution-ShareAlike License.Additional terms may apply.See everipedia.org/everipedia-termsfor further details.Images/media credited individually (click the icon for details).
Sep 26, 2019, 1:53 AM