Studying error correcting codes is necessary in advancing technology. The safe and reliable transfer of information depends on coding theory. The problem of transferring dependable information is important and this research project attempts to continue incremental progress in this field.
This project has value because the study of error correcting codes is relatively new. Profound advancement can be made in this field and is necessary for the transfer of reliable and safe information. The study of error correcting codes, as conducted in this research project, is specifically related to reliable communications. This is especially pertinent to Naval Reactors as nuke power begins to rely more heavily on computer communications. The need for such communication to be reliable is paramount. Error correcting codes are vital to systems, such as nuclear reactors, that depend upon computers and cannot be allowed to miscommunicate. More knowledge of this topic is crucial to the overarching goals of the Navy. This is especially true if the Navy continues with its plans for unmanned ships. The military depends upon reliable, fault-tolerant communication and this research project aims to continue research in the pertinent field of coding theory.
Another important parameter associated to the code is the number of errors which it can, in principle, correct. The Hamming metric is useful for quantifying such errors. For any two , let denote the number of coordinates where these two vectors differ:
(1) |
(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 , call the matrix a generator matrix for .
The dual code of is the vector space of all code words in which are orthogonal to each codeword in ;
is self-dual if .
be the generator matrix of a code . This is a binary self-dual code. In fact, this is an extremal Type II code (these terms will be defined below).
be the generator matrix of a code . This is a ternary self-dual code. In fact, this is an extremal Type III code (these terms will be defined below).
be the generator matrix of a code . This is a quaternary self-dual code and is referred to as the hexacode. In fact, this is an extremal Type IV code (these terms will be defined below). Note that this code is MDS.
The dual code of has parameters . Moreover, denote the minimum distance of the dual code by . For future reference, note that if then (equating dimensions) , forcing to be even and . The genus of an -code is defined by
This measures how ``far away the code is from being MDS''.
The (Hamming) weight enumerator polynomial is defined by
where
denotes the number of codewords of weight . Let , so therefore . The support of is the set . If then is called a formally self-dual code. The spectrum of is the list of coefficients of :
Two codes are formally equivalent if they have the same spectrum.
The goal of this section is to prove the MacWilliams identity (for simplicity, restricted to the binary case). This identity is necessary to verify the functional equation (4) for the Duursma Zeta Function. Several lemmas are needed to prove this identity. The proof given below follows Hill Ch. 13 [HILL].
proof: Part 1: Let and . Let be a codeword of C such that . Let . Then , for if , then . Similarly . Hence, . Thus, .
Part 2: If , then for all , and so . If then by Part 1, as ranges over the vector space , the quantity takes the value 0 and equally often, giving .
proof:
since , if , and , if .
This is the general statement of the MacWilliams identity. This proof will restrict to the binary case.
proof: Now, express the polynomial in two ways.
On one hand, Lemma 6 implies
On the other hand, reversing the order of summation gives
Replace by in the above gives
Since this polynomial is homogeneous in degree , multiplying both sides by gives the theorem in the binary case.
If , then . Therefore, the MacWilliam's Identity can be rewritten in this case as
where .
is called a virtual self-dual weight enumerator (or VSDWE for short) over having genus.
If is an integer and then the VWE is called -divisible.
It is amazing that the -divisible virtual self-dual weight enumerators can be classified.
Then either
For Assmus and Mattson`s proof of this theorem, please see Sloane [Sl].
Next, in order to carefully define the problem that this paper addresses, the notion of Types of weight enumerators are introduced. Theorem 9 motivates the following definition.
The divisibility condition is extremely restricting and, for example, forces the length to be even. The next sections concentrate on Duursma zeta functions for certain weight enumerators of Type IV.For a proof, see Duursma [D3].
An extremal -divisible virtual self-dual weight enumerator is one for which equality holds in the above theorem. The next section focuses on the Type IV extremal case. With Theorems 9 and 11, the foundations of Duursma's paper [D3] extend from self-dual codes to virtual self-dual weight enumerators. This is because the coding-theoretic versions of the Theorem 9 and 11, used by Duursma, in fact hold for virtual self-dual weight enumerators.
is called a Duursma zeta polynomial of .
where are coefficients which may depend on . The Duursma polynomial is a polynomial of degree . Provided , the Duursma polynomial can be written as . Now, rewrite the terms of degree
by means of the matrix equation given by
The diagonal entries of this matrix are binomial coefficients, hence are non-zero. Therefore the matrix is invertible and the existence is established.
To establish uniqueness, suppose that
and
hold. Subtracting these gives
This forces .
An example will be given in §4.
The Duursma zeta function of is defined in terms of the zeta polynomial by means of
The Duursma zeta function satisfies an analog of the functional equation for the Riemann zeta function. But before stating the functional equation, new notation is needed.
Define by , where
Then there is a functional equation relating and (and hence also and ). Note that even though may not depend on , (and hence ) does.
The Duursma zeta function satisfies the functional equation
This paper concerns the zeros of the zeta function in the case where is an extremal virtual -divisible self-dual weight enumerator of type IV.
Following Duursma [D3], define the ultraspherical polynomial on the interval by
The following theorem^{1} is due to Duursma [D3], section 5.2.
Where and is the Duursma zeta polynomial of an extremal Type IV virtual self-dual weight enumerator of length and minimum distance .
The main result is stated below.
Therefore, all the roots of the degree polynomial , hence the roots of , lie on the circle of radius . According to Duursma [D3], §4.4, all other Type IV extremal virtual self-dual weight enumerators have length of the form or . This verifies the Riemann hypothesis in the case with length divisible by .
The first example below computes a Duursma zeta function ``by hand'' in a simple case.
[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: q = var("q") sage: T = var("T") sage: x = var("x") sage: y = var("y") sage: f1 = lambda q,T,N: sum([ sum([q^i for i in range(k+1)])*T^k for k in range(N)]) sage: f2 = lambda x,y,T,n: sum([ binomial(n,j)*(x-y)^j*y^(n-j)*T^j for j in range(n+1)]) sage: a0,a1,a2,a3,a4 = var("a0,a1,a2,a3,a4") sage: F = expand(f1(2,T,6)*f2(x,y,T,6)*(a0+a1*T+a2*T^2+a3*T^3+a4*T^4))
compute the first terms (as a power series in ) of the series when , , , and . Next, SAGEcomputes the coefficients and read off the matrix :
[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: aa = (F.coeff("T^4")).coeffs("x") sage: v = [expand(aa[i][0]/y^(6-i)) for i in range(5)] sage: B0 = [v[0].coeff("a%s"%str(i)) for i in range(5)] sage: B1 = [v[1].coeff("a%s"%str(i)) for i in range(5)] sage: B2 = [v[2].coeff("a%s"%str(i)) for i in range(5)] sage: B3 = [v[3].coeff("a%s"%str(i)) for i in range(5)] sage: B4 = [v[4].coeff("a%s"%str(i)) for i in range(5)] sage: B0.reverse(); B1.reverse(); B2.reverse(); B3.reverse(); B4.reverse() sage: B = matrix([B0,B1,B2,B3,B4]) sage: B [ 1 -3 4 -2 1] [ 0 6 -12 12 0] [ 0 0 15 -15 15] [ 0 0 0 20 0] [ 0 0 0 0 15]
Note that the diagonal entries are binomial coefficients.
Finally, the vector is determined by solving the equation :
[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: Wmx6 = 3*x^4*y^2+3*x^2*y^4+y^6 sage: c = [Wmx6(1,y).coeff("y^%s"%str(i)) for i in range(2,7)] sage: c.reverse() sage: cc = vector(c) sage: (B^(-1)*cc).list() [4/5, 0, 0, 0, 1/5]This implies that the zeta polynomial of is given by .
The next example illustrates the computation of the Duursma zeta function for a quaternary code.
Here is a more interesting example. Let denote the same element as was defined in Example 3. Let
be a generator matrix of a code . This is an extremal Type IV code over a field with four elements. According to SAGE, the zeta polynomial for this code is . It can be checked directly, using SAGE, that this satisfies the Riemann hypothesis.
[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: F.<z> = GF(4,"z") sage: MS = MatrixSpace(F, 9, 18) sage: G = MS([ ....: [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, z^2, 1, 1, z, 1, 1, z^2, z],\ ....: [0, 1, 0, 0, 0, 0, 0, 0, 0, z^2, z^2, 0, z, 0, 1, z, z^2, z^2],\ ....: [0, 0, 1, 0, 0, 0, 0, 0, 0, z^2, 1, 0, z^2, z^2, z^2, z, 0, z],\ ....: [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, z^2, 1, 0, z^2, z^2, z^2, z, z],\ ....: [0, 0, 0, 0, 1, 0, 0, 0, 0, z, 1, 1, z^2, z^2, 1, 1, z, 1],\ ....: [0, 0, 0, 0, 0, 1, 0, 0, 0, z, z^2, z^2, z^2, 0, 1, z^2, 0, z],\ ....: [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, z, z^2, z^2, z^2, 0, 1, z^2, z],\ ....: [0, 0, 0, 0, 0, 0, 0, 1, 0, z^2, z, 1, 0, z, 0, z^2, z^2, z^2],\ ....: [0, 0, 0, 0, 0, 0, 0, 0, 1, z^2, 1, 1, z, 1, 1, z^2, 1, z]]) sage: C = LinearCode(G) sage: print C.spectrum() [1, 0, 0, 0, 0, 0, 0, 0, 2754, 0, 18360, 0, 77112, 0, 110160, 0, 50949, 0, 2808] sage: R.<T> = PolynomialRing(CC,"T") sage: P = C.sd_zeta_polynomial(4) sage: P 48/143*T^4 + 48/143*T^3 + 32/143*T^2 + 12/143*T + 3/143 sage: rts = R(P).roots() sage: [abs(r[0]) for r in rts] [0.500000000000000, 0.500000000000000, 0.500000000000000, 0.500000000000000]
Background Information: SAGEis a computer algebra program whose open source kernel is written in the Python programming language.
Acknowledgements: I thank the readers of this honors project for their helpful suggestion that improved this presentation. The SAGEexamples are due to my advisor. I also thank Prof. Philippe Gaborit for the generator matrix of the last example and Prof. Thann Ward for the reference to Sloane [Sl].
http://arxiv.org/pdf/math/0510182
,
http://front.math.ucdavis.edu/math.NT/0510182
http://arxiv.org/abs/0704.3903
The command line arguments were:
latex2html -t 'S. Catalano Math Honors Thesis 2007-2008' -no_navigation -split 0 CatalanoHonorsFinal.tex
The translation was initiated by david joyner on 2008-04-21