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 ε > 0. {\displaystyle \varepsilon >0.} For a large enough k {\displaystyle k} , there exists an ensemble of inner codes C i n 1 , ⋯ , C i n N {\displaystyle C_{in}^{1},\cdots ,C_{in}^{N}} of rate 1 2 {\displaystyle {\tfrac {1}{2}}} , where N = q k − 1 {\displaystyle N=q^{k}-1} , such that for at least ( 1 − ε ) N {\displaystyle (1-\varepsilon )N} values of i , C i n i {\displaystyle i,C_{in}^{i}} has relative distance ⩾ H q − 1 ( 1 2 − ε ) {\displaystyle \geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)} . Here relative distance is the ratio of minimum distance to block length. And H q {\displaystyle 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 ) . {\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 α ∈ F q k − { 0 } {\displaystyle \alpha \in \mathbb {F} _{q^{k}}-\{0\}} , define the inner code
{ C i n α : F q k → F q 2 k C i n α ( x ) = ( x , α x ) {\displaystyle {\begin{cases}C_{in}^{\alpha }:\mathbb {F} _{q}^{k}\to \mathbb {F} _{q}^{2k}\\C_{in}^{\alpha }(x)=(x,\alpha x)\end{cases}}}
… excerpt ends here. Continue reading the full article.
