No label defined (Q4242008)

This article of over one hundred and thirty pages, is an extensive review of algebraic and combinatorial coding theory, the first chapter in a recently appeared Handbook of Coding Theory (see Zbl 0907.94001). It is an elegantly written exposition that, with its numerous carefully chosen examples, serves as an excellent introduction/review of the subject. While it does not cover such subjects as codes from algebraic geometries, decoding or nonlinear codes interpreted as linear codes over integer residue rings, it does cover rather comprehensively many topics not covered so well elsewhere, such as duadic codes, weight distributions and others. While it is an eminently readable account of the theory as an introduction, it is at a sufficient depth that it will also be of interest to experienced researchers in the field. In addition to the examples, there are numerous interesting proposals for research problems. The article begins with a satisfying introduction to information theory leading to the notion of channel capacity and computing these capacities for symmetric channels. Linear codes are then introduced using the standard generator and parity check matrix approach, with interpretations of minimum distance of the code. Notions of code equivalence are discussed. The sphere packing bound and covering radius of a code are considered and all the perfect codes noted. The Gilbert and Varshamov bounds are given, as well as the asymptotic Gilbert-Varshamov bound. The Singleton bound is proven and the maximum distance separable (MDS) codes and their properties shown. The Griesmer bound and some generalizations are proven and the notion of generalized Hamming weight of a code defined. Section 4 introduces finite field theory to a depth sufficient to discuss cyclic codes on the next section. The usual characterizations and properties of cyclic codes are established, including the notion of a subfield subcode. The important result of Delsarte relating subfield subcodes duals and trace codes is given. The ring theoretic characterization of codes using idempotents is described. The BCH, Hartmann-Tzeng-Roos and van Lint and Wilson bounds are derived. There follows quite complete sections on Bose-Chaudhuri-Hocquenghem (BCH) and Reed-Solomon (RS) codes. Chapter 9 on duadic codes is a comprehensive introduction to the subject. Similarly, the section on weight distributions has extensive coverage giving, for example, the Prange identities, the Pless power moment identities and the Gleason theorem on characterizations of self dual code weight enumerators. Chapter 11 is on codes and designs culminating in the Assmus-Mattson theorem. Again, it is comprehensive, going into such topics as designs from extremal self-dual codes, projective planes and many others. The final three sections cover quadratic-residue, Golay and Hamming codes (section 12), Reed-Muller codes (section 13) and nonlinear codes (section 14). The latter gives the Johnson bound and a discussion of nearly-perfect codes. The article is a very readable account of the theory of algebraic codes that has not sacrificed depth or coverage in any sense. Most of the important results are proved and the examples and open problems given illustrate and complement the theory and state of the subject in a very appropriate manner. It contains some 123 references. For the entire collection see [Zbl 0907.94001].