User:ECCclass/Elias-Bassalygo

{{multiple issues|cleanup=May 2010|confusing=May 2010|sections=May 2010|tone=May 2010|unreferenced=May 2010|orphan}} {{expert|date=May 2010}} Let $C$ be a $q$ -ary code of length $n$ , i.e. a subset of $[q]^{n}$ . Let $R$ be the rate of $C$ and $\delta$ be the relative distance.

Let $B_{q}({\boldsymbol {y}},\rho n)=\{{\boldsymbol {x}}\in [q]^{n}|\Delta ({\boldsymbol {x}},{\boldsymbol {y}})\leq \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 </math>\boldsymbol{y}</math>. 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\leq 1-H_{q}(J_{q}(\delta ))+o(1)$

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}}(1-{1 \over q})(1-{\sqrt {1-{q\delta  \over {q-1}}}}

is a function related with Johnson bound

To prove the Elias–Bassalygo bound, we'll need the following Lemma:

Lemma 1: Given a q-ary code, $C\subseteq [q]^{n}$ and $0\leq e\leq 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: We prove Lemma 1 using probability method. Let's random 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|\geq 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=nJ_{q}(\delta )-1$ .

By Lemma 1, there exists a Hamming ball with $B$ codewords such that $B\geq {{|C|Vol(0,e)} \over {q^{n}}}$

By Johnson Bound Johnson bound, we have $B\leq qdn$ . Thus,

$\mid C\mid \leq qnd\cdot {{q^{n}} \over {Vol_{q}(0,e)}}\leq 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 )\leq 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}\leq 1-H_{q}(J_{q}(\delta ))+o(1)

See also