Wozencraft ensemble

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

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

${\displaystyle H_{q}(x)=x\log _{q}(q-1)-x\log _{q}x-(1-x)\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 ${\displaystyle \alpha \in \mathbb {F} _{q^{k}}-\{0\}}$, define the inner code

${\displaystyle {\begin{cases}C_{in}^{\alpha }:\mathbb {F} _{q}^{k}\to \mathbb {F} _{q}^{2k}\\C_{in}^{\alpha }(x)=(x,\alpha x)\end{cases}}}$

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

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

For all ${\displaystyle x,y\in \mathbb {F} _{q}^{k}}$, we have the following facts:

1. ${\displaystyle C_{in}^{\alpha }(x)+C_{in}^{\alpha }(y)=(x,\alpha x)+(y,\alpha y)=(x+y,\alpha (x+y))=C_{in}^{\alpha }(x+y)}$
2. For any ${\displaystyle a\in \mathbb {F} _{q},aC_{in}^{\alpha }(x)=a(x,\alpha x)=(ax,\alpha (ax))=C_{in}^{\alpha }(ax)}$

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

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

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

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 ${\displaystyle <H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k}$, then that code has distance ${\displaystyle <H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.}$

Let ${\displaystyle P}$ be the set of linear codes having distance ${\displaystyle <H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.}$ Then there are ${\displaystyle |P|}$ linear codes having some codeword that has weight ${\displaystyle <H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.}$

Lemma. Two linear codes ${\displaystyle C_{in}^{\alpha _{1}}}$ and ${\displaystyle C_{in}^{\alpha _{2}}}$ with ${\displaystyle \alpha _{1},\alpha _{2}\in \mathbb {F} _{q^{k}}}$ distinct and non-zero, do not share any non-zero codeword.

Proof. Suppose there exist distinct non-zero elements ${\displaystyle \alpha _{1},\alpha _{2}\in \mathbb {F} _{q^{k}}}$ such that the linear codes ${\displaystyle C_{in}^{\alpha _{1}}}$ and ${\displaystyle C_{in}^{\alpha _{2}}}$ contain the same non-zero codeword ${\displaystyle y.}$ Now since ${\displaystyle y\in C_{in}^{\alpha _{1}},y=(y_{1},\alpha _{1}y_{1})}$ for some ${\displaystyle y_{1}\in \mathbb {F} _{q}^{k}}$ and similarly ${\displaystyle y=(y_{2},\alpha _{2}y_{2})}$ for some ${\displaystyle y_{2}\in \mathbb {F} _{q}^{k}.}$ Moreover since ${\displaystyle y}$ is non-zero we have ${\displaystyle y_{1},y_{2}\neq 0.}$ Therefore ${\displaystyle (y_{1},\alpha _{1}y_{1})=(y_{2},\alpha _{2}y_{2})}$, then ${\displaystyle y_{1}=y_{2}\neq 0}$ and ${\displaystyle \alpha _{1}y_{1}=\alpha _{2}y_{2}.}$ This implies ${\displaystyle \alpha _{1}=\alpha _{2}}$, which is a contradiction.

Any linear code having distance ${\displaystyle <H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k}$ has some codeword of weight ${\displaystyle <H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.}$ Now the Lemma implies that we have at least ${\displaystyle |P|}$ different ${\displaystyle y}$ such that ${\displaystyle wt(y)<H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k}$ (one such codeword ${\displaystyle y}$ for each linear code). Here ${\displaystyle wt(y)}$ denotes the weight of codeword ${\displaystyle y}$, which is the number of non-zero positions of ${\displaystyle y}$.

Denote

${\displaystyle S=\left\{y\$ :\ wt(y)<H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k\right\}}

Then:[1]

${\displaystyle {\begin{aligned}|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{aligned}}}$

So ${\displaystyle |P|<\varepsilon N}$, therefore the set of linear codes having the relative distance ${\displaystyle \geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k}$ has at least ${\displaystyle N-\varepsilon N=(1-\varepsilon )N}$ elements.

• Justesen code
• Linear code
• Hamming bound

• Massey, James L. (1963), Threshold decoding, Tech. Report 410, Cambridge, Mass.: Massachusetts Institute of Technology, Research Laboratory of Electronics, hdl:1721.1/4415, MR 0154763.
• Justesen, Jørn (1972), "A class of constructive asymptotically good algebraic codes", Institute of Electrical and Electronics Engineers. Transactions on Information Theory, IT-18 (5): 652–656, doi:10.1109/TIT.1972.1054893, MR 0384313.

• Lecture 28: Justesen Code. Coding theory's course. Prof. Atri Rudra.
• Lecture 9: Bounds on the Volume of a Hamming Ball. Coding theory's course. Prof. Atri Rudra.
• J. Justesen (1972). "A class of constructive asymptotically good algebraic codes". IEEE Trans. Inf. Theory. 18 (5): 652–656. doi:10.1109/TIT.1972.1054893.
• Coding Theory's Notes: Gilbert-Varshamov Bound. Venkatesan Guruswami