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$ .Each $q$ -ary block code of length $n$ is a subset of the strings of $\mathcal{A}_q^n,$ where the alphabet set $\mathcal{A}_q$ has $q$ elements. 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 = n J_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)

References

{{Citation

| title = New upper bounds for error-correcting codes

| year = 1965

| author = Bassalygo, L. A.

| journal = Problems of Information Transmission

| pages = 32–35

| volume = 1

| issue = 1

}}

{{Citation

| title = Lower bounds to error probability for coding on discrete memoryless channels. Part I.

| year = 1967

| journal = Information and Control

| pages = 65–103

| volume = 10

| last1 = Claude E. Shannon | first1 = Robert G. Gallager

| last2 = Berlekamp

| first2 = Elwyn R.

| doi=10.1016/s0019-9958(67)90052-6

| doi-access = free

}}

{{Citation

| title = Lower bounds to error probability for coding on discrete memoryless channels. Part II.

| year = 1967

| journal = Information and Control

| pages = 522–552

| volume = 10

| last1 = Claude E. Shannon | first1 = Robert G. Gallager

| last2 = Berlekamp

| first2 = Elwyn R.

| doi=10.1016/s0019-9958(67)91200-4

| doi-access = free

}}

Category:Coding theory

Category:Articles containing proofs

Elias Bassalygo bound

Definition

Proof

See also

References