Wozencraft ensemble
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.
Contents
Existence theorem[edit]
- Theorem: Let For a large enough , there exists an ensemble of inner codes of rate , where , such that for at least values of has relative distance .
Here relative distance is the ratio of minimum distance to block length. And 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 and . We can do the multiplication since is isomorphic to .
This ensemble is due to Wozencraft and is called the Wozencraft ensemble.
For all , we have the following facts:
- For any
So 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.
Proof[edit]
To prove that there are at least number of linear codes in the Wozencraft ensemble having relative distance , we will prove that there are at most number of linear codes having relative distance i.e., having 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
Let be the set of linear codes having distance Then there are linear codes having some codeword that has weight
- Lemma. Two linear codes and with distinct and non-zero, do not share any non-zero codeword.
- Proof. Suppose there exist distinct non-zero elements such that the linear codes and contain the same non-zero codeword Now since for some and similarly for some Moreover since is non-zero we have Therefore , then and This implies , which is a contradiction.
Any linear code having distance has some codeword of weight Now the Lemma implies that we have at least different such that (one such codeword for each linear code). Here denotes the weight of codeword , which is the number of non-zero positions of .
Denote
Then:
So , therefore the set of linear codes having the relative distance has at least elements.
See Also on BitcoinWiki[edit]
Source[edit]