 |
|
| COVERING CODES, 54
| |
| | |
|
|
 To order this title, and for more information, click here
By
G. Cohen, ENST, Dépt. Informatique, Paris, France
I. Honkala, University of Turku, Department of Mathematics, Turku, Finland
S. Litsyn, Tel Aviv University, Department of Electrical Engineering Systems, Ramat Aviv, Israel
A. Lobstein, ENST, Dépt. Informatique, Paris, France
Included in series
North-Holland Mathematical Library, 54
Description
The problems of constructing covering codes and of estimating their parameters are the main concern of this book. It provides a unified
account of the most recent theory of covering codes and shows how a number of mathematical and engineering issues are related to covering
problems.
Scientists involved in discrete mathematics, combinatorics, computer science, information theory, geometry, algebra or number
theory will find the book of particular significance. It is designed both as an introductory textbook for the beginner and as a reference
book for the expert mathematician and engineer.
A number of unsolved problems suitable for research projects are also discussed.
Contents
Introduction.
Covering problems. Applications.
Basic Facts.
Codes. The MacWilliams identities. Krawtchouk polynomials. Hamming
spheres. Finite fields. Families of error-correcting codes. Designs, constant weight codes, graphs.
Constructions.
Puncturing
and adding a parity check bit. Direct sum. Piecewise constant codes. Variations on the (
u
,
u
+
v
) construction.
Matrix construction. Cascading. Optimal short nonbinary codes. Simulated annealing and local search.
Normality.
Amalgamated direct
sum. Normality of binary linear codes. Abnormal binary nonlinear codes. Normality of binary nonlinear codes. Blockwise direct sum.
Linear
Constructions.
Basic facts about linear covering codes. The case R=1; examples of small codes. Saving more than one coordinate.
Davydov's basic construction.
Lower Bounds.
Bounds for the cardinality of the union of K spheres. Balanced codes. Excess
bounds for codes with covering radius one. Excess bounds for codes with arbitrary covering radius. The method of linear inequalities.
Table on K(n,R). Lower bounds for nonbinary codes.
Lower Bounds for Linear Codes.
Excess bounds for linear codes.
Linear codes with covering radius two and three. Tables for linear codes.
Upper Bounds.
Codes with given size and distance. Covering
radii of subcodes. Covering radius and dual distance.
Reed-Muller Codes.
Definitions and properties. First order Reed-Muller codes.
Reed-Muller codes of order 2 and m—3. Covering radius of Reed-Muller codes of arbitrary order.
Algebraic Codes.
BCH codes: definitions and properties. 2- and 3-error-correcting BCH codes. Long BCH codes. Normality of BCH codes. Other algebraic codes.
Perfect Codes.
Perfect linear codes over IFq. A nonexistence result. Enumeration of perfect binary codes. Enumeration
of perfect codes over IFq. Mixed codes. Generalizations of perfect codes.
Asymptotic Bounds.
Covering radius of unrestricted
codes. Greedy algorithm and good coverings. Covering radius of linear codes. Density of coverings. Coverings of small size. Bounds on
the minimum distance. Covering radius as a function of dual distance. Packing radius vs covering radius.
Weighted Coverings.
Basic notions. Lloyd theorem for perfect weighted coverings. Perfect weighted coverings with radius one. Weighted coverings and nonexistence
results.
Multiple Coverings.
Definitions. Perfect multiple coverings. Normality of multiple coverings. Constructions. Tables for
multiple coverings. Multiple coverings of deep holes.
Football Pools.
Constructions for mixed binary/ternary codes. Tables for
mixed binary/ternary codes. On the early history of the ternary Golay code.
Tilings.
Preliminaries. A sufficient condition. Small
tiles. Periodicity of tilings. Recursive decomposition of tilings. Tilings and perfect binary codes. Nonexistence results.
Writing
on Constrained Memories.
Worst case coverings and WOMs. The error case. A model for correcting single errors. Single-error-correcting
WOM-codes. Nonlinear WOM-codes.
Subset Sums and Constrained Memories.
Cayley graphs. Subset sums. Maximal sum-free sets. Constrained
memories (W*Ms). Translation-invariant constraints. Domatic number and reluctant memories. Defective memories. The error case.
Heterodox
Coverings.
Perfect coverings by L-spheres. Perfect coverings by spheres of two radii. Coverings by spheres all of different
radii. Multicovering radius. Perfect coverings of a sphere and constant weight coverings.
Complexity.
Basic facts about the polynomial
hierarchy. The complexity of computing the covering radius of a binary code. Derandomization.
Bibliography. Index.
Bibliographic & ordering Information
Hardbound, publication date: APR-1997
ISBN-13: 978-0-444-82511-7
ISBN-10: 0-444-82511-8
Imprint: NORTH-HOLLAND
Price: Order form
EUR 179
USD 179
GBP 119
Books and book related electronic products are priced in US dollars (USD), euro (EUR), and Great Britain Pounds (GBP). USD prices apply to the Americas and Asia Pacific. EUR prices apply in Europe and the Middle East. GBP prices apply to the UK and all other countries.
See also information about conditions of sale & ordering procedures, and links to our regional sales offices.
050/500
Last update: 29 Aug 2008
|
|
| |
| | |
|
|
| |
