Wozencraft Ensemble

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 , who attributes it to Wozencraft. 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_^1,\cdots,C_^N$ of rate $\tfrac$, where $N = q^k - 1$, such that for at least $(1 - \varepsilon)N$ values of $i, C_^i$ has relative distance $\geqslant H_q^ \left(\tfrac - \varepsilon \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\log_q(q-1)-x\log_qx-(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_ - \$, define the inner code

:$\begin C_^\alpha :\mathbb_q^k \to \mathbb_q^ \\ C_^\alpha (x) = (x,\alpha x) \end$

Here we can notice that $x \in \mathbb_q^k$ and $\alpha \in \mathbb_$. We can do the multiplication $\alpha x$ since $\mathbb_q^k$ is isomorphic to $\mathbb_$.

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

For all $x, y \in \mathbb_q^k$, we have the following facts:
# $C_^\alpha (x) + C_^\alpha (y) = (x,\alpha x)+(y,\alpha y) = (x + y,\alpha (x + y)) = C_^\alpha (x + y)$
# For any $a \in \mathbb_q, aC_^\alpha (x) = a(x,\alpha x) = (ax,\alpha (ax)) = C_^\alpha (ax)$

So $C_^\alpha$ is a linear code for every $\alpha \in \mathbb_ - \$.

Now we know that Wozencraft ensemble contains linear codes with rate $\tfrac$. In the following proof, we will show that there are at least $(1 - \varepsilon)N$ those linear codes having the relative distance $\geqslant H_q^ \left (\tfrac - \varepsilon \right )$, 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 $\geqslant H_q^\left(\tfrac-\varepsilon \right)$, we will prove that there are at most $\varepsilon N$ number of linear codes having relative distance $< H_q^\left(\tfrac-\varepsilon \right)$ i.e., having distance $< H_q^\left(\tfrac-\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 $< H_q^\left(\tfrac-\varepsilon \right) \cdot 2k$, then that code has distance $< H_q^\left(\tfrac-\varepsilon \right) \cdot 2k.$

Let $P$ be the set of linear codes having distance $< H_q^\left(\tfrac-\varepsilon \right) \cdot 2k.$ Then there are $, P,$ linear codes having some codeword that has weight $< H_q^\left(\tfrac-\varepsilon \right) \cdot 2k.$

:Lemma. Two linear codes $C_^$ and $C_^$ with $\alpha_1, \alpha_2 \in \mathbb_$ distinct and non-zero, do not share any non-zero codeword.

:Proof. Suppose there exist distinct non-zero elements $\alpha_1, \alpha_2 \in \mathbb_$ such that the linear codes $C_^$ and $C_^$ contain the same non-zero codeword $y.$ Now since $y \in C_^, y = (y_1,\alpha_1 y_1)$ for some $y_1 \in \mathbb_q^k$ and similarly $y = (y_2,\alpha_2 y_2)$ for some $y_2 \in \mathbb_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 has some codeword of weight $< H_q^\left(\tfrac-\varepsilon \right) \cdot 2k.$ Now the Lemma implies that we have at least $, P,$ different $y$ such that $wt(y) < H_q^\left(\tfrac-\varepsilon \right) \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 = \left \$

Then:For the upper bound of the volume of Hamming ball chec
Bounds on the Volume of a Hamming ball
/ref>

: \begin
, P, &\leqslant , S, \\
&\leqslant \text_q \left (H_q^ \left (\tfrac-\varepsilon \right ) \cdot 2k,2k \right ) && \text_q(r,n) \text r \text n \\
&\leqslant q^ && \text_q(pn,n) \leqslant q^ \\
&= q^ \\
&= q^ \\
&< \varepsilon(q^k-1) && \text k \text \\
&= \varepsilon N
\end

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

See also

* Hamming bound
* Justesen code
* Linear code

References

*.
*.

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

* {{cite journal , author=J. Justesen , title=A class of constructive asymptotically good algebraic codes , journal=IEEE Trans. Inf. Theory , volume=18 , year=1972 , issue=5 , pages=652–656 , doi=10.1109/TIT.1972.1054893

Coding Theory's Notes: Gilbert-Varshamov Bound. Venkatesan Guruswami

Error detection and correction