Table of Contents


E. F. Assmus, Jr and J. D. Key

  1. Introduction

  2. Projective and affine geometries

  3. The Reed-Muller codes

  4. The group-algebra approach

  5. Generalized Reed-Muller codes


The reader familiar with ``Designs and their Codes'' will soon understand the debt this chapter owes to that book --- especially its Chapter 5. We have, however, entirely reworked that material and, more importantly, added a discussion of the group-algebra approach to the Reed-Muller and generalized Reed-Muller codes. This enables us to include a straightforward new proof of Berman's theorem identifying the Reed-Muller codes with the radical powers in the appropriate modular group algebra and to use our treatment of the Mattson-Solomon polynomial to give a proof of the generalization of Berman's theorem to the p-ary case. We have also included Charpin's treatment of the characterization of ``affine-invariant'' extended cyclic codes due to Kasami, Lin and Peterson.

We have relied heavily on Charpin's doctoral thesis for the new material. The older material relies (as did Chapter 5 of our book) on the treatment of the polynomial codes introduced by Kasami, Lin and Peterson given by Delsarte, Goethals and MacWilliams.

Our definition of the generalized Reed-Muller codes is the straightforward generalization of the boolean-function definition of the Reed-Muller codes and, for us, the cyclicity of the punctured variants is simply a consequence of the easily seen fact that their automorphism groups contain the general linear groups.

We are, of course, principally interested in the geometric nature of certain of these codes. Were one interested only in the binary case the development would be very short and our treatment reflects that fact in that we first discuss the Reed-Muller codes giving complete proofs that differ substantially from those given for the general case. In fact, we have here an instance in which the generalization to an arbitrary finite field seems far from trivial, the biggest hurdle being the passage to fields that are not of prime order.

The peculiar nature of the definitions of the geometric codes in the coding-theory literature was due to the interest --- at the time of their introduction --- in majority-logic decoding of these codes; we therefore also give a short discussion of decoding. On the other hand, we give the natural definitions of the geometric codes (as codes generated by the incidence vectors of the geometric objects at hand) and, hence, our definitions are not the ones found in many engineering texts.

We review the necessary geometry briefly before beginning our discussion of the codes; our treatment is undoubtedly too brief to be useful to a reader with no background whatsoever in finite geometry and such a reader may wish to jump directly to Section 3 --- which may even motivate a study of the geometry involved. Much of the material will be understandable even without a firm grip on the geometry and subsequent sections should be of interest to professional coding theorists. We have, at least, tried to make them so.

We assume a knowledge of coding theory and we believe the reader will find in Chapter 1 the coding theory necessary for a study of this chapter.

We have not attempted to discuss open problems or to explore new avenues of research. The reader interested in such matters may wish to consult our book or the articles cited in the bibliography.