Wozencraft ensemble

Template:Refimprove 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 $\epsilon >0.$ For a large enough $k$, there exists an ensemble of inner codes $C_{in}^1,\cdots ,C_{in}^N$ of rate $\frac{1}{2}$, where $N=q^k-1$, such that for at least $(1-\epsilon )N$ values of $i,C_{in}^i$ has relative distance $⩾H_q^{-1}(\frac{1}{2}-\epsilon )$.

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{\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 $\alpha \in {𝔽}_{q^k}-\{0\}$, define the inner code

$\{\begin{array}{c}{C}_{in}^{\alpha }:{𝔽}_q^k\to {𝔽}_q^{2k}\\ C_{in}^{\alpha }(x)=(x,\alpha x)\end{array}$

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

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

For all $x,y\in {𝔽}_q^k$, we have the following facts:

1. $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 $a\in {𝔽}_q,a{C}_{in}^{\alpha }(x)=a(x,\alpha x)=(ax,\alpha (ax))=C_{in}^{\alpha }(ax)$

So $C_{in}^{\alpha }$ is a linear code for every $\alpha \in {𝔽}_{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 $(1-\epsilon )N$ those linear codes having the relative distance $⩾H_q^{-1}(\frac{1}{2}-\epsilon )$, i.e. they meet the Gilbert-Varshamov bound.

Proof

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

Let $P$ be the set of linear codes having distance $<H_q^{-1}(\frac{1}{2}-\epsilon )\cdot 2k.$ Then there are $|P|$ linear codes having some codeword that has weight $<H_q^{-1}(\frac{1}{2}-\epsilon )\cdot 2k.$

Lemma. Two linear codes $C_{in}^{{\alpha }_1}$ and $C_{in}^{{\alpha }_2}$ with ${\alpha }_1,{\alpha }_2\in {𝔽}_{q^k}$ distinct and non-zero, do not share any non-zero codeword.

Proof. Suppose there exist distinct non-zero elements ${\alpha }_1,{\alpha }_2\in {𝔽}_{q^k}$ such that the 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},y=(y_1,{\alpha }_1{y}_1)$ for some $y_1\in {𝔽}_q^k$ and similarly $y=(y_2,{\alpha }_2{y}_2)$ for some $y_2\in {𝔽}_q^k.$ Moreover since $y$ is non-zero we have $y_1,y_2\ne 0.$ Therefore $(y_1,{\alpha }_1{y}_1)=(y_2,{\alpha }_2{y}_2)$, then $y_1=y_2\ne 0$ and ${\alpha }_1{y}_1={\alpha }_2{y}_2.$ This implies ${\alpha }_1={\alpha }_2$, which is a contradiction.

Any linear code having distance $<H_q^{-1}(\frac{1}{2}-\epsilon )\cdot 2k$ has some codeword of weight $<H_q^{-1}(\frac{1}{2}-\epsilon )\cdot 2k.$ Now the Lemma implies that we have at least $|P|$ different $y$ such that $wt(y)<H_q^{-1}(\frac{1}{2}-\epsilon )\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$.

Denote

$S=\{y:wt(y)<H_q^{-1}(\frac{1}{2}-\epsilon )\cdot 2k\}$

Then:

$\begin{array}{cc}|P|& ⩽|S|\\ & ⩽{\text{Vol}}_q(H_q^{-1}(\frac{1}{2}-\epsilon )\cdot 2k,2k)& & {\text{Vol}}_q(r,n)\text{ is the volume of Hamming ball of radius }r\text{ in }[q{]}^n\\ & ⩽q^{H_q\left(H_q^{-1}(\frac{1}{2}-\epsilon )\right)\cdot 2k}& & {\text{Vol}}_q(pn,n)⩽q^{H_q(p)n}\\ & =q^{(\frac{1}{2}-\epsilon )\cdot 2k}\\ & =q^{k(1-2\epsilon )}\\ & <\epsilon (q^k-1)& & \text{ for }k\text{ large enough }\\ & =\epsilon N\end{array}$

So $|P|<\epsilon N$, therefore the set of linear codes having the relative distance $⩾H_q^{-1}(\frac{1}{2}-\epsilon )\cdot 2k$ has at least $N-\epsilon N=(1-\epsilon )N$ elements.

See also

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

References

• Template:Citation.
• Template:Citation.

External links

• 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.
• Template:Cite journal
• Coding Theory's Notes: Gilbert-Varshamov Bound. Venkatesan Guruswami