CONTENTS
xxii + 542 pages
PREFACE ... p. vii
CONTENTS ... p. ix
LIST OF SYMBOLS ... p. xv
LIST OF TABLES ... p. xxi
1 INTRODUCTION ... p. 1
1. Covering problems ... p. 2
2. Applications ... p. 10
2 BASIC FACTS ... p. 15
1. Codes ... p. 15
2. The MacWilliams identities ... p. 24
3. Krawtchouk polynomials ... p. 27
4. Hamming spheres ... p. 32
5. Finite fields ... p. 40
6. Families of error-correcting codes ... p. 45
7. Designs, constant weight codes, graphs ... p. 52
8. Notes ... p. 57
3 CONSTRUCTIONS ... p. 61
1. Puncturing and adding a parity check bit ... p. 62
2. Direct sum ... p. 63
3. Piecewise constant codes ... p. 64
4. Variations on the (u,u+v) construction ... p. 66
5. Matrix construction ... p. 70
6. Cascading ... p. 72
7. Optimal short nonbinary codes ... p. 73
8. Simulated annealing and local search ... p. 79
9. Notes ... p. 80
4 NORMALITY ... p. 85
1. Amalgamated direct sum ... p. 85
2. Normality of binary linear codes ... p. 94
3. Abnormal binary nonlinear codes ... p. 102
4. Normality of binary nonlinear codes ... p. 106
5. Blockwise direct sum ... p. 110
6. Notes ... p. 114
5 LINEAR CONSTRUCTIONS ... p. 119
1. Basic facts about linear covering codes ... p. 120
2. The case R=1; examples of small codes ... p. 122
3. Saving more than one coordinate ... p. 127
4. Davydov's basic construction ... p. 129
5. Notes ... p. 143
6 LOWER BOUNDS ... p. 145
1. Bounds for the cardinality of the union of K spheres ... p. 146
2. Balanced codes ... p. 149
3. Excess bounds for codes with covering radius one ... p. 151
4. Excess bounds for codes with arbitrary covering radius ... p. 156
5. The method of linear inequalities ... p. 158
6. Table on K(n,R) ... p. 165
7. Lower bounds for nonbinary codes ... p. 170
8. Notes ... p. 177
7 LOWER BOUNDS FOR LINEAR CODES ... p. 181
1. Excess bounds for linear codes ... p. 181
2. Linear codes with covering radius two and three ... p. 184
3. Tables for linear codes ... p. 191
4. Notes ... p. 213
8 UPPER BOUNDS ... p. 215
1. Codes with given size and distance ... p. 216
2. Covering radii of subcodes ... p. 222
3. Covering radius and dual distance ... p. 226
4. Notes ... p. 235
9 REED-MULLER CODES ... p. 237
1. Definitions and properties ... p. 238
2. First order Reed-Muller codes ... p. 241
3. Reed-Muller codes of order 2 and m-3 ... p. 247
4. Covering radius of Reed-Muller codes of arbitrary order ... p. 251
5. Notes ... p. 258
10 ALGEBRAIC CODES ... p. 261
1. BCH codes: definitions and properties ... p. 262
2. 2- and 3-error-correcting BCH codes ... p. 266
3. Long BCH codes ... p. 269
4. Normality of BCH codes ... p. 277
5. Other algebraic codes ... p. 279
6. Notes ... p. 281
11 PERFECT CODES ... p. 285
1. Perfect linear codes over Fq ... p. 286
2. A nonexistence result ... p. 290
3. Enumeration of perfect binary codes ... p. 296
4. Enumeration of perfect codes over Fq ... p. 307
5. Mixed codes ... p. 310
6. Generalizations of perfect codes ... p. 312
7. Notes ... p. 314
12 ASYMPTOTIC BOUNDS ... p. 319
1. Covering radius of unrestricted codes ... p. 320
2. Greedy algorithm and good coverings ... p. 322
3. Covering radius of linear codes ... p. 324
4. Density of coverings ... p. 328
5. Coverings of small size ... p. 332
6. Bounds on the minimum distance ... p. 338
7. Covering radius as a function of dual distance ... p. 342
8. Packing radius vs covering radius ... p. 346
9. Notes ... p. 351
13 WEIGHTED COVERINGS ... p. 355
1. Basic notions ... p. 355
2. Lloyd theorem for perfect weighted coverings ... p. 357
3. Perfect weighted coverings with radius one ... p. 361
4. Weighted coverings and nonexistence results ... p. 365
5. Notes ... p. 368
14 MULTIPLE COVERINGS ... p. 371
1. Definitions ... p. 371
2. Perfect multiple coverings ... p. 373
3. Normality of multiple coverings ... p. 378
4. Constructions ... p. 381
5. Tables for multiple coverings ... p. 382
6. Multiple coverings of deep holes ... p. 385
7. Notes ... p. 389
15 FOOTBALL POOLS ... p. 393
1. Constructions for mixed binary/ternary codes ... p. 394
2. Tables for mixed binary/ternary codes ... p. 397
3. On the early history of the ternary Golay code ... p. 401
4. Notes ... p. 402
16 TILINGS ... p. 403
1. Preliminaries ... p. 403
2. A sufficient condition ... p. 405
3. Small tiles ... p. 406
4. Periodicity of tilings ... p. 409
5. Recursive decomposition of tilings ... p. 412
6. Tilings and perfect binary codes ... p. 415
7. Nonexistence results ... p. 417
8. Notes ... p. 420
17 WRITING ON CONSTRAINED MEMORIES ... p. 423
1. Worst case coverings and WOMs ... p. 423
2. The error case ... p. 428
3. A model for correcting single errors ... p. 429
4. Single-error-correcting WOM-codes ... p. 430
5. Nonlinear WOM-codes ... p. 433
6. Notes ... p. 436
18 SUBSET SUMS AND CONSTRAINED MEMORIES ... p. 439
1. Cayley graphs ... p. 439
2. Subset sums ... p. 441
3. Maximal sum-free sets ... p. 446
4. Constrained memories (W*Ms) ... p. 448
5. Translation-invariant constraints ... p. 449
6. Domatic number and reluctant memories ... p. 452
7. Defective memories ... p. 455
8. The error case ... p. 456
9. Notes ... p. 456
19 HETERODOX COVERINGS ... p. 461
1. Perfect coverings by L-spheres ... p. 461
2. Perfect coverings by spheres of two radii ... p. 467
3. Coverings by spheres all of different radii ... p. 470
4. Multicovering radius ... p. 472
5. Perfect coverings of a sphere and constant weight coverings ... p. 473
6. Notes ... p. 475
20 COMPLEXITY ... p. 479
1. Basic facts about the polynomial hierarchy ... p. 479
2. The complexity of computing the covering radius of a binary code ... p. 483
3. Derandomization ... p. 490
4. Notes ... p. 493
BIBLIOGRAPHY ... p. 495
INDEX ... p. 537
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.
UPDATED BIBLIOGRAPHY / IE TENUE À JOUR
K(n,R): A NEW TABLE
Revenir à la page d'accueil
Revenir en haut de la page