The Elias Bassalygo bound is a mathematical limit used in coding theory for error correction during data transmission or communications.
Definition Let be a -ary code of length , i.e. a subset of .Each -ary block code of length is a subset of the strings of where the alphabet set has elements. Let be the rate of , the relative distance and
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. indifferent to In particular,
With large enough , the rate and the relative distance satisfy the Elias-Bassalygo bound:
where
is the q-ary entropy function and
is a function related with Johnson bound.
Proof To prove the Elias–Bassalygo bound, start with the following Lemma:
Lemma. For and , there exists a Hamming ball of radius with at least
codewords in it.
Proof of Lemma. Randomly pick a received word and let be the Hamming ball centered at with radius . Since is (uniform) randomly selected the expected size of overlapped region is
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, there exists a Hamming ball with codewords such that:
By the 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 Gilbert–Varshamov bound Hamming bound Johnson bound Plotkin bound Singleton bound
References