This material is presented to ensure timely dissemination of scholarly work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse copyrighted component of this work in other works, must be obtained from the publishers.
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.

  COVERING CODES:

  PREFACE

 

Covering and packing the euclidean space by spheres are old and well-known problems. The discrete counterpart of the packing problem has been extensively studied within the theory of error-correcting codes. Its dual, the covering problem, has received much less attention over the years. The last decade, however, has witnessed the blossoming of active research in the area, now materialized in the publication of over 500 papers. We feel that during these ten years the area of covering codes has come of age and developed into an elegant discipline with its own flavour and techniques. Our purpose is, on the one hand, to give an account on the state of the art in the theory of covering codes and, on the other hand, to show how a number of issues are related to -- or can be viewed as -- covering problems.

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.


  Revenir à la page d'accueil

  Revenir en haut de la page