Algebraic Coding Theory and Applications

The last twenty-fit,e years have witnessed thr: growth of one of the most elegant and esoteric branches of applied mathematics: Algebraic Coding Theory. Areas of mathematics which were previously considered to be of the utmost purity have been applied to the problem of constructing error-correcting codes and their decoding algorithms. In spite of the impressive theoretical accomplishments of these twenty-five years, however, only recently has algebraic coding been put into practice.
To present some of the latest results on the theory and applications of algebraic coding, a number of scholars who have been active in the various areas of coding research were invited to lecture at the summer school on "Algebraic Coding: Theory and Applications", organized by Giuseppe Longo at the Centre International des Sciences Mecaniques (ClSM) in Udine, a picturesque city in northern Italy, for a period of two weeks ill July, 1978.
The first contribution, "A Survey of Error-Control Codes", by P.G. Farrell (the University of Kent, Great Britain) is an excellent compilati01l and condef'sation of numerous results on error-correcting codes. This contribution consists of four main sections. The first introduces the reader to the basic facts about error-correcting codes, the second .describes various decoding methods, the third lists some classes of error-control codes which hat'e foulld practical application, and the last is devoted to the performance of such codes.
The second contributioll, "The Bounds of Delsarte and LovGsz, and Their Applications to Coding Theory", is by R.J. McEliece (University of Illinois, U.S.A.). In 1972, P. Delsarte developed a new powerful technique for obtaining upper bounds on the largest possible number of codewords in a code of fixed length and minimum Hamming distance. This technique is nowadays usually called the linear programming approach. In 1977, L. Lovasz produced all astonishingly simp! ' 50114 ti01l to a long-standing problem in information theory which was posed by C. ShamlO1I ill 1956, namely the problem of computing the zero-error capacity of a certaill discrete memoryless channel having five inputs and outputs. Lovasz's technique call be applied to any graph (or discrete memoryless channel), although in general it gilles only all upper bound for the "Shallnon capacity", rather than the true value. In his paper, McElicce offers a unified treatment of these two techniques using standard methods of linear a l ~ e b r a . The result is an extremely powerful and general technique for studying combinatorial packing problems. This technique is used to obtain, as special cases, the McEliece-Rodemich-Rumsey-Welch bound for binary codes and Lovasz's bound on the "Shannon capacity" of many graphs.