Algebraic Coding Theory

Author: Calderbank, Arthur Robert

Year: 1980

Degree: Dissertation (Ph.D.)

Advisor: Hall, Marshall

Committee Member: Unknown, Unknown

Option: Mathematics

DOI: 10.7907/tydq-8k36

Abstract

The present investigation concerns quadratic residue codes, quasi-cyclic binary codes and symmetry codes. We show how to regard such a code as an ideal in an algebra generated by a group of automorphisms of the code. We then use the algebra to establish a square-root bound on the minimum weight of the code.

We begin by proving that any linear code may be regarded as an ideal in a suitable polynomial ring.

In chapter 2 we present the extended quadratic residue codes of length (q + 1), where q is an odd prime power. We construct these codes in an elementary way from representations of the special linear group, SL2(q).

We then establish a square root bound on the minimum weight in the quasi-cyclic binary codes constructed by V. K. Bhargava, S. E. Tavares, and S.G.S. Shiva. The bound is tight and is achieved only by the [8,4,4] Hamming code. This result answers a question raised by F. J. MacWilliams and N.J.A. Sloane in 'The Theory of Error-Correcting Codes'. The proof rests on viewing these binary codes as ideals in a group algebra over GF(4).

In chapter 4 we extend the construction for symmetry codes given by V. Pless to fields other than GF(3). Given an odd prime power q, and a finite field F of odd characteristic containing √-q, we construct a [2q + 2, q + l] symmetry code over F. We establish a square root bound on the minimum weight in this enlarged family of symmetry codes. When q ≡ -1 (rood 4) this bound is tight and is achieved by an [8,4,4] code over GF(7).

Finally let q ≡ -1 (mod 8) be an odd prime power and let C(q) and C(q)* be the two extended binary quadratic residue codes of length (q + 1). We show how to regard C(q) and C(q)* as one-sided ideals in a binary group algebra and that the appropriate product is a 2-dimensional ideal. This allows us to prove that if d is the minimum weight in C(q) then (d - 1)2 - (d - 1) + 1 - st ≥ q where s, t are non-negative integers with s ≡ 0 (mod 4), and t odd. The integers s and t depend on the way the non-zero entries of a codeword of minimum weight are distributed among the coordinate positions. We prove that (d - 1)2 - (d - 1) + 1 = q only if q = 7 and d = 4. When s = 0 we establish a correspondence between codewords of minimum weight d in C(q) and d x d Hadamard submatrices of the (q + 1) x (q + 1) Paley-Hadamard matrix.

Files