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 $C$ be a $q$-ary code of length $n$, i.e. a subset of $[q{]}^n$. Let $R$ be the rate of $C$, $\delta$ the relative distance and

$B_q(y,\rho n)=\{x\in [q{]}^n:\mathrm{\Delta }(x,y)⩽\rho n\}$

be the Hamming ball of radius $\rho n$ centered at $y$. Let ${\text{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⩽1-H_q(J_q(\delta ))+o(1),$

where

$H_q(x){\equiv }_{\text{def}}-x{\log }_q\left(\frac{x}{q-1}\right)-(1-x){\log }_q(1-x)$

is the q-ary entropy function and

$J_q(\delta ){\equiv }_{\text{def}}(1-\frac{1}{q})(1-\sqrt{1-\frac{q\delta }{q-1}})$

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⩽e⩽n$, there exists a Hamming ball of radius $e$ with at least

$\frac{|C|{\text{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

$\frac{|C|{\text{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|⩾\frac{|C|{\text{Vol}}_q(y,e)}{q^n}=\frac{|C|{\text{Vol}}_q(0,e)}{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⩾\frac{|C|\text{Vol}(0,e)}{q^n}$

By the Johnson bound, we have $B⩽qdn$. Thus,

$|C|⩽qnd\cdot \frac{q^n}{{\text{Vol}}_q(0,e)}⩽q^{n(1-H_q(J_q(\delta ))+o(1))}$

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

${\text{Vol}}_q(0,\lfloor \frac{d-1}{2}\rfloor )⩾q^{H_q\left(\frac{\delta }{2}\right)n-o(n)}.$

Putting in $d=2e+1$ and $\delta =\frac{d}{n}$ gives the second inequality.

Therefore we have

$R=\frac{{\log }_q|C|}{n}⩽1-H_q(J_q(\delta ))+o(1)$

See also

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