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

${\displaystyle B_{q}(y,\rho n)=\left\{x\in [q]^{n}\$ :\ \Delta (x,y)\leqslant \rho n\right\}}

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

With large enough ${\displaystyle n}$, the rate${\displaystyle R}$ and the relative distance${\displaystyle \delta }$ satisfy the Elias-Bassalygo bound:

${\displaystyle R\leqslant 1-H_{q}(J_{q}(\delta ))+o(1),}$

where

${\displaystyle 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

${\displaystyle 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 ${\displaystyle C\subseteq [q]^{n}}$ and ${\displaystyle 0\leqslant e\leqslant n}$, there exists a Hamming ball of radius ${\displaystyle e}$ with at least

${\displaystyle {\frac {|C|{\text{Vol}}_{q}(0,e)}{q^{n}}}}$

codewords in it.

Proof of Lemma. Randomly pick a received word ${\displaystyle y\in [q]^{n}}$ and let ${\displaystyle B_{q}(y,0)}$ be the Hamming ball centered at ${\displaystyle y}$ with radius ${\displaystyle e}$. Since ${\displaystyle y}$ is (uniform) randomly selected the expected size of overlapped region ${\displaystyle |B_{q}(y,e)\cap C|}$ is

${\displaystyle {\frac {|C|{\text{Vol}}_{q}(y,e)}{q^{n}}}}$

Since this is the expected value of the size, there must exist at least one ${\displaystyle y}$ such that

${\displaystyle |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 ${\displaystyle e=nJ_{q}(\delta )-1.}$ By Lemma, there exists a Hamming ball with ${\displaystyle B}$ codewords such that:

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

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

${\displaystyle |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:

${\displaystyle {\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 ${\displaystyle d=2e+1}$ and ${\displaystyle \delta ={\tfrac {d}{n}}}$ gives the second inequality.

Therefore we have

${\displaystyle R={\log _{q}{|C|} \over n}\leqslant 1-H_{q}(J_{q}(\delta ))+o(1)}$

See also

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

References

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

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