PREFACE
In a basic covering problem, we have a vector space over a finite alphabet which we wish to cover with as few spheres of a given radius as possible. This means that we can approximate any point in the space by one or more of the centres with a given accuracy. The covering problems are mathematically and aesthetically appealing in their own right, and lend themselves to technical applications, e.g., data compression.
This book is intended for people involved in communication, algorithms, computer science, discrete mathematics, geometry, algebra or number theory. We have strived to remain accessible to a wide audience, although a minimal background in coding theory, algebra and discrete mathematics is occasionally required. The chapters are fairly independent, which should allow nonlinear reading.
Roughly speaking, the first half of the book is about the covering radius of codes -- and we shall emphasize binary codes -- whereas the second half deals with generalizations and related problems. We begin with basic definitions and results in the first two chapters. Chapters 3, 4 and 5 are devoted to constructing codes with small covering radius. In Chapter 4 we study normality, the amalgamated direct sum construction and various generalizations. Chapter 5 focuses on linear codes. In Chapters 6 and 7, we present nonexistence results for nonlinear and linear codes, and show 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 we study the covering radius of certain families of codes including the Reed-Muller and BCH codes. In Chapter 11 we give a thorough account of perfect codes. 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. Chapter 15 deals with a more recreational application, namely, how to use covering codes in connection with football pools. Chapter 16 studies partitions of the binary space into tiles, i.e., cosets of a given set. In the next chapter, we study a general model of constrained memories; it turns out to rely on the worst-case behaviour of the covering radius of shortened codes. In Chapter 18 we 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. In Chapter 20 we study various complexity issues related to the field.
POUR ALLER CHEZ ELSEVIER et commander cet ouvrage, CLIQUEZ ICI SVP, OU sur l'un des deux ICONES ci-dessous.
TO GO TO ELSEVIER for ordering details, PLEASE CLICK HERE.