Wozencraft ensemble

:Theorem: Let $\backslash varepsilon\; >\; 0.$ For a large enough $k$, there exists an ensemble of inner codes $C\_\{in\}^1,\backslash cdots,C\_\{in\}^N$ of rate $\backslash tfrac\{1\}\{2\}$, where $N\; =\; q^k\; -\; 1$, such that for at least $(1\; -\; \backslash varepsilon)N$ values of $i,\; C\_\{in\}^i$ has relative distance $\backslash geqslant\; H\_q^\{\; -\; 1\}\; \backslash left(\backslash tfrac\{1\}\{2\}\; -\; \backslash varepsilon\; \backslash right\; )$.

Here relative distance is the ratio of minimum distance to block length. And $H\_q$ is the q-ary entropy function defined as follows:

:$H\_q(x)\; =\; x\backslash log\_q(q-1)-x\backslash log\_qx-(1-x)\backslash log\_q(1-x).$

In fact, to show the existence of this set of linear codes, we will specify this ensemble explicitly as follows: for $\backslash alpha\; \backslash in\; \backslash mathbb\{F\}\_\{q^k\; \}\; -\; \backslash \{\; 0\backslash \}$, define the inner code

:$\backslash begin\{cases\}\; C\_\{in\}^\backslash alpha\; :\backslash mathbb\{F\}\_q^k\; \backslash to\; \backslash mathbb\{F\}\_q^\{2k\}\; \backslash \backslash \; C\_\{in\}^\backslash alpha\; (x)\; =\; (x,\backslash alpha\; x)\; \backslash end\{cases\}$

Here we can notice that $x\; \backslash in\; \backslash mathbb\{F\}\_q^k$ and $\backslash alpha\; \backslash in\; \backslash mathbb\{F\}\_\{q^k\}$. We can do the multiplication $\backslash alpha\; x$ since $\backslash mathbb\{F\}\_q^k$ is isomorphic to $\backslash mathbb\{F\}\_\{q^k\}$.

This ensemble is due to Wozencraft and is called the Wozencraft ensemble.

For all $x,\; y\; \backslash in\; \backslash mathbb\{F\}\_q^k$, we have the following facts:

1. $C\_\{in\}^\backslash alpha\; (x)\; +\; C\_\{in\}^\backslash alpha\; (y)\; =\; (x,\backslash alpha\; x)+(y,\backslash alpha\; y)\; =\; (x\; +\; y,\backslash alpha\; (x\; +\; y))\; =\; C\_\{in\}^\backslash alpha\; (x\; +\; y)$
2. For any $a\; \backslash in\; \backslash mathbb\{F\}\_q,\; aC\_\{in\}^\backslash alpha\; (x)\; =\; a(x,\backslash alpha\; x)\; =\; (ax,\backslash alpha\; (ax))\; =\; C\_\{in\}^\backslash alpha\; (ax)$

So $C\_\{in\}^\backslash alpha$ is a linear code for every $\backslash alpha\; \backslash in\; \backslash mathbb\{F\}\_\{q^k\; \}\; -\; \backslash \{\; 0\backslash \}$.

Now we know that Wozencraft ensemble contains linear codes with rate $\backslash tfrac\{1\}\{2\}$. In the following proof, we will show that there are at least $(1\; -\; \backslash varepsilon)N$ those linear codes having the relative distance $\backslash geqslant\; H\_q^\{\; -\; 1\}\; \backslash left\; (\backslash tfrac\{1\}\{2\}\; -\; \backslash varepsilon\; \backslash right\; )$, i.e. they meet the Gilbert-Varshamov bound.

To prove that there are at least $(1-\backslash varepsilon)N$ number of linear codes in the Wozencraft ensemble having relative distance $\backslash geqslant\; H\_q^\{-1\}\backslash left(\backslash tfrac\{1\}\{2\}-\backslash varepsilon\; \backslash right)$, we will prove that there are at most $\backslash varepsilon\; N$ number of linear codes having relative distance i.e., having distance

Notice that in a linear code, the distance is equal to the minimum weight of all codewords of that code. This fact is the property of linear code. So if one non-zero codeword has weight , then that code has distance

Let $P$ be the set of linear codes having distance Then there are $|P|$ linear codes having some codeword that has weight

:Lemma. Two linear codes $C\_\{in\}^\{\backslash alpha\_1\}$ and $C\_\{in\}^\{\backslash alpha\_2\}$ with $\backslash alpha\_1,\; \backslash alpha\_2\; \backslash in\; \backslash mathbb\{F\}\_\{q^k\}$ distinct and non-zero, do not share any non-zero codeword.

:Proof. Suppose there exist distinct non-zero elements $\backslash alpha\_1,\; \backslash alpha\_2\; \backslash in\; \backslash mathbb\{F\}\_\{q^k\}$ such that the linear codes $C\_\{in\}^\{\backslash alpha\_1\}$ and $C\_\{in\}^\{\backslash alpha\_2\}$ contain the same non-zero codeword $y.$ Now since $y\; \backslash in\; C\_\{in\}^\{\backslash alpha\_1\},\; y\; =\; (y\_1,\backslash alpha\_1\; y\_1)$ for some $y\_1\; \backslash in\; \backslash mathbb\{F\}\_q^k$ and similarly $y\; =\; (y\_2,\backslash alpha\_2\; y\_2)$ for some $y\_2\; \backslash in\; \backslash mathbb\{F\}\_q^k.$ Moreover since $y$ is non-zero we have $y\_1,\; y\_2\; \backslash ne\; 0.$ Therefore $(y\_1,\backslash alpha\_1\; y\_1)\; =\; (y\_2,\backslash alpha\_2\; y\_2)$, then $y\_1\; =\; y\_2\; \backslash ne\; 0$ and $\backslash alpha\_1\; y\_1\; =\; \backslash alpha\_2\; y\_2.$ This implies $\backslash alpha\_1\; =\; \backslash alpha\_2$, which is a contradiction.

Any linear code having distance

Denote

:

Then:For the upper bound of the volume of Hamming ball check [http://www.cse.buffalo.edu/~atri/courses/coding-theory/lectures/lect9.pdf Bounds on the Volume of a Hamming ball]

:$\backslash begin\{align\}$

|P| &\leqslant |S| \\

&\leqslant \text{Vol}_q \left (H_q^{-1} \left (\tfrac{1}{2}-\varepsilon \right ) \cdot 2k,2k \right ) && \text{Vol}_q(r,n) \text{ is the volume of Hamming ball of radius } r \text{ in } [q]^n \\

&\leqslant q^{H_q \left (H_q^{-1}\left (\frac{1}{2}-\varepsilon \right ) \right ) \cdot 2k} && \text{Vol}_q(pn,n) \leqslant q^{H_q(p )n} \\

&= q^{ \left (\frac{1}{2}-\varepsilon \right ) \cdot 2k} \\

&= q^{k(1-2\varepsilon)} \\

&< \varepsilon(q^k-1) && \text{ for } k \text{ large enough } \\

&= \varepsilon N

\end{align}

So , therefore the set of linear codes having the relative distance $\backslash geqslant\; H\_q^\{-1\}\; \backslash left\; (\backslash tfrac\{1\}\{2\}-\backslash varepsilon\; \backslash right\; )\; \backslash cdot\; 2k$ has at least $N\; -\; \backslash varepsilon\; N\; =\; (1-\backslash varepsilon)N$ elements.

• Hamming ball
• Hamming bound
• Justesen code
• Linear code

{{Reflist}}

• {{citation

| last = Massey | first = James L.

| location = Cambridge, Mass.

| mr = 0154763

| publisher = Massachusetts Institute of Technology, Research Laboratory of Electronics

| series = Tech. Report 410

| title = Threshold decoding

| hdl = 1721.1/4415

| year = 1963| hdl-access = free

}}.

• {{citation

| last = Justesen | first = Jørn

| doi = 10.1109/TIT.1972.1054893

| journal = IEEE Transactions on Information Theory

| mr = 0384313

| pages = 652–656

| title = A class of constructive asymptotically good algebraic codes

| volume = IT-18

| year = 1972| issue = 5

}}.

• [http://www.cse.buffalo.edu/~atri/courses/coding-theory/ Lecture 28: Justesen Code. Coding theory's course. Prof. Atri Rudra].
• [http://www.cse.buffalo.edu/~atri/courses/coding-theory/lectures/lect9.pdf Lecture 9: Bounds on the Volume of a Hamming Ball. Coding theory's course. Prof. Atri Rudra].
• {{cite journal | author=J. Justesen | title=A class of constructive asymptotically good algebraic codes | journal= IEEE Transactions on Information Theory| volume=18 | year=1972 | issue=5 | pages=652–656 | doi=10.1109/TIT.1972.1054893 }}
• [https://www.cs.cmu.edu/~venkatg/teaching/codingtheory/ Coding Theory's Notes: Gilbert-Varshamov Bound. Venkatesan Guruswami]

Category:Error detection and correction