Coding Theory

Lecture Notes in Mathematics A collection of informal reports and seminars Edited by A. Dold, Heidelberg and B. Eckmann, ZUrich Series: California Institute of Technology, Pasadena Adviser: C. R. DePrima 201 Jacobus H. van Lint California Institute of Technology, Pasadena, CA/USA Cod ing Theory Second Printing Springer-Verlag Berlin · Heidelberg · New York 1973 AMS Subject Classifications (1970): 94A 10 ISBN 3-540-06363-3 Springer-Verlag Berlin - Heidelberg -New York ISBN 0-387-06363-3 Springer-Verlag New York · Heidelberg . Berlin ISBN 3-540-05476-6 1. Auflage Springer-Verlag Berlin· Heidelberg· New York ISBN 0-387-05476-6 1st edition Springer-Verlag New York· Heidelberg· Berlin This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically those of translation, reprinting, re-use of illustrations, broadcasting, reproduction by photocopying machine or similar means, and storage in data banks. Under § 54 of the German Copyright Law where copies are made for other than private use, a fee is payable to the publisher, the amount of the fee to be determined by agreement with the publisher. © by Springer-Verlag Berlin· Heidelberg 1973. Library of Congress Catalog Card Number 73-83239. Printed in Germany. Offsetdruck: Julius Beltz, Hemsbach PREFACE These lecture notes are the contents of a two-term course given by me during the 1970-1971 academic year as Morgan Ward visiting professor at the California Institute of Technology. and graduate students. The students who took the course were mathematics seniors Therefore a thorough knowledge of algebra. (a.o. linear algebra, theory of finite fields, characters of abelian groups) and also probability theory were assumed. After introducing coding theory and linear codes these notes concern topics mostly from algebraic coding theory. subject, e.g. circuitry, is not included. The practical side of the Some topics which one would like to include 1n a course for students of mathematics such as bounds on the information rate of codes and many connections between combinatorial mathematics and coding theory could not be treated due to lack of time. For an extension of the course into a third term these two topics would have been chosen. Although the material for this course came from many sources there are three which contributed heavily and which were used as suggested reading material for the students. These are W. W. Peterson's Error-Correcting Codes «(15]), E. R. Berlekamp's Algebraic Coding Theory «(5]) and several of the AFCRL-reports by E. F. Assmus, H. F. Mattson and R. Turyn ([2], (3), [4] a.o.). For several fruitful discussions I would like to thank R. J. McEliece. The extensive treatment of perfect codes is due to my own interest in this topic and recent developments. The reader who is familiar with coding theory will notice that in several places I have given a new treatment or new proofs of known theorems. Since coding theory is young there remain several parts which need polishing and several problems are still open. I sincerely hope that the course and these notes will contribute to the growing interest of mathematicians in this fascinating subject. For her excellent typing of these lecture notes I thank Mrs. L. Decker. Pasadena, March 1971. J. H. van Lint. CONTENTS CHAPl'ER I: Introduction 1 •1 Channels, noise, redundancy ••.••••••••••••••••••••••••••••••• 1.2 An introductory example •••••••••••••••••••••••••••••••••••••• 4 1.3 Some definitions in information theory ••••••.••••• · . . • • • • • • • •