Cyclic Codes and Quadratic Residue Codes over Z_{4}

Vera Pless^{∗} and Zhongqiang Qian

Department of Mathematics, Statistics and Computer Science University of Illinois at Chicago

September 3, 1996

∗This work was supported in part by NSA grant MDA 904-91-H-0003.

List of Tables

I The Z_{4} cyclic codes of length 7 . . . . . . . . . . . . . . . . . 15 II The weight distribution of the Gray image of the length 32 code 27 Abstract. A set of n−tuples over Z_{4} is called a code over Z_{4} or a Z_{4} code if it is a Z_{4} module. In this paper we prove that any Z_{4}−cyclic code C has generators of the form (fh, 2fg) where fgh = x^{n} − 1 over Z_{4} and |C| = 4^{degg}2^{degh}. We also show that C^{⊥} has generators of the form (g^{⋆}h^{⋆}, 2f^{⋆}g^{⋆}). We show that idempotent generators exist for certain cyclic codes. A particularly interesting family of Z_{4} − cyclic codes are quadratic residue codes. We define such codes in terms of their idempotent generators and show that these codes also have many good properties which are analogous in many respects to properties of quadratic residue codes over a field. We show that the non-linear binary images of the extended Q.R codes of lengths 32 and 48 have higher minimum weights than comparable known linear codes.

Index Terms. Generators and Idempotents of Z_{4}−Cyclic Codes, Z_{4}−Quadratic Residue Codes.

I Introduction

Let Z_{4} denote the integers modulo 4. Z_{4} is a ring which has 2 as a zero divisor. A set of n − tuples over Z_{4} is called a code over Z_{4} or a Z_{4} code if it is a Z_{4} module. Throughout this paper, notation is as in [11].

In this paper we prove that any Z_{4} − cyclic code C has generators of the form (fh, 2fg) where fgh = x^{n} − 1 over Z_{4} and |C| = 4^{degg}2^{degh}. We also show that C^{⊥} has generators of the form (g^{⋆}h^{⋆}, 2f^{⋆}g^{⋆}). We show when a Z_{4}− cyclic code has an idempotent generator. A particularly interesting family of Z_{4}−cyclic codes are quadratic residue codes. We define such codes in terms of their idempotent generators and show that these codes also have many good properties which are analogous in many respects to the quadratic residue codes over a field. The symmetrized Lee weight enumerators of length 32 and 48 Z_{4}− quadratic residue codes are given in the Appendix. The binary images of these codes are nonlinear and have better minimum Hamming weights than comparable linear codes [2].

II Z_{4}−cyclic codes, their generators and idempotents

The structure of the ring

R = Z_{q}[x]/(x^{n} − 1)

where q is a power of prime, has been fully studied in [3]. Lemma 3 is an immediate result of Theorem 3 in [3] and if x^{n} − 1 = fgh, generators of the form (fh, 2fg) can be derived from Theorem 6 in [3] since (fh, 2f) = (fh, 2fg) because (g, h) = 1. However the results in this section have been studied independently and the proofs are different and more elementary. In particular, Theorem 2 provides a mechanism to find the size of a Z_{4}− cyclic code and the dual of the code which can not be derived from the results in [3].

Let μ: Z_{4}[x] → Z_{2}[x] be the map which sends 0, 2 to 0; 1, 3 to 1 and x to x.

Definition. A polynomial f in Z_{4}[x] is basic irreducible if μf is irreducible in Z_{2}[x]; f is primary if (f) is a primary ideal [10].

Lemma 1. If f(x) is a basic irreducible polynomial, then f(x) is primary.

Proof. Suppose g(x)h(x) ∈ (f(x)). Since μf(x) is irreducible,

gcd(μg(x), μf(x)) = 1 or μf(x).

If gcd(μg(x), μf(x)) = 1, then f(x) divides h(x). Otherwise, there are u(x) and v(x) in Z_{4}[x] such that g(x) = f(x)u(x) + 2v(x). Squaring both sides, we see that g^{2}(x) ∈ (f(x)).

A local ring is a ring that has a unique maximal ideal. If R is a local ring, the polynomial ring R[x] may not be a unique factorization domain. But some special polynomials in R[x] may have the unique factorization property. An example of such polynomials are regular polynomials. A regular polynomial is a polynomial which is not a zero divisor in R[x]. In our case the local ring is Z_{4} and any polynomial which has some nonzero coefficient not equal to 2 is regular. In particular, x^{n} − 1 is regular. By Hensel’s lemma [10], x^{n} − 1 is the product of basic irreducible polynomials and such polynomials are primary by Lemma 1. Hence by Factorization Theorem in [10, page 263], we immediately get the following.

Lemma 2. If x^{n} − 1 = f_{1}f_{2} ⋯ f_{r}, where the f_{i} are basic irreducible and pairwise coprime, then this factorization is unique.

The following lemma discusses the structure of the ring Z_{4}[x]/(f(x)) for a basic irreducible polynomial f(x).

Lemma 3. If f(x) is in Z_{4}[x] and is basic irreducible, then the only ideals of Z_{4}[x]/(f(x)) are (0), (1) and (2).

Proof. Suppose I is a nonzero ideal of the ring Z_{4}[x]/(f(x)) and g(x)+(f(x)) is in I for some g(x) ∉ (f(x)). Since

gcd(μg(x), μf(x)) = 1 or μf(x),

g(x) + (f(x)) is either invertible in the ring Z_{4}[x]/(f(x)) or is an element of (2 + (f(x))). If g(x) + (f(x)) is invertible, then

I = Z_{4}[x]/(f(x)).

Otherwise,

I ⊆ (2 + (f(x))).

In this case there is an element 2r(x) + (f(x)) ≠ 0 ∈ I. We can suppose μr(x) ∉ (μf(x)), since otherwise there are u(x), v(x) in Z_{4}[x] such that

r(x) = f(x)u(x) + 2v(x).

Then 2r(x) = 2f(x)u(x), which implies 2r(x) + (f(x)) = 0 in the ring Z_{4}[x]/(f(x)). So, if μr(x) is not in (μf(x)), then

gcd(μr(x), μf(x)) = 1.

Hence there are u(x), v(x) and w(x) in Z_{4}[x] such that

r(x)u(x) + f(x)v(x) = 1 + 2w(x).

Therefore,

2r(x)u(x) + 2f(x)v(x) = 2,

i.e, 2 + (f(x)) is in I because I is an ideal. Hence I = (2 + (f(x))).

Let ℜ_{n} = Z_{4}[x]/(x^{n} − 1). As usual, if C is a Z_{4} cyclic code of length n, an element c = (a_{0}, a_{1}, ⋯, a_{n−1}) in C is identified with a polynomial a_{0} + a_{1}x + a_{2}x^{2} + ⋯ a_{n−1}x^{n−1} modulo x^{n} − 1. Under this correspondence, a code is Z_{4} cyclic if and only if it is an ideal in the ring ℜ_{n}.

Theorem 1. Let x^{n} − 1 = f_{1}f_{2} ⋯ f_{r} be a product of basic irreducible and pairwise coprime polynomials for odd n, and let f̂_{i} denote the product of all f_{j} except f_{i}. Then any ideal in the ring ℜ_{n} is a sum of some (f̂_{i}) and (2f̂_{i}).

Proof. By Hensel’s lemma, such a factorization of x^{n}−1 exists and is unique by the corollary.

Since the f_{i} are basic irreducible and pairwise coprime, by induction it is easy to show that

(f_{1}f_{2}....f_{r}) = (f_{1}) ∩ (f_{2}) ∩ (f_{3}) ∩ ⋯ ∩ (f_{r}).

Applying the Chinese Remainder Theorem [7, page 131], we have

ℜ_{n} = Z_{4}[x]/(f_{1})∩(f_{2})∩(f_{3})∩⋯∩(f_{r}) ≅ Z_{4}[x]/(f_{1})⊕Z_{4}[x]/(f_{2})⊕⋯⊕Z_{4}[x]/(f_{r}).

If I is an ideal of ℜ_{n}, then

I ≅ I_{1} ⊕ I_{2} ⊕ ⋯ ⊕ I_{r}

[7, page 135], where I_{i} is an ideal of the ring Z_{4}[x]/(f_{i}), for i = 1, 2, ⋯, r. By Lemma 2,

I_{i} = 0, Z_{4}[x]/(f_{i}) or (2 + (f_{i})).

If I_{i} = Z_{4}[x]/(f_{i}), then it corresponds to the ideal (f̂_{i}) in the ring ℜ_{n}, if I_{i} = (2 + (f_{i})), then it corresponds to the ideal (2f̂_{i}). In any case, the ideal I is a sum of (f̂_{i}) and (2f̂_{j}).

The following Corollary is also in [1].

Corollary. The number of Z_{4} cyclic codes of length n is 3^{r}, where r is the number of basic irreducible polynomial factors in x^{n} − 1.

If f is a polynomial, f^{∗} denotes its reciprocal polynomial.

Theorem 2. Suppose C is a Z_{4}− cyclic code of odd length n. Then there are unique, monic polynomials f, g and h such that C = (fh, 2fg), where fgh=x^{n} − 1, and |C|=4^{degg}2^{degh}.

When h = 1, C = (f) and |C| = 4^{n−degf};

When g = 1, C = (2f) and |C| = 2^{n−degf}.

Proof. We know that x^{n} − 1 has a unique factorization such that x^{n} − 1 = f_{1}f_{2} ⋯ f_{r}, where the f_{i} are basic irreducible and pairwise coprime.We also know, by Theorem 1, that C is a sum of (f̂_{i}) and (2f̂_{j}). By permuting the subscripts of f_{i}, we can suppose that C is a sum of

(f̂_{k+1}), (f̂_{k+2}), ⋯, (f̂_{k+l}), (2f̂_{k+l+1}), (2f̂_{k+l+2}), ⋯, (2f̂_{r}).

Then

C = (f_{1}f_{2} ⋯ f_{k}f_{k+l+1}f_{k+l+2} ⋯ f_{r}, 2f_{1}f_{2} ⋯ f_{k}f_{k+1} ⋯ f_{k+l}) = (fh, 2fg),

where

f = f_{1}f_{2} ⋯ f_{k}, g = f_{k+1}f_{k+2} ⋯ f_{k+l} or 1 if l = 0

and

h = f_{k+l+1}f_{k+l+2} ⋯ f_{r} or 1 if k + l = r.

When h ≠ 1, fh and g are coprime, (fh) ∩ (2fg) = 0. Therefore

| C |=| fh || 2fg |= 4^{n−deg(f)−deg(h)}2^{n−deg(f)−deg(g)}.

When h = 1, the above identity is still true because in this case C = (f) and

| C |=| fh || 2fg |= 4^{n−deg(f)−deg(h)}2^{n−deg(f)−deg(g)} = 4^{n−deg(f)}.

The following theorem is the same as [11, Theorem 47] except that the field is replaced by a ring. We state it here without proof.

Theorem 3: Let

a(x) = a_{0} + a_{1}x + ⋯ + a_{n−1}x^{n−1}

and

b(x) = b_{0} + b_{1}x + ⋯ + b_{n−1}x^{n−1},

then a(x)b(x) = 0 in ℜ_{n} iff the vector (a_{0}, a_{1}, ⋯, a_{n−1}) is orthogonal to the vector (b_{n−1}, b_{n−2}, ⋯, b_{0}) and all its cyclic shifts.

The next theorem discusses the dual of C.

Theorem 4. Let C = (fh, 2fg) be a Z_{4} cyclic code of odd length n, where f, g and h are monic polynomials such that fgh = x^{n} − 1 and |C| = 4^{degg}2^{degh}. Then

C^{⊥} = (g^{∗}h^{∗}, 2g^{∗}f^{∗}) and |C^{⊥}| = 4^{degf}2^{degh}.

If h = 1, then C = (f) and C^{⊥} = (g^{∗});

If g = 1, then C = (2f) and C^{⊥} = (h^{∗}, 2f^{∗}).

Proof. We know that

(g^{∗}h^{∗}) ⊆ (g^{∗}) ⊆ (fh, 2fg)^{⊥}

and similarly

(2g^{∗}f^{∗}) ⊆ (g^{∗}) ⊆ (fh, 2fg)^{⊥}.

Therefore,

(g^{∗}h^{∗}, 2g^{∗}f^{∗}) ⊆ (fh, 2fg)^{⊥}.

Since

| (g^{∗}h^{∗}, 2g^{∗}f^{∗}) |= 4^{n−deg(g)−deg(h)}2^{n−deg(g)−deg(f)} =| (fh, 2fg)^{⊥} | we have

(g^{∗}h^{∗}, 2g^{∗}f^{∗}) = (fh, 2fg)^{⊥}.

An idempotent in Z_{4}[x] is defined to be a polynomial e(x) such that e(x)^{2} ≡ e(x) (mod x^{n} − 1).

Theorem 5. Let C be a Z_{4}− cyclic code of odd length n. ( i ) If C = (f), where fg = x^{n} − 1 for some g,

then C has an idempotent generator in Z_{4}. (ii) If C=(2f) and f divides x^{n} − 1, then C=(2e),

where e is an binary idempotent generator of (μf). (iii) If C=(fh, 2fg), where fgh = x^{n} − 1, then C=(e, 2ν),

where e is an idempotent in Z_{4}, ν is an idempotent in Z_{2}.

Proof. In (i), because f and g are coprime, there are u and v in Z_{4}[x] such that fu + gv = 1. Set e = fu, then e = 1 − gv and e^{2} = e − gev = e (mod x^{n} − 1). fe = f − fgv = f (mod x^{n} − 1). Hence (e) = (f);

In (ii), (2f) = (2e) follows from the fact that 2f = 2μf and (μf) has binary idempotent e.

In (iii), it is clear from (i) and (ii) that (fh) has an idempotent e in Z_{4} and (μfg) has the binary idempotent ν. Therefore (fh, 2fg) = (e, 2ν).

If we know the idempotent generator of a Z_{4} code, by the following theorem we can also find the idempotent generator of the dual code.

Theorem 6. If a Z_{4}− cyclic code C has the idempotent generator e(x), then C^{⊥} has the idempotent generator 1 − e(x^{−1}).

Proof. Since e(x)(1 − e(x)) = 0 in ℜ_{n}, by Theorem 4, e(x) is orthogonal to 1 − e(x^{−1}). That is, 1 − e(x^{−1}) ∈ C^{⊥}. On the other hand, if C has generator polynomial g and gh = x^{n} − 1, then C^{⊥} has generator polynomial h^{∗}. Since 1 − e(x) is the idempotent generator of (h), and the map: x → x^{−1} sends (h) to (h^{∗}), 1 − e(x^{−1}) is the idempotent generator of C^{⊥}.

If e_{1} and e_{2} are idempotents, then it is easy to see that

e_{1}e_{2} and e_{1} + e_{2} − e_{1}e_{2}

are also idempotents. Let C_{1} = (e_{1}) and C_{2} = (e_{2}), then it is simple to verify that

e_{1}e_{2} and e_{1} + e_{2} − e_{1}e_{2}

are the multiplicative identities of C_{1} ∩ C_{2} and C_{1} + C_{2} respectively. This proves the following theorem:

Theorem 7. Let C_{1} and C_{2} be cyclic codes with idempotent generators e_{1} and e_{2}, then C_{1} ∩ C_{2} has the idempotent generator e_{1}e_{2} and C_{1} + C_{2} has the idempotent generator e_{1} + e_{2} − e_{1}e_{2} .

For odd n, x^{n} − 1 = f_{1}f_{2} ⋯ f_{r} is a product of basic irreducible, pairwise coprime polynomials. We know [11, page 80] that there are binary idempotents e_{1}, e_{2}, ⋯, e_{r} with (μf̂_{i}) = (e_{i}) such that

e_{1} + e_{2} + ⋯ + e_{r} = 1

and

e_{i}e_{j} = 0, if i ≠ j.

These e_{i} are called primitive idempotents and any binary idempotent is the sum of some e_{i}.

In Z_{4}, let θ_{i} = e_{i}^{2}, for i = 1, 2, ⋯, r. It was shown in [1], that the θ_{i} are Z_{4} idempotents. Moreover, it can also be shown that

∑_{i=1}^{r} θ_{i} = 1 andθ_{i}θ_{j} = 0 for i ≠ j.

Example. Z_{4} cyclic codes of length 7.

x^{7} − 1 = (x − 1)(3 + x + 2x^{2} + x^{3})(3 + 2x + 3x^{2} + x^{3}) = f_{0}f_{1}f_{2}. Let

e_{1} = x + x^{2} + x^{4} and e_{2} = x^{3} + x^{5} + x^{6}

be binary idempotents. Then we know that in the binary case,

h = 1 + e_{1} + e_{2}

is the idempotent generator of μf_{1}μf_{2};

1 + e_{2}

is the idempotent generator of μf_{0}μf_{1} and

1 + e_{1}

is the idempotent generator of μf_{0}μf_{2}. It is easy to verify that θ_{0} = h^{2} = 3h, θ_{1} = (1 + e_{2})^{2} = 1 + 3e_{2} + 2e_{1}, θ_{2} = (1 + e_{1})^{2} = 1 + 3e_{1} + 2e_{2}. ¿From this we can list all non-trivial cyclic codes along with their idempotent generators and their dual codes (see Table I).

Table I: The Z_{4} cyclic codes of length 7

generator polynomial idempotent generator order dual
f_{1}f_{2}  3h  4  f_{0}
f_{0}f_{1}  1 + 3e_{2} + 2e_{1}  4^{3}  f_{1}
f_{0}f_{2}  1 + 3e_{1} + 2e_{2}  4^{3}  f_{2}
2f_{1}f_{2}  2h  2  (f_{0}, 2f_{1}f_{2})
2f_{0}f_{1}  2(1 + e_{2})  2^{3}  (f_{1}, 2f_{0}f_{2})
2f_{0}f_{2}  2(1 + e_{1})  2^{3}  (f_{2}, 2f_{0}f_{1})
2f_{1}  2e_{1}  2^{4}  (f_{0}f_{1}, 2f_{2})
2f_{2}  2e_{2}  2^{4}  (f_{0}f_{2}, 2f_{1})
2f_{0}  2e_{1} + 2e_{2}  2^{6}  (f_{1}f_{2}, 2f_{0})
2  2  2^{7}  self-dual
(f_{1}f_{2}, 2f_{0}f_{1})  (3h, 2(1 + e_{2}))  4.2^{3} (f_{0}f_{1}, 2f_{0}f_{2})
(f_{1}f_{2}, 2f_{0}f_{2})  (3h, 2(1 + e_{1}))  4.2^{3} (f_{0}f_{2}, 2f_{0}f_{1})
(f_{0}f_{1}, 2f_{1}f_{2})  (1 + 3e_{2} + 2e_{1}, 2h)  4^{3}.2 self-dual
(f_{0}f_{2}, 2f_{1}f_{2})  (1 + 3e_{1} + 2e_{2}, 2h)  4^{3}.2 self-dual

III Quadratic Residue Codes

Quadratic residue codes are cyclic codes which can be defined in terms of their idempotent generators [8].

Let

e_{1} = ∑_{i∈Q} x_{i}

and

e_{2} = ∑_{i∈N} x_{i},

where Q is the set of quadratic residues and N is the set of non-residues for a prime p ≡ ±1 (mod 8). When p ≡ −1 (mod 8), e_{1} and e_{2} are idempotents of binary [p, p + 1/2] Q.R codes. When p ≡ 1 (mod 8), they are idempotents of binary [p, p − 1/2] Q.R codes.

The following result is proved in [1].

Theorem 8. Let p be a prime ≡ ±1 (mod 8) such that p + 1 (or p − 1) =8r.

If r is odd then e_{i} + 2e_{j} and 1 + 3e_{i} + 2e_{j} are idempotents over Z_{4}, where i, j = 1, 2 and i ≠ j.

If r is even then 3e_{i} and 1 + e_{i} are idempotents over Z_{4}, where i = 1, 2.

Definition. A Z_{4} − cyclic code is a Z_{4}− quadratic residue (Q.R) code if it is generated by one of the idempotents in Theorem 8.

Let the map μ_{a} be defined as follows:

μ_{a} : i → ai (mod p) for any nonzero a ∈ GF (p).

It is not hard to show that μ_{a}(fg) = μ_{a}(f)μ_{x}(g), for f and g polynomials in ℜ_{n}.

We know that in the binary case, the all 1 vector 1 + e_{1} + e_{2}, denoted by h, is an idempotent. In Z_{4},

h^{2} = (1 + e_{1} + e_{2})h
= h + \frac{p − 1}{2}h + \frac{p − 1}{2}h
= h + (p − 1)h = ph.

Therefore, when p ≡ 1 (mod 8), h is an idempotent in Z_{4}; when p ≡ −1 (mod 8), 3h, denoted by h̃, is an idempotent in Z_{4}.

Theorem 9. Let p be a prime with p + 1 = 8r . If r is odd, let

Q_{1} = (e_{1} + 2e_{2}), Q_{2} = (e_{2} + 2e_{1})

and

Q′_{1} = (1 + 3e_{2} + 2e_{1}), Q′_{2} = (1 + 3e_{1} + 2e_{2});

If r is even, let

Q_{1} = (3e_{1}), Q_{2} = (3e_{2})

and

Q′_{1} = (1 + e_{2}), Q′_{2} = (1 + e_{1}).

Then the following holds for Z_{4} − Q.R codes Q_{1}, Q_{2}, Q′_{1} and Q′_{2}:

(a) Q_{1} and Q_{2} are equivalent, Q′_{1} and Q′_{2} are equivalent;

(b) Q_{1} ∩ Q_{2} = (h̃) and Q_{1} + Q_{2} = R_{p} = Z_{4}[x]/(x^{p} − 1); (c) |Q_{1}| = 4^{p+1/2} = |Q_{2}|;

(d) Q_{1} = Q′_{1} + (h̃), Q_{2} = Q′_{2} + (h̃);

(e) |Q′_{1}| = |Q′_{2}| = 4^{p−1/2};

(f) Q′_{1} and Q′_{2} are self-orthogonal and Q_{1}^{⊥} = Q′_{1}, Q_{2}^{⊥} = Q′_{2}.

Proof. We only prove the case when r is odd. When r is even, the proof is similar.

Let s be an element in N, then the map μ_{s} interchanges e_{1} and e_{2}. Hence

μ_{s}(e_{1} + 2e_{2}) = e_{2} + 2e_{1} and μ_{s}(1 + 3e_{2} + 2e_{1}) = 1 + 3e_{1} + 2e_{2}.

This proves (a).

Since

h̃ = 3 + (e_{1} + 2e_{2}) + (e_{2} + 2e_{1}),
(e_{1} + 2e_{2})h̃ = (e_{1} + 2e_{2})(e_{2} + 2e_{1}).

On the other hand,

(e_{1} + 2e_{2})h̃ = e_{1}h̃ + 2e_{2}h̃ = \frac{p − 1}{2}h̃ + (p − 1)h̃ = h̃

because

\frac{p − 1}{2} + (p − 1) = (−1 + 4r) + (−2 + 8r) ≡ 1(mod 8).

Hence

(e_{1} + 2e_{2})(e_{2} + 2e_{1}) = h̃.

By Theorem 7, Q_{1} ∩ Q_{2} has idempotent generator h̃. Therefore

| Q_{1} ∩ Q_{2} |=| (h̃) |= 4.

Also by Theorem 7, Q_{1} + Q_{2} has idempotent generator

(e_{1} + 2e_{2}) + (e_{2} + 2e_{1}) − (e_{1} + 2e_{2})(e_{2} + 2e_{1}) = 1.

Hence

Q_{1} + Q_{2} = ℜ_{p},

and

| Q_{1} + Q_{2} |= 4^{p}.

Now

| Q_{1} |=| Q_{2} |= 4^{p+1/2}

as

| Q_{1} + Q_{2} |= \frac{| Q_{1} || Q_{2} |}{| Q_{1} ∩ Q_{2} |}.

This proves (b) and (c).

By the fact that

(1 + 3e_{2} + 2e_{1})h̃ = 3h + \frac{p − 1}{2}h + (p − 1)h
= 3h + (−1 + 4r)h + (−2 + 8r)h
= 0

Q′_{1} + (h̃) has idempotent generator

1 + 3e_{2} + 2e_{1} + h̃ − (1 + 3e_{2} + 2e_{1})h̃ = e_{1} + 2e_{2}.

Hence

Q′_{1} + (h̃) = (e_{1} + 2e_{2}) = Q_{1}.

Similarly,

Q′_{2} + (h̃) = Q_{2}

and

4^{p+1/2} =| Q_{1} |=| Q′_{1} + (h̃) |=| Q′_{1} || (h̃) |= 4 | Q′_{1} | .

Hence

| Q′_{1} |= 4^{p−1/2}.

This proves (d) and (e).

Finally, by Theorem 6, Q_{1}^{⊥} has idempotent generator

1 − (e_{1}(x^{−1}) + 2e_{2}(x^{−1})) = 1 + 3e_{2} + 2e_{1}.

Hence

Q_{1}^{⊥} = Q′_{1},

and

Q′_{1} ⊆ Q_{1} = Q_{1}^{′^{⊥}},

so that Q′_{1} is self-orthogonal.

Similarly, we can show that Q_{2}^{⊥} = Q′_{2} and Q′_{2} is self-orthogonal.

Theorem 10. Let p be a prime with p − 1 = 8r. If r is odd, let

Q_{1} = (1 + 3e_{1} + 2e_{2}), Q_{2} = (1 + 3e_{2} + 2e_{1})

Q′_{1} = (e_{2} + 2e_{1}), Q′_{2} = (e_{1} + 2e_{2}).

If r is even, let

Q_{1} = (1 + e_{1}), Q_{2} = (1 + e_{2})
Q′_{1} = (3e_{2}), Q′_{2} = (3e_{1}).

Then the following holds for Z_{4} − Q.R codes Q_{1}, Q_{2}, Q′_{1} and Q′_{2}.

(a) Q_{1} and Q_{2} are equivalent, Q′_{1} and Q′_{2} are equivalent;

(b) Q_{1} ∩ Q_{2} = (h) and Q_{1} + Q_{2} = R_{p} = Z_{4}[x]/(x^{p} − 1);

(c) |Q_{1}| = 4^{p+1/2} = |Q_{2}|;

(d) Q_{1} = Q′_{1} + (h), Q_{2} = Q′_{2} + (h);

(e) |Q′_{1}| = |Q′_{2}| = 4^{p−1/2};

(f) Q_{1}^{⊥} = Q′_{2}, Q_{2}^{⊥} = Q′_{1}.

Proof. We only prove (f) for even r. The proofs of (a) - (e) are very similar to the proofs in Theorem 9.

By Theorem 6 and the fact that −1 is a square , Q_{1}^{⊥} has the idempotent generator

1 − (1 + e_{1}(x^{−1})) = 3e_{1},

which is the idempotent generator of Q′_{2}. This proves that

Q_{1}^{⊥} = Q′_{2}.

Similarly, we can show that Q_{2}^{⊥} = Q′_{1}.

Definition. The extended code of a Z_{4} code C denoted by \overline{C} is the code obtained by adding an overall parity check to each codeword of C.

When p = 1 + 8r, we define Q̃_{1} to be the Z_{4} code generated by the following matrix

\begin{aligned}& ∞ 0 1 ⋯ p − 1 \\ ( & \begin{matrix}0 \\ 0 \\ . & G′_{1} \\ . \\ 1 & 1 1 ⋯ 1 \end{matrix} & ) \end{aligned}

where each row of G′_{1} is a cyclic shift of e_{2} + 2e_{1} when r is odd and is a cyclic shift of 3e_{2} when r is even. We define Q̃_{2} similarly. Notice that these are not the extended codes of Q_{1} and Q_{2} because the sum of the components of the all one vector is not 0 (mod 4).

Theorem 11. Let Q_{1}, Q_{2} be the Z_{4} − Q.R codes in Theorems 9 and 10. Let \overline{Q}_{1} and \overline{Q}_{2} denote their extended codes.

When p ≡ −1 (mod 8), \overline{Q}_{1} and \overline{Q}_{2} are self-dual.

When p ≡ 1 (mod 8), the dual of \overline{Q}_{1} is Q̃_{2} and the dual of \overline{Q}_{2} is Q̃_{1}.

Proof. We first prove the case when p + 1 = 8r with r odd. In this case

Q_{1} = Q′_{1} + (h̃) = (e_{1} + 2e_{2})

and \overline{Q}_{1} has the following \frac{p+1}{2} × (p + 1) generator matrix

\begin{aligned}& ∞ 0 1 ⋯ p − 1 \\ ( & \begin{matrix}0 \\ 0 \\ . & G′_{1} \\ . \\ 3 & 3 3 ⋯ 3 \end{matrix} & ) \end{aligned}

where each row of G′_{1} is a cyclic shift of the vector 1+3e_{2}+2e_{1}. We know that G′_{1} generates Q′_{1}. Since Q′_{1} is self-orthogonal, the rows of G′_{1} are orthogonal to each other and clearly also orthogonal to h̃. Because the vector h̃ is orthogonal to itself and

| \overline{Q}_{1} |=| Q_{1} |= 4^{p+1/2},

\overline{Q}_{1} is self-dual. Similarly, \overline{Q}_{2} is self-dual.

Now, we suppose that p − 1 = 8r with r odd. In this case, \overline{Q}_{1} has the following \frac{p+1}{2} × (p + 1) generator matrix

\begin{aligned}& ∞ 0 1 ⋯ p − 1 \\ ( & \begin{matrix}0 \\ 0 \\ . & G′_{1} \\ . \\ 3 & 3 3 ⋯ 3 \end{matrix} & ) \end{aligned}

where each row of G′_{1} is a cyclic shift of the vector e_{2}+2e_{1}. Since G′_{1} generates Q′_{1} and Q_{2}^{⊥} = Q′_{1} by Theorem 10, any row in above matrix is orthogonal to any row in the matrix which defines Q̃_{2}. By comparing the order of the dual of \overline{Q}_{1} with the order of Q̃_{2}, we know that the dual of \overline{Q}_{1} is Q̃_{2}.

Remark. For both p ≡ 1 (mod 8) and p ≡ −1 (mod 8), the extended codes \overline{Q}_{1} and \overline{Q}_{2} are equivalent because Q_{1} and Q_{2} are equivalent. They are also equivalent to \overline{Q}_{1}^{⊥} and \overline{Q}_{2}^{⊥}. Due to this property, the group of the extended code will be the group of either one of the extended codes. This group contains the subgroup G which is isomophic to P SL_{2}(p) when p ≡ 1 (mod 8) and G/±I ≅ P SL_{2}(p) when p ≡ −1 (mod 8). This result has been shown in [1]. There is an alternate proof in [12].

Example: For p=7, 17 and 23, the symmetrized Lee weight enumerator of Z_{4} − Q.R codes are in [1, 3]. Here we discuss the Lee weight distribution of the extended Z_{4} −Q.R codes of length 32 and 48. The results in [4, Theorem 7] and in [1, Theorem 3.2] are used to determine the symmetrized Lee weight enumerator. More than that, we have used the following algorithm to find the whole swe.

Let C be a code over Z_{4}, and C_{2} be the subcode of C consisting of vectors all of whose components are 0 or 2. Let C′ be the image of C under the map μ. Then kerμ = C_{2}. Suppose that C is generated by the vectors r_{1}, r_{2}, ⋯, r_{k}, and μr_{1}, μr_{2}, ⋯, μr_{k} are linearly independent over Z_{2}. Since for any x in C,

x = ∑_{i=1}^{k} a_{i}r_{i} + ∑_{i=1}^{k} b_{i}r_{i},

where the a_{i} are 0 or 1 and the b_{i} are 0 or 2, the set {∑_{i=1}^{k} a_{i}r_{i}, a_{i} 0 or 1} is a set of coset representations of C_{2} in C.

We first compute the set of coset representations. If we want to know a particular coefficient in the symmetrized Lee weight enumerator, say the cofficient of a^{i}b^{j}c^{k} where the powers of a, b and c are the numbers of 0, 1 or 3 and 2 components respectively, we compute the distribution of 2′s in the set of cosets {x + C_{2}, where the weight of μx = j}. Theoretically speaking, this algorithm can determine all coefficients of the symmetrized Lee weight enumerator, but in practice, this was not possible for larger n.

The Euclidean weight defined in [1], counts 1, 3 as 1; 2 as 4 and 0 as 0. The Euclidean weight of a vector is the sum of the Eulidean weights of its components.

Using the techniques mentioned above, we get the following theorem.

Theorem 12. The extended Z_{4} − Q.R code of length 32 has minimum Lee weight 14, minimum Euclidean weight 16 and minimum Hamming weight 8.

The extended Z_{4} − Q.R code of length 48 has minimum Lee weight 18 , minimum Euclidean weight 24 and minimum Hamming weight 12.

Remarks.

(1) The binary images of the length 32 and 48 Q.R codes under the Gray map are non-linear and better than any linear codes by the tables in [2].

(2) The Z_{4} cyclic code K^{−} of length 31 appearing in [6] is a subcode of the length 31 Z_{4} − Q.R code.

Since K^{−} has generator polynomial

g = (1, 1, 1, 2, 0, 1, 2, 2, 0, 1, 0, 3, 0, 3, 1, 3, 3, 0, 1, 3, 2, 1, 2, 2, 1, 3, 0, 0, 0, 0, 0)

and

(3e_{2})g = g.

Therefore the length 32 extended Z_{4} code, the Kerdock code K , is a subcode of the extended Z_{4} − Q.R code.

The symmetrized Lee weight enumerators of lengths 32 and 48 extended Q.R codes are given in the Appendix. We give the weight distribution of the image of the length 32 Z_{4} − Q.R code under the gray map in Table II.

We thank A.R.Calderbank for sending us copies of [1, 3].

Table II: The weight distribution of the Gray image of the length 32 code

\begin{matrix}i & A_{i} \\ 0, 64 & 1 \\ 14, 50 & 39680 \\ 16, 48 & 127596 \\ 18, 46 & 1944320 \\ 20, 44 & 9443840 \\ 22, 42 & 32347136 \\ 24, 40 & 136671808 \\ 26, 38 & 232207360 \\ 28, 36 & 603596288 \\ 30, 34 & 643625472 \\ 32 & 974960294 \end{matrix}

Appendix

In the following formulas, the powers of a, b and c are numbers of 0, 1 or 3 and 2 components respectively.

The following is the symmetrized Lee weight enumerator of the extended Z_{4}− quadratic residue code of length 32.

65536 b^{32} + (8888320 a^{6} c^{2} + 22220800 a^{4} c^{4} + 8888320 a^{2} c^{6} + 317440 c^{8} + 317440 a^{8})b^{24} + (97771520 a^{9} c^{3} + 351977472 a^{7} c^{5} + 5332992 a c^{11} + 5332992 a^{11} c + 97771520 a^{3} c^{9} + 351977472 a^{5} c^{7})b^{20} + (8808960 a^{14} c^{2} + 132769280 a^{12} c^{4} + 939582720 a^{8} c^{8} + 132769280 a^{4} c^{12} + 8808960 a^{2} c^{14} + 67456 a^{16} + 585184768 a^{10} c^{6} + 67456 c^{16} + 585184768 a^{6} c^{10})b^{16} + (27014144 a^{5} c^{15} + 134435840 a^{13} c^{7} + 291648000 a^{9} c^{11} + 1944320 a^{17} c^{3} + 134435840 a^{7} c^{13} + 27014144 a^{15} c^{5} + 39680 a^{19} c + 1944320 a^{3} c^{17} + 39680 a c^{19} + 291648000 a^{11} c^{9})b^{12} + (634880 a^{18} c^{6} + 9523200 a^{14} c^{10} + 13054720 a^{12} c^{12} + 59520 a^{20} c^{4} + 3571200 a^{16} c^{8} + 3571200 a^{8} c^{16} + 59520 a^{4} c^{20} + 634880 a^{6} c^{18} + 9523200 a^{10} c^{14})b^{8} + a^{32} + c^{32} + 620 a^{24} c^{8} + 13888 a^{20} c^{12} + 36518 a^{16} c^{16} + 13888 c^{20} a^{12} + 620 c^{24} a^{8}

The following is the symmetrized Lee weight enumerator of the extended Z_{4}− quadratic residue code of length 48.

535095 a^{32} c^{16} + 3995376 a^{28} c^{20} + a^{48} + 17296 a^{36} c^{12} + c^{48} + 17296 c^{36} a^{12} + 7681680 a^{24} c^{24} + 3995376 c^{28} a^{20} + 535095 c^{32} a^{16} + (5076306816 c^{25} a^{11} + 72615388032 a^{19} c^{17} + 72615388032 a^{17} c^{19} + 73058304 c^{29} a^{7} + 2490624 c^{31} a^{5} + 73058304 a^{29} c^{7} + 47009974528 a^{15} c^{21} + 19521510912 a^{23} c^{13} + 47009974528 a^{21} c^{15} + 790496384 a^{27} c^{9} + 138368 a^{33} c^{3} + 19521510912 c^{23} a^{13} + 2490624 a^{31} c^{5} + 5076306816 a^{25} c^{11} + 138368 c^{33} a^{3} + 790496384 c^{27} a^{9})b^{12} + (44011401600 c^{24} a^{8} + 943888173888 a^{20} c^{12} + 154626240 a^{28} c^{4} + 44011401600 a^{24} c^{8} + 269649067776 a^{22} c^{10} + 3769974528 c^{26} a^{6} + 3769974528 a^{26} c^{6} + 2512593794304 a^{16} c^{16} + 1660416 a^{30} c^{2} + 154626240 c^{28} a^{4} + 943888173888 c^{20} a^{12} + 269649067776 c^{22} a^{10} + 1970930396160 a^{18} c^{14} + 1970930396160 c^{18} a^{14} + 1660416 c^{30} a^{2})b^{16} + (14943744 a^{27} c + 1625547264 c^{25} a^{3} + 18699565142016 a^{13} c^{15} + 14943744 c^{27} a + 591187795968 c^{21} a^{7} + 3449721792000 c^{19} a^{9} + 591187795968 a^{21} c^{7} + 3449721792000 a^{19} c^{9}

+ 1625547264 a^{25} c^{3} + 18699565142016 a^{15} c^{13}

+ 49135030272 c^{23} a^{5} + 49135030272 a^{23} c^{5}

+ 10724392825344 a^{11} c^{17} + 10724392825344 a^{17} c^{11})b^{20} + (

11299014650880 a^{8} c^{16} + 4247344128 a^{2} c^{22}

+ 41544378753024 a^{12} c^{12} + 30131947726848 a^{10} c^{14}

+ 2067976176640 a^{6} c^{18} + 30131947726848 a^{14} c^{10}

+ 14775296 a^{24} + 163212251136 a^{20} c^{4} + 2067976176640 a^{18} c^{6}

+ 11299014650880 a^{16} c^{8} + 4247344128 a^{22} c^{2} + 14775296 c^{24}

+ 163212251136 a^{4} c^{20})b^{24} + (21474027294720 a^{9} c^{11}

+ 2557040640 a^{19} c + 21474027294720 a^{11} c^{9}

+ 145751316480 c^{17} a^{3} + 1982217904128 c^{15} a^{5}

+ 9911089520640 a^{13} c^{7} + 1982217904128 a^{15} c^{5}

+ 2557040640 c^{19} a + 9911089520640 c^{13} a^{7}

+ 145751316480 a^{17} c^{3})b^{28} + (273968640 c^{16} + 273968640 a^{16}

+ 2193940869120 a^{6} c^{10} + 498622924800 a^{4} c^{12}

+ 498622924800 a^{12} c^{4} + 32876236800 a^{2} c^{14}

+ 2193940869120 a^{10} c^{6} + 3525976396800 a^{8} c^{8}

+ 32876236800 a^{14} c^{2})b^{32} + (112217554944 c^{5} a^{7}

+ 1700265984 a^{11} c + 1700265984 c^{11} a + 31171543040 a^{9} c^{3} + 112217554944 c^{7} a^{5} + 31171543040 c^{9} a^{3})b^{36} + 16777216 b^{48}

31

References

[1] A.Bonnecaze, P.Solé, and A.R.Calderbank, Quaternary Quadratic residue Codes and Unimodular Lattices, IEEE Trans. Inform. Theory, vol.41, pp.366-377, March 1995.

[2] A.E.Brouwer and Tom Verhoeff,An Updated Table of Minimum-Distance Bounds for Binary Linear Codes, IEEE Trans. Inform. Theory, vol.39, pp. 662-675, March 1993.

[3] A.R.Calderbank and N.J.A.Sloane, Modular and p-adic Cyclic Codes, Designs,Codes and Cryptography, 6, pp. 21-35, 1995.

[4] J.H.Conway and N.J.A.Sloane, Self-Dual Codes over the Integers Modulo 4, J.Combinatorial Theory (A), vol.62, pp.30-45, January 1993.

[5] L.E.Dickson, Linear Groups, Dover Publications, Inc. NY, 1958.

[6] A.R.Hammons, Jr., P.V.Kumar, A.R.Calderbank, N.J.A.Sloane and P.Solé, The Z_{4}-linearity of kerdock, Preparata, Goethals and Related Codes, IEEE Trans. Inform. Theory, vol.40, pp. 301-319, March 1994.

[7] T.W.Hungerford, Algebra, Springer-Verlag, NY, 1974.

[8] J.S.Leon, J.M.Masley, and V.Pless, Duadic Codes, IEEE Trans.Inform.Theory, vol.30, pp. 709-714, September 1984.

[9] F.J.MacWilliams and N.J.A.Sloane, The Theory of Error-Correcting Codes, North Holland, Amsterdam, 1978.

[10] B.R.McDonald, Finite Rings with Identity, Dekker, NY, 1974.

[11] V. Pless, Introduction to the Theory of Error-Correcting Codes, Wiley-Interscience, 1989.

[12] Z.Qian, Cyclic Codes over Z_{4}, Ph.D dissertation, Uni. of Illinois at Chicago, 1996.