Elias Bassalygo bound explained

The Elias Bassalygo bound is a mathematical limit used in coding theory for error correction during data transmission or communications.

Definition

Let

C be a q -ary code of length n , i.e. a subset of [q] ^{n} .^[1] Let R be the rate of C , \delta the relative distance and B _{q(y,} \rho n) = \left \{ x \in [q] ^{n} : \Delta(x, y) \leqslant \rho n \right \}

be the Hamming ball of radius

\rho n centered at y . Let Vol _{q(y,} \rho n) = |B _{q(y,} \rho n)| be the volume of the Hamming ball of radius \rho n . It is obvious that the volume of a Hamming Ball is translation-invariant, i.e. indifferent to y. In particular, |B _{q(y,} \rho n)| = |B _{q(0,} \rho n)|.

With large enough

n , the rate R and the relative distance \delta satisfy the Elias-Bassalygo bound: R \leqslant 1 - H _{q} ( J _{q(\delta))+o(1),}

where

H _{q(x)\equiv} _{def} - x log _{q} \left ({x \over {q -1 }} \right) - ( 1- x) log _{q{(1-x)}}

is the q-ary entropy function and

J _{q(\delta)} \equiv _{def} \left( 1- { 1 \over q}\right)\left( 1- \sqrt{ 1- {q \delta \over{q -1 }}}\right)

is a function related with Johnson bound.

Proof

To prove the Elias–Bassalygo bound, start with the following Lemma:

Lemma. For

C\subseteq [q] ^{n} and 0 \leqslant e\leqslant n , there exists a Hamming ball of radius e with at least (|C| Vol _{q(0,e)})/(q ^{n})

codewords in it.

Proof of Lemma. Randomly pick a received word

y \in [q] ^{n} and let B _{q(y,} 0 ) be the Hamming ball centered at y with radius e . Since y is (uniform) randomly selected the expected size of overlapped region |B _{q(y,e)} \cap C| is (|C| Vol _{q(y,e)})/(q ^{n})

Since this is the expected value of the size, there must exist at least one

y such that |B _{q(y,e)} \cap C| \geqslant {{|C| Vol _{q(y,e)}} \over {q ^{n}}} = {{|C| Vol _{q(0,e)}} \over {q ^{n}},}

otherwise the expectation must be smaller than this value.

Now we prove the Elias–Bassalygo bound. Define

e = n J _{q(\delta)-1.} By Lemma, there exists a Hamming ball with B codewords such that:B\geqslant { {|C| Vol ( 0 ,e)} \over {q ^{n}}}

By the Johnson bound, we have

B\leqslant qdn . Thus, | C | \leqslant qnd ⋅ {{q ^{n}} \over { Vol _{q(0,e)}}} \leqslant q ^{n( 1- H _{q(J} _{q(\delta))+o(1))}}

The second inequality follows from lower bound on the volume of a Hamming ball:

Vol _{q} \left ( 0 , \left \lfloor (d -1)/(2) \right \rfloor \right ) \geqslant q ^{H _{q} \left ( (\delta)/(2) \right )n - o(n)} .

Putting in

d =2 e +1 and \delta = \tfrac{d}{n} gives the second inequality.

Therefore we have

R = { log _{q{|C|}} \over n} \leqslant 1- H _{q(J} _{q(\delta))+o(1)}

See also

• Gilbert–Varshamov bound
• Hamming bound
• Johnson bound
• Plotkin bound
• Singleton bound

Notes and References

1. Each q -ary block code of length n is a subset of the strings of l{A} ^{n,} _{q} where the alphabet set l{A} _{q} has q elements.