Elias Bassalygo bound

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 . 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