# Gilbert–Varshamov bound

885 VIEWS

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 weight*d*(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 whichSee 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

[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