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)=\left\{x\in [q]^{n}\ :\ \Delta (x,y)\leqslant \rho n\right\}$

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\leqslant 1-H_{q}(J_{q}(\delta ))+o(1),$

where

$H_{q}(x)\equiv _{\text{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 _{\text{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

${\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|\geqslant {{|C|{\text{Vol}}_{q}(y,e)} \over {q^{n}}}={{|C|{\text{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=nJ_{q}(\delta )-1.$ By Lemma, there exists a Hamming ball with $B$ codewords such that:

$B\geqslant {{|C|{\text{Vol}}(0,e)} \over {q^{n}}}$

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

$|C|\leqslant qnd\cdot {{q^{n}} \over {{\text{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:

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

Putting in $d=2e+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

References

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