zbMATH — the first resource for mathematics

Covering codes. (English) Zbl 0874.94001
North-Holland Mathematical Library. 54. Amsterdam: Elsevier. xxi, 542 p. (1997).
This monograph deals with the covering problem in the Hamming space: how many codewords are there in the smallest code of length \(n\) such that the spheres of radius \(r\) centered at the codewords cover the whole \(n\)-dimensional Hamming space. Such a set is called a covering code. For any code it is possible to determine the smallest integer \(r\) such that the spheres of radius \(r\) centered at the codewords cover the whole space. This integer is called the covering radius of the code.
The authors give an account on the state of the art in the theory of covering codes and show how a number of issues are related to covering problems. In the bibliography 714 different publications are mentioned.
The first half of the book is about the covering radius of codes, the second half deals with generalizations and related problems. The basic definitions and results are in the first two chapters. Chapters 3, 4 and 5 are devoted to constructing codes with small covering radius. In Chapter 4 the authors study normality, the amalgamated direct sum construction and various generalizations. Chapter 5 focuses on linear codes. In Chapters 6 and 7 nonexistence results for nonlinear and linear codes are presented, and it is shown how to improve on the sphere-covering bound. In Chapter 8 bounds are derived on the maximum possible covering radius of a code with a given length, cardinality and minimum or dual distance. In the next two chapters the authors study the covering radius of certain families of codes including the Reed-Muller and BCH codes. In Chapter 11 a thorough account of perfect codes is given. Chapter 12 is devoted to asymptotical covering radius problems. The next two chapters discuss natural generalizations of the covering radius problem, like weighted coverings, multiple coverings and multiple coverings of deep holes. In Chapter 15 it is shown how to use covering codes in connection with football pools. Chapter 16 studies partitions of the binary space into cosets of a given set. In the next chapter a general model of constrained memories is studied; it turns out to rely on the worst-case behaviour of the covering radius of shortened codes. In Chapter 18 the authors explore the connections between graphs, groups and codes and how specific techniques pertaining to these three areas are intertwined. Chapter 19 is devoted to variations on the theme of perfect coverings by spheres, namely coverings by unions of shells, by spheres of two or more radii, or by spheres all of different radii. Chapter 20 discusses various complexity issues related to the field.

94-02 Research exposition (monographs, survey articles) pertaining to information and communication theory
94Bxx Theory of error-correcting codes and error-detecting codes
05B40 Combinatorial aspects of packing and covering
94B75 Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory