Wozencraft ensemble

From formulasearchengine
Jump to navigation Jump to search

{{ safesubst:#invoke:Unsubst||$N=Refimprove |date=__DATE__ |$B= {{#invoke:Message box|ambox}} }} 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 Template:Harvtxt, who attributes it to Wozencraft. Template:Harvtxt used the Wozencraft ensemble as the inner codes in his construction of strongly explicit asymptotically good code.

Existence theorem

Theorem: Let > 0. For a large enough , there exists an ensemble of inner codes of rate , where , such that for at least values of i, 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 , the inner code , is defined as . 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 any x and y in , we have the following facts:

  1. 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

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 the 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 the weight less than , then that code has the distance less than .

So = the number of linear codes having the distance less than = the number of linear codes having some codeword that has the weight less than .

Now we have the following claim:

Claim: Two linear codes and (here ) do not share any non-zero codeword.

Proof of Claim:

We prove the above claim by contradiction. Suppose there exist such that two linear codes and contain the same non-zero codeword y.

Now since , for some . As is non-zero, .

Similarly, for some .

So , then and .

This implies , which is a contradiction, which completes the proof of the claim.

Now we come back to the proof of the theorem.

With any linear code having distance < , it has some codeword that has the weight less than .

Also due to the Claim, notice that no two linear code share the same non-zero codewords. This implies that if we have linear codes having distance < , then 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 .

So (the number of linear codes having distance < ) is less than or equal the number of non-zero such that wt(y) < .

Denote <

So

Here is the Volume of Hamming ball of radius r in .

Recall the upper bound of the Volume of Hamming ball (check Bounds on the Volume of a Hamming ball for proof's detail), we have:

When is large enough, we have <

So < .

That means the number of linear codes having the relative distance < is less than . So the number of linear codes having the relative distance at least is greater than , which completes the proof.

See also

References

  • {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

  • {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

External links

|CitationClass=journal }}