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.
Here relative distance is the ratio of minimum distance to block length.
is the q-ary entropy function defined as follows: In fact, to show the existence of this set of linear codes, we will specify this ensemble explicitly as follows: for
α ∈
, define the inner code Here we can notice that
α x
This ensemble is due to Wozencraft and is called the Wozencraft ensemble.
is a linear code for every
Now we know that Wozencraft ensemble contains linear codes with rate
In the following proof, we will show that there are at least
those linear codes having the relative distance
, i.e. they meet the Gilbert-Varshamov bound.
number of linear codes in the Wozencraft ensemble having relative distance
number of linear codes having relative distance
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
, then that code has distance
be the set of linear codes having distance
linear codes having some codeword that has weight
Any linear code having distance
has some codeword of weight
Now the Lemma implies that we have at least
for each linear code).
denotes the weight of codeword
, which is the number of non-zero positions of
, therefore the set of linear codes having the relative distance