Elias Bassalygo bound

The Elias Bassalygo bound is a mathematical limit used in coding theory for error correction during data transmission or communications.

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

${\displaystyle B_{q}(y,\rho n)=\left\{x\in [q]^{n}\ :\ \Delta (x,y)\leqslant \rho n\right\}}${\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}${\displaystyle \rho n} centered at ${\displaystyle y}${\displaystyle y}. Let ${\displaystyle {\text{Vol}}_{q}(y,\rho n)=|B_{q}(y,\rho n)|}${\displaystyle {\text{Vol}}_{q}(y,\rho n)=|B_{q}(y,\rho n)|} be the volume of the Hamming ball of radius ${\displaystyle \rho n}${\displaystyle \rho n}. It is obvious that the volume of a Hamming Ball is translation-invariant, i.e. indifferent to ${\displaystyle y.}${\displaystyle y.} In particular, ${\displaystyle |B_{q}(y,\rho n)|=|B_{q}(0,\rho n)|.}${\displaystyle |B_{q}(y,\rho n)|=|B_{q}(0,\rho n)|.}

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

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

To prove the Elias–Bassalygo bound, start with the following Lemma:

Lemma. For ${\displaystyle C\subseteq [q]^{n}}${\displaystyle C\subseteq [q]^{n}} and ${\displaystyle 0\leqslant e\leqslant n}${\displaystyle 0\leqslant e\leqslant n}, there exists a Hamming ball of radius ${\displaystyle e}${\displaystyle e} with at least

${\displaystyle {\frac {|C|{\text{Vol}}_{q}(0,e)}{q^{n}}}}${\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}}${\displaystyle y\in [q]^{n}} and let ${\displaystyle B_{q}(y,0)}${\displaystyle B_{q}(y,0)} be the Hamming ball centered at ${\displaystyle y}${\displaystyle y} with radius ${\displaystyle e}${\displaystyle e}. Since ${\displaystyle y}${\displaystyle y} is (uniform) randomly selected the expected size of overlapped region ${\displaystyle |B_{q}(y,e)\cap C|}${\displaystyle |B_{q}(y,e)\cap C|} is

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

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

By the Johnson bound, we have ${\displaystyle B\leqslant qdn}${\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))}}${\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)}.}${\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}${\displaystyle d=2e+1} and ${\displaystyle \delta ={\tfrac {d}{n}}}${\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)}${\displaystyle R={\log _{q}{|C|} \over n}\leqslant 1-H_{q}(J_{q}(\delta ))+o(1)}

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

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

• Coding theory

• Articles containing proofs