Wozencraft ensemble

{{ safesubst:#invoke:Unsubst||$N=Refimprove |date=__DATE__ |$B= {{#invoke:Message box|ambox}} }} In coding theory, the Wozencraft ensemble is a set of linear codes in which most of codes satisfy the Gilbert-Varshamov bound. It is named after John Wozencraft, who proved its existence. The ensemble is described by Template:Harvtxt, who attributes it to Wozencraft. Template:Harvtxt used the Wozencraft ensemble as the inner codes in his construction of strongly explicit asymptotically good code.

Existence theorem

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

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)=xlog_{q}(q-1)-xlog_{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 $\alpha \in \mathbb {F} _{q^{k}}-\{0\}$ , the inner code $C_{in}^{\alpha }:\mathbb {F} _{q}^{k}\to \mathbb {F} _{q}^{2k}$ , is defined as $C_{in}^{\alpha }(x)=(x,\alpha x)$ . Here we can notice that $x\in \mathbb {F} _{q}^{k}$ and $\alpha \in \mathbb {F} _{q^{k}}$ . We can do the multiplication $\alpha x$ since $\mathbb {F} _{q}^{k}$ is isomorphic to $\mathbb {F} _{q^{k}}$ .

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

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

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

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

Proof

To prove that there are at least $(1-\varepsilon )N$ number of linear codes in the Wozencraft ensemble having relative distance $\geq H_{q}^{-1}({\frac {1}{2}}-\varepsilon )$ , we will prove that there are at most $\varepsilon N$ number of linear codes having relative distance < $H_{q}^{-1}({\frac {1}{2}}-\varepsilon )$ (i.e., having the distance < $H_{q}^{-1}({\frac {1}{2}}-\varepsilon )\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 the weight less than $H_{q}^{-1}({\frac {1}{2}}-\varepsilon )\cdot 2k$ , then that code has the distance less than $H_{q}^{-1}({\frac {1}{2}}-\varepsilon )\cdot 2k$ .

So $P$ = the number of linear codes having the distance less than $H_{q}^{-1}({\frac {1}{2}}-\varepsilon )\cdot 2k$ = the number of linear codes having some codeword that has the weight less than $H_{q}^{-1}({\frac {1}{2}}-\varepsilon )\cdot 2k$ .

Now we have the following claim:

Claim: Two linear codes $C_{in}^{\alpha _{1}}$ and $C_{in}^{\alpha _{2}}$ (here $\alpha _{1}\neq \alpha _{2}\in \mathbb {F} _{q^{k}}-\{0\}$ ) do not share any non-zero codeword.

Proof of Claim:

We prove the above claim by contradiction. Suppose there exist $\alpha _{1}\neq \alpha _{2}\in \mathbb {F} _{q^{k}}-\{0\}$ such that two linear codes $C_{in}^{\alpha _{1}}$ and $C_{in}^{\alpha _{2}}$ contain the same non-zero codeword y.

Now since $y\in C_{in}^{\alpha _{1}}-\{0\}$ , $y=(y_{1},\alpha _{1}y_{1})$ for some $y_{1}\in \mathbb {F} _{q}^{k}$ . As $y$ is non-zero, $y_{1}\neq 0$ .

So $(y_{1},\alpha _{1}y_{1})=(y_{2},\alpha _{2}y_{2})$ , then $y_{1}=y_{2}\neq 0$ and $\alpha _{1}y_{1}=\alpha _{2}y_{2}$ .

This implies $\alpha _{1}=\alpha _{2}$ , which is a contradiction, which completes the proof of the claim.

Now we come back to the proof of the theorem.

With any linear code having distance < $H_{q}^{-1}({\frac {1}{2}}-\varepsilon )\cdot 2k$ , it has some codeword that has the weight less than $H_{q}^{-1}({\frac {1}{2}}-\varepsilon )\cdot 2k$ .

Also due to the Claim, notice that no two linear code share the same non-zero codewords. This implies that if we have $P$ linear codes having distance < $H_{q}^{-1}({\frac {1}{2}}-\varepsilon )\cdot 2k$ , then we have at least $P$ different $y$ such that $wt(y)$ < $H_{q}^{-1}({\frac {1}{2}}-\varepsilon )\cdot 2k$ (one such codeword $y$ for each linear code). Here $wt(y)$ denotes the weight of codeword $y$ , which is the number of non-zero positions of $y$ .