Elias Bassalygo bound
Encyclopedia
Let 
be a 
-ary code of length 
, i.e. a subset of 
. Let 
be the rate of 
and 
be the relative distance.
Let
be the Hamming Ball of radius 
centered at 
. Let 
be the volume of the Hamming ball of radius 
. It is obvious that the volume of a Hamming Ball is translation invariant, i.e. irrelevant with position of \boldsymbol{y}. In particular, 
With large enough
, the rate 
and the relative distance
satisfies the Elias-Bassalygo bound: 
where
is the q-ary entropy function
and
To prove the Elias–Bassalygo bound, we'll need the following Lemma:
----
Lemma 1: Given a q-ary code,
and 
, there exists a Hamming ball of radius 
with at least 
codewords in it.
Proof of Lemma 1: We prove Lemma 1 using probability method. Let's random pick a received word
. The expected size of overlapped region between 
and the Hamming ball centered at 
with radius 
, 
is 
since 
is (uniform) randomly selected. Since this is the expected value of the size, there must exist at least one 
such that 
, otherwise the expectation must be smaller than this value.
----
Now we prove the Elias–Bassalygo bound.
Define
.
By Lemma 1, there exists a Hamming ball with
codewords such that
By Johnson Bound Johnson bound, we have
. Thus,
The second inequality follows from lower bound on the volume of a Hamming ball:
Putting in
and 
gives the second inequality.
Therefore we have
be a -ary code of length , i.e. a subset of . Let be the rate of and be the relative distance.Let
be the Hamming Ball of radius centered at . Let be the volume of the Hamming ball of radius . It is obvious that the volume of a Hamming Ball is translation invariant, i.e. irrelevant with position of \boldsymbol{y}. In particular, With large enough
, the rate and the relative distance satisfies the Elias-Bassalygo bound: where
is the q-ary entropy function
and
-
is a function related with Johnson bound
To prove the Elias–Bassalygo bound, we'll need the following Lemma:
----
Lemma 1: Given a q-ary code,
and , there exists a Hamming ball of radius with at least codewords in it.Proof of Lemma 1: We prove Lemma 1 using probability method. Let's random pick a received word
. The expected size of overlapped region between and the Hamming ball centered at with radius , is since is (uniform) randomly selected. Since this is the expected value of the size, there must exist at least one such that , otherwise the expectation must be smaller than this value.----
Now we prove the Elias–Bassalygo bound.
Define
.By Lemma 1, there exists a Hamming ball with
codewords such thatBy Johnson Bound Johnson bound, we have
. Thus,The second inequality follows from lower bound on the volume of a Hamming ball:
Putting in
and gives the second inequality.Therefore we have
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...
- 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 :...
- Gilbert–Varshamov bound
- Johnson bound