Elias Bassalygo bound

The Elias-Bassalygo bound is a mathematical limit used in coding theory for error correction during data transmission or communications. The properties of the Elias-Bassalygo bound are defined, below, using mathematical expressions.

Definition

Let $C$ be a $q$-ary code of length $n$, i.e. a subset of $[q]^n$. (Each $q$-ary block code of length $n$ is a subset of the strings of $\mathcal{A}_q^n\text{,}$ where the alphabet set $\mathcal{A}_q$ has $q$ elements). Let $R$ be the rate of $C$ and $\delta$ (delta) be the relative distance.

Let $B_q(\boldsymbol{y}, \rho n) =\{ \boldsymbol{x} \in [q]^n | \Delta(\boldsymbol{x}, \boldsymbol{y}) \le \rho n \}$ be the Hamming ball of radius $\rho n$ centered at $\boldsymbol{y}$. Let $Vol_q(\boldsymbol{y}, \rho n) = |B_q(\boldsymbol{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. irrelevant with position of $\boldsymbol{y}$. In particular, $|B_q(\boldsymbol{y}, \rho n)| =|B_q(\boldsymbol{0}, \rho n)|$ .

With large enough $n$, the rate $R$ and the relative distance $\delta$ satisfies the Elias-Bassalygo bound: $R \le 1 - H_q( J_q(\delta))+o(1)\text{,}$

where

$H_q(x)\equiv_ \text{def} -x\cdot\log_q{x \over {q-1}}-(1-x)\cdot\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 1: Given a q-ary code, $C\subseteq [q]^n$ and $0\le e\le n$, there exists a Hamming ball of radius $e$ with at least ${|C|Vol_q(0,e)} \over {q^n}$ codewords in it.

Proof of Lemma 1: To prove Lemma 1, use the probability method. Randomly pick a received word $y \in [q]^n$. The expected size of overlapped region between $C$ and the Hamming ball centered at $y$ with radius $e$, $|B_q(y,e) \cap C|$ is $Vol_q(y,e) {{|C|} \over {q^n}}$ since $y$ is (uniform) randomly selected. Since this is the expected value of the size, there must exist at least one $y$ such that $|B_q(y,e) \cap C| \ge Vol_q(y,e) {{|C|} \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 1, there exists a Hamming ball with $B$ codewords such that $B\ge { {|C|Vol(0,e)} \over {q^n}}$

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

$\mid C \mid \le qnd \cdot {{q^n} \over {Vol_q(0,e)}} \le 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(0, \lfloor {{d-1} \over 2} \rfloor) \le q^{H_q({\delta \over 2})n-o(n)}$.

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

Therefore we have

$R={\log_q{|C|} \over n} \le 1-H_q(J_q(\delta))+o(1)$

See also

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

References

Bassalygo, L. A. (1965), "New upper boundes 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