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 (Massey 1963), who attributes it to Wozencraft. (Justesen 1972) used the Wozencraft ensemble as the inner codes in his construction of strongly explicit asymptotically good code.
Existence theorem
- Theorem: Let [math]\displaystyle{ \varepsilon \gt 0. }[/math] For a large enough [math]\displaystyle{ k }[/math], there exists an ensemble of inner codes [math]\displaystyle{ C_{in}^1,\cdots,C_{in}^N }[/math] of rate [math]\displaystyle{ \tfrac{1}{2} }[/math], where [math]\displaystyle{ N = q^k - 1 }[/math], such that for at least [math]\displaystyle{ (1 - \varepsilon)N }[/math] values of [math]\displaystyle{ i, C_{in}^i }[/math] has relative distance [math]\displaystyle{ \geqslant H_q^{ - 1} \left(\tfrac{1}{2} - \varepsilon \right ) }[/math].
Here relative distance is the ratio of minimum distance to block length. And [math]\displaystyle{ H_q }[/math] is the q-ary entropy function defined as follows:
- [math]\displaystyle{ H_q(x) = x\log_q(q-1)-x\log_qx-(1-x)\log_q(1-x). }[/math]
In fact, to show the existence of this set of linear codes, we will specify this ensemble explicitly as follows: for [math]\displaystyle{ \alpha \in \mathbb{F}_{q^k } - \{ 0\} }[/math], define the inner code
- [math]\displaystyle{ \begin{cases} C_{in}^\alpha :\mathbb{F}_q^k \to \mathbb{F}_q^{2k} \\ C_{in}^\alpha (x) = (x,\alpha x) \end{cases} }[/math]
Here we can notice that [math]\displaystyle{ x \in \mathbb{F}_q^k }[/math] and [math]\displaystyle{ \alpha \in \mathbb{F}_{q^k} }[/math]. We can do the multiplication [math]\displaystyle{ \alpha x }[/math] since [math]\displaystyle{ \mathbb{F}_q^k }[/math] is isomorphic to [math]\displaystyle{ \mathbb{F}_{q^k} }[/math].
This ensemble is due to Wozencraft and is called the Wozencraft ensemble.
For all [math]\displaystyle{ x, y \in \mathbb{F}_q^k }[/math], we have the following facts:
- [math]\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) }[/math]
- For any [math]\displaystyle{ a \in \mathbb{F}_q, aC_{in}^\alpha (x) = a(x,\alpha x) = (ax,\alpha (ax)) = C_{in}^\alpha (ax) }[/math]
So [math]\displaystyle{ C_{in}^\alpha }[/math] is a linear code for every [math]\displaystyle{ \alpha \in \mathbb{F}_{q^k } - \{ 0\} }[/math].
Now we know that Wozencraft ensemble contains linear codes with rate [math]\displaystyle{ \tfrac{1}{2} }[/math]. In the following proof, we will show that there are at least [math]\displaystyle{ (1 - \varepsilon)N }[/math] those linear codes having the relative distance [math]\displaystyle{ \geqslant H_q^{ - 1} \left (\tfrac{1}{2} - \varepsilon \right ) }[/math], i.e. they meet the Gilbert-Varshamov bound.
Proof
To prove that there are at least [math]\displaystyle{ (1-\varepsilon)N }[/math] number of linear codes in the Wozencraft ensemble having relative distance [math]\displaystyle{ \geqslant H_q^{-1}\left(\tfrac{1}{2}-\varepsilon \right) }[/math], we will prove that there are at most [math]\displaystyle{ \varepsilon N }[/math] number of linear codes having relative distance [math]\displaystyle{ \lt H_q^{-1}\left(\tfrac{1}{2}-\varepsilon \right) }[/math] i.e., having distance [math]\displaystyle{ \lt H_q^{-1}\left(\tfrac{1}{2}-\varepsilon \right) \cdot 2k. }[/math]
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 [math]\displaystyle{ \lt H_q^{-1}\left(\tfrac{1}{2}-\varepsilon \right) \cdot 2k }[/math], then that code has distance [math]\displaystyle{ \lt H_q^{-1}\left(\tfrac{1}{2}-\varepsilon \right) \cdot 2k. }[/math]
Let [math]\displaystyle{ P }[/math] be the set of linear codes having distance [math]\displaystyle{ \lt H_q^{-1}\left(\tfrac{1}{2}-\varepsilon \right) \cdot 2k. }[/math] Then there are [math]\displaystyle{ |P| }[/math] linear codes having some codeword that has weight [math]\displaystyle{ \lt H_q^{-1}\left(\tfrac{1}{2}-\varepsilon \right) \cdot 2k. }[/math]
- Lemma. Two linear codes [math]\displaystyle{ C_{in}^{\alpha_1} }[/math] and [math]\displaystyle{ C_{in}^{\alpha_2} }[/math] with [math]\displaystyle{ \alpha_1, \alpha_2 \in \mathbb{F}_{q^k} }[/math] distinct and non-zero, do not share any non-zero codeword.
- Proof. Suppose there exist distinct non-zero elements [math]\displaystyle{ \alpha_1, \alpha_2 \in \mathbb{F}_{q^k} }[/math] such that the linear codes [math]\displaystyle{ C_{in}^{\alpha_1} }[/math] and [math]\displaystyle{ C_{in}^{\alpha_2} }[/math] contain the same non-zero codeword [math]\displaystyle{ y. }[/math] Now since [math]\displaystyle{ y \in C_{in}^{\alpha_1}, y = (y_1,\alpha_1 y_1) }[/math] for some [math]\displaystyle{ y_1 \in \mathbb{F}_q^k }[/math] and similarly [math]\displaystyle{ y = (y_2,\alpha_2 y_2) }[/math] for some [math]\displaystyle{ y_2 \in \mathbb{F}_q^k. }[/math] Moreover since [math]\displaystyle{ y }[/math] is non-zero we have [math]\displaystyle{ y_1, y_2 \ne 0. }[/math] Therefore [math]\displaystyle{ (y_1,\alpha_1 y_1) = (y_2,\alpha_2 y_2) }[/math], then [math]\displaystyle{ y_1 = y_2 \ne 0 }[/math] and [math]\displaystyle{ \alpha_1 y_1 = \alpha_2 y_2. }[/math] This implies [math]\displaystyle{ \alpha_1 = \alpha_2 }[/math], which is a contradiction.
Any linear code having distance [math]\displaystyle{ \lt H_q^{-1}\left(\tfrac{1}{2}-\varepsilon \right) \cdot 2k }[/math] has some codeword of weight [math]\displaystyle{ \lt H_q^{-1}\left(\tfrac{1}{2}-\varepsilon \right) \cdot 2k. }[/math] Now the Lemma implies that we have at least [math]\displaystyle{ |P| }[/math] different [math]\displaystyle{ y }[/math] such that [math]\displaystyle{ wt(y) \lt H_q^{-1}\left(\tfrac{1}{2}-\varepsilon \right) \cdot 2k }[/math] (one such codeword [math]\displaystyle{ y }[/math] for each linear code). Here [math]\displaystyle{ wt(y) }[/math] denotes the weight of codeword [math]\displaystyle{ y }[/math], which is the number of non-zero positions of [math]\displaystyle{ y }[/math].
Denote
- [math]\displaystyle{ S = \left \{ y \ : \ wt(y) \lt H_q^{ - 1} \left (\tfrac{1}{2} - \varepsilon \right ) \cdot 2k \right \} }[/math]
Then:[1]
- [math]\displaystyle{ \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)} \\ &\lt \varepsilon(q^k-1) && \text{ for } k \text{ large enough } \\ &= \varepsilon N \end{align} }[/math]
So [math]\displaystyle{ |P| \lt \varepsilon N }[/math], therefore the set of linear codes having the relative distance [math]\displaystyle{ \geqslant H_q^{-1} \left (\tfrac{1}{2}-\varepsilon \right ) \cdot 2k }[/math] has at least [math]\displaystyle{ N - \varepsilon N = (1-\varepsilon)N }[/math] elements.
See also
References
- ↑ For the upper bound of the volume of Hamming ball check Bounds on the Volume of a Hamming ball
- Massey, James L. (1963), Threshold decoding, Tech. Report 410, Cambridge, Mass.: Massachusetts Institute of Technology, Research Laboratory of Electronics.
- 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.
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.
- 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
 |  |
