Gilbert-Varshamov bound
Encyclopedia
In coding theory
, the Gilbert–Varshamov bound (due to Edgar Gilbert
and independently Rom Varshamov) is a bound 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 Gilbert–Varshamov bound is by far the most popular name. Varshamov proved this bound by using the probabilistic method for linear code. For this proof, check here
for more detail.
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:
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 d – a contradiction on the maximality of
.
Hence the whole of
is contained in the union
of all balls
of radius d − 1 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:
(using the fact:
).
where k is the greatest integer for which
Coding theory
Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...
, the Gilbert–Varshamov bound (due to Edgar Gilbert
Edgar Gilbert
Edgar Nelson Gilbert was an American mathematician and coding theorist, a longtime researcher at Bell Laboratories whose accomplishments include the Gilbert–Varshamov bound in coding theory, the Gilbert–Elliott model of bursty errors in signal transmission, and the Erdős–Rényi model for random...
and independently Rom Varshamov) is a bound on the parameters of a (not necessarily linear
Linear code
In coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although Turbo codes can be seen as a hybrid of these two types. Linear codes allow for...
) code
Code
A code is a rule for converting a piece of information into another form or representation , not necessarily of the same type....
. It is occasionally known as the Gilbert–Shannon–Varshamov bound (or the GSV bound), but the Gilbert–Varshamov bound is by far the most popular name. Varshamov proved this bound by using the probabilistic method for linear code. For this proof, check here
GV-linear-code
In coding theory, the bound of parameters such as rate R, relative distance, block length, etc. is usually concerned. Here Gilbert–Varshamov bound theorem claims the lower bound of the rate of the general code...
for more detail.
Statement of the bound
Letdenote 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 fieldField (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
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 satisfiessince otherwise we could add x to the code whilst maintaining the code's minimum Hamming distance d – a contradiction on the maximality of
.Hence the whole of
is contained in the unionUnion (set theory)
In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
of all balls
Ball (mathematics)
In mathematics, a ball is the space inside a sphere. It may be a closed ball or an open ball ....
of radius d − 1 having their centre
Ball (mathematics)
In mathematics, a ball is the space inside a sphere. It may be a closed ball or an open ball ....
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 centreBall (mathematics)
In mathematics, a ball is the space inside a sphere. It may be a closed ball or an open ball ....
) to one of
possible other values (recall: the code is q-ary: it takes values in ). Hence we deduceThat is:
(using the fact:
).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 boundSingleton boundIn coding theory, the Singleton bound, named after Richard Collom Singleton, is a relatively crude bound on the size of a block code C with block length n, size r and minimum distance d.-Statement of the Bound:...
- Hamming boundHamming boundIn mathematics and computer science, in the field of coding theory, the Hamming bound is a limit on the parameters of an arbitrary block code: it is also known as the sphere-packing bound or the volume bound from an interpretation in terms of packing balls in the Hamming metric into the space of...
- Johnson bound
- Plotkin boundPlotkin boundIn the mathematics of coding theory, the Plotkin bound, named after Morris Plotkin, is a bound on the maximum possible number of codewords in binary codes of given length n and given minimum distance d.- Statement of the bound :...
- Griesmer boundGriesmer boundIn the mathematics of coding theory, the Griesmer bound, named after James Hugo Griesmer, is a bound on the length of binary codes of dimension k and minimum distance d.There is also a very similar version for non-binary codes....
- Grey–Rankin bound
- Gilbert–Varshamov bound for linear codeGV-linear-codeIn coding theory, the bound of parameters such as rate R, relative distance, block length, etc. is usually concerned. Here Gilbert–Varshamov bound theorem claims the lower bound of the rate of the general code...