Greg Coy^{1}
Another important parameter is the smallest weight of any non-zero codeword, . This is related to error-correction because can correct errors.
We will construct an interesting family of codes which have the property that has a limit and has a limit . We will also investigate how this family violates the ``fake Goppa conjecture." Moreover, we can show that the Goppa conjecture is incompatible with a conjecture on hyperelliptic curves over finite fields, which we call the ``small content conjecture."
Another important parameter associated to the code is the number of errors which it can, in principle, correct. For this notion, we need to introduce the Hamming metric. For any two , let denote the number of coordinates where these two vectors differ:
(1) |
This is called the Hamming distance or Hamming metric. Define the weight of to be the number of non-zero entries of . Note, because the vector has non-zero entries only at locations where and differ. The smallest distance between distinct codewords in a linear code is the minimum distance of :
(2) |
A linear code of length and dimension over has a basis of vectors of length . If those vectors are arranged as rows of a matrix , then we call the matrix a generator matrix for .
Cyclic codewords are conveniently represented as polynomials modulo . In fact, if then let
Denote by the ring of polynomials with coefficients in modulo :
In fact the algebraic software package GUAVA allows you to easily pass back and forth between codewords as vectors and codewords as polynomials.
In order to define the generator polynomial of a cyclic code we need the following mathematical fact.
Proof Suppose not. Let be a non-zero element in of smallest degree. Pick an arbitrary non-zero element in . By the division algorithm, we can write where and are polynomials and either or the degree of is strictly less than the degree of . Notice that belongs to by definition. This contradicts the assumption that has smallest degree unless . Therefore every element of is a multiple of . Take .
More generally we have the following result:
We define to be a quadratic residue if is a square in the finite field . Let denote the subset of quadratic residues and denote the subset of non-quadratic residues.
A simple observation is that is a subgroup of , in particular a quadratic residue times another quadratic residue is a quadratic residue. Similarly, a quadratic residue times a quadratic non-residue is a quadratic non-residue. In particular we can represent the quotient using two elements, the identity and a fixed quadratic non-residue:
Observe that by the above discussion the Legendre symbol is a multiplicative character on .
Now let us define the family of quadratic residue codes.
Note that these generator polynomials, and both divide . By the lemma above .
For any binary code of length let denote the extended code defined by
For example if is the code above then belongs to since belongs to .
Recall that ([MS],§1.9), the check matrix of is
One of the most remarkable facts about quadratic residue codes is the following theorem.
Recall that the automorphism group of a binary code of length is the group of all permutations of the coordinates which send codewords to codewords.
We intend to extend the Gleason-Prange theorem to a new class of codes studied here (called ``QQR codes").
If , let . Let be the quadratic residue character, which is on the set quadratic residues in , on the set non-quadratic residues, and is 0 on . Let and denotes the polynomial
Define the QQR code as
If is a nonzero codeword of the binary code then the weight of this codeword can be expressed in terms of a character sum as
In fact, looking carefully at their proof, one finds the following result:
Let , then we have
Case 1. If is even and then so odd implies that is even, since 0 is not included in or . Likewise, even implies that is odd. Therefore .
Case 2. If is even and then parity parity . If is even then and if is odd then .
Case 3. is odd. We claim that . (Proof: Let and . Then , which is obviously a contradiction. Therefore , so Replace by to prove the claim.) Also note that
Conclusion.
Remarks on QQR Codes: These codes have very interesting but unexplained behavior. The conjecture of Bazzi-Mitter that they (or a subsequence of them) form a ``good family'' of codes (where the rate, relative minimum distance pair stays bounded away from the axes and ) seems not to be consistent with the above (very limited) data on values, except possibly in the case .
For a result similar in spirit to the lemma above, see also [HV]. For more information on quadratic residue codes, see [MS], [HP], [vLM], and [W].
We now introduce a new code, constructed similarly to the Quasi-Quadratic Residue Codes discussed earlier:
For any , let
We know that
We have the following trivial estimates:
This implies the minimum non-zero weight of satisfies , when .
We now compute the size of . We now prove the claim: if then the map that sends to the codeword is injective. This implies . Suppose not, then there are two subsets that are mapped to the same codeword. Subtracting, the subset satisfies . If is even then . This forces to be the empty set, so . Now if is odd then similar reasoning implies that is the empty set. Therefore, and or vice versa. This proves the claim.
In case , claim: . Again, suppose there are two subsets that are mapped to the same codeword. Then the subset for which . This implies either or . Therefore, either or .
We have proven the following result.
First, a few observations.
For any , let denote the set which is if , and if .
By (5), it suffices to find the minimum non-zero weight of , . We first find a ``duality'' relation between and , and and .
By (6), it is obvious that if then .
If then , so
(7) |
By (5), we have
(9) |
Let us denote the map by and its inverse (which only exists if ) by .
When , define ``addition'' on by
The surprising fact is the following result.
Proof Assume . Recall from the above discussion that is a 2-to-1 map from the set of subsets of to the codewords of . For all , there is a and (for ) if and only if or . We know . This implies does not depend on the choice in , made to compute the right-hand side of (10).
This operation is commutative, since the symmetric difference operation is symmetric, and it is associative since is associative. Each element is the inverse of itself and the element is the identity.
Therefore, is a vector space over with the operation . When , the set of codewords , a singleton subset of , form a basis. When , the set of codewords , a singleton subset of , are linearly dependent (their sum is 0), so do not form a basis. However, if you just omit one (any one - pick your least favorite), you get a basis.
Define the metric as follows. For , let
We make a few remarks comparing to . If is written , for polynomials , then
We assert that, with this notion of addition, the ``-Hamming metric'' on is the more ``natural'' one to use.
This and the previous section prove the following result.
Here is an example from Amin Shokrollahi [S].
This example will construct, in a naive way, a set of vectors, call it , in , and an addition in , such that is a binary vector space under , and such that the weight of is always at least (this construction gets you all the way to the ``fake Singleton" bound). Here it is.
Let denote the -dimensional vector in which all entries are . Let . For and let . Under this ``addition" becomes a binary vector space. The weight of any element in is , so the -distance of any two elements in , defined as the weight of their -addition, is . This is a code of length , dimension , and minimum -distance , so the fake singleton bound is almost attained. In particular, we have asymptotic rate and relatively minimum -distance .
Here is sometimes referred to as the entropy of the code.
The Gilbert-Varshamov bound implies that there is a code with relative minimum distance and rate . However our code above yields and .
Therefore we have constructed a linear binary code which beats the -Gilbert-Varshamov bound, thereby disproving the fake Goppa's conjecture.
Goppa's conjecture was investigated recently by Jiang and Vardy [JV], where they proved that there is a code (possibly non-linear) of ``sufficiently large" length and minimum distance which has at least elements, where is a positive constant which they do not determine. Our result is somewhat different because we show that if then the rate can be taken larger than that predicted either by analogs of the Gilbert-Varshamov bound or the Jiang-Vardy bound.
For an infinite number of primes for which , the content of is less than .
Acknowledgements: I thank Prof. Amin Shokrollahi of the Ecole Polytechnique Federale de Lausanne in Switzerland for his helpful remarks.
(http://www.gap-system.org)
.
The command line arguments were:
latex2html -t 'G. Coy Math Honors Thesis 2005-2006' -split 0 finalhonorspaper.tex
The translation was initiated by David Joyner on 2006-04-19