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](https://everipedia.org/cdn-cgi/image/width=828/https://epcdn-vz.azureedge.net/static/images/no-image-slide-big.png)
Gilbert–Varshamov bound
Gilbert–Varshamov bound
![Gilbert–Varshamov bound](https://everipedia.org/cdn-cgi/image/width=828/https://epcdn-vz.azureedge.net/static/images/no-image-slide-big.png)
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 code
with length n and minimumHamming weightd (a q-ary code is a code over thefield
of q elements).
Then:
Proof
Let
be a code of length
and minimumHamming 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 theunionof allballsof radius
having theircentreat some
:
Now each ball has size
since we may allow (orchoose) up to
of the
components of a codeword to deviate (from the value of the corresponding component of the ball'scentre) 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
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