The Elias Bassalygo bound is a mathematical limit used in coding theory for error correction during data transmission or communications.
-ary code of length
the relative distance and be the Hamming ball of radius
ρ n
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