The Elias Bassalygo bound is a mathematical limit used in coding theory for error correction during data transmission or communications.
-ary code of length
be the rate of
the relative distance and be the Hamming ball of radius
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
and the relative distance
satisfy 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, start with the following Lemma: Now we prove the Elias–Bassalygo bound.
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
Therefore we have Bassalygo, L. A.
(1965), "New upper bounds for error-correcting codes", Problems of Information Transmission, 1 (1): 32–35 Claude E. Shannon, Robert G. Gallager; Berlekamp, Elwyn R. (1967), "Lower bounds to error probability for coding on discrete memoryless channels.
Part I.
", Information and Control, 10: 65–103, doi:10.1016/s0019-9958(67)90052-6 Claude E. Shannon, Robert G. Gallager; Berlekamp, Elwyn R. (1967), "Lower bounds to error probability for coding on discrete memoryless channels.
Part II.
", Information and Control, 10: 522–552, doi:10.1016/s0019-9958(67)91200-4