Covering Codes (eBook)

Cover 1
Contents 10
Preface 8
List of Symbols 16
List of Tables 22
Chapter 1. Introduction 24
1.1 Covering problems 25
1.2 Applications 33
Chapter 2. Basic facts 38
2.1 Codes 38
2.2 The MacWilliams identities 47
2.3 Krawtchouk polynomials 50
2.4 Hamming spheres 55
2.5 Finite fields 63
2.6 Families of error-correcting codes 68
2.7 Designs, constant weight codes, graphs 75
2.8 Notes 80
Chapter 3. Constructions 84
3.1 Puncturing and adding a parity check bit 85
3.2 Direct sum 86
3.3 Piecewise constant codes 87
3.4 Variations on the (u, u + v) construction 89
3.5 Matrix construction 93
3.6 Cascading 95
3.7 Optimal short nonbinary codes 96
3.8 Simulated annealing and local search 102
3.9 Notes 103
Chapter 4. Normality 108
4.1 Amalgamated direct sum 108
4.2 Normality of binary linear codes 117
4.3 Abnormal binary nonlinear codes 125
4.4 Normality of binary nonlinear codes 129
4.5 Blockwise direct sum 133
4.6 Notes 137
Chapter 5. Linear constructions 142
5.1 Basic facts about linear covering codes 143
5.2 The case R = 1 examples of small codes
5.3 Saving more than one coordinate 150
5.4 Davydov's basic construction 152
5.5 Notes 166
Chapter 6. Lower bounds 168
6.1 Bounds for the cardinality of the union of K spheres 169
6.2 Balanced codes 172
6.3 Excess bounds for codes with covering radius one 174
6.4 Excess bounds for codes with arbitrary covering radius 179
6.5 The method of linear inequalities 181
6.6 Table on K ( n , R) 188
6.7 Lower bounds for nonbinary codes 193
6.8 Notes 200
Chapter 7. Lower bounds for linear codes 204
7.1 Excess bounds for linear codes 204
7.2 Linear codes with covering radius two and three 207
7.3 Tables for linear codes 214
7.4 Notes 236
Chapter 8. Upper bounds 238
8.1 Codes with given size and distance 239
8.2 Covering radii of subcodes 245
8.3 Covering radius and dual distance 249
8.4 Notes 258
Chapter 9. Reed-Muller codes 260
9.1 Definitions and properties 261
9.2 First order Reed-Muller codes 264
9.3 Reed-Muller codes of order 2 and m – 3 270
9.4 Covering radius of Reed-Muller codes of arbitrary order 274
9.5 Notes 281
Chapter 10. Algebraic codes 284
10.1 BCH codes: definitions and properties 285
10.2 2-and 3-error-correcting BCH codes 289
10.3 Long BCH codes 292
10.4 Normality of BCH codes 300
10.5 Other algebraic codes 302
10.6 Notes 304
Chapter 11. Perfect codes 308
11.1 Perfect linear codes over IFq 309
11.2 A nonexistence result 313
11.3 Enumeration of perfect binary codes 319
11.4 Enumeration of perfect codes over Fq 330
11.5 Mixed codes 333
11.6 Generalizations of perfect codes 335
11.7 Notes 337
Chapter 12. Asymptotic bounds 342
12.1 Covering radius of unrestricted codes 343
12.2 Greedy algorithm and good coverings 345
12.3 Covering radius of hnear codes 347
12.4 Density of coverings 351
12.5 Coverings of small size 355
12.6 Bounds on the minimum distance 361
12.7 Covering radius as a function of dual distance 365
12.8 Packing radius vs covering radius 369
12.9 Notes 374
Chapter 13. Weighted coverings 378
13.1 Basic notions 378
13.2 Lloyd theorem for perfect weighted coverings 380
13.3 Perfect weighted coverings with radius one 384
13.4 Weighted coverings and nonexistence results 388
13.5 Notes 391
Chapter 14. Multiple coverings 394
14.1 Definitions 394
14.2 Perfect multiple coverings 396
14.3 Normality of multiple coverings 401
14.4 Constructions 404
14.5 Tables for multiple coverings 405
14.6 Multiple coverings of deep holes 408
14.7 Notes 412
Chapter 15. Football pools 416
15.1 Constructions for mixed Constructions for mixed binary/ternary codes 417
15.2 Tables for mixed binary/ternary codes 420
15.3 On the early history of the ternary Golay code 424
15.4 Notes 425
Chapter 16. Tilings 426
16.1 Preliminaries 426
16.2 A sufficient condition 428
16.3 Small tiles 429
16.4 Periodicity of tilings 432
16.5 Recursive decomposition of tilings 435
16.6 Tilings and perfect binary codes 438
16.7 Nonexistence results 440
16.8 Notes 443
Chapter 17. Writing on constrained memories 446
17.1 Worst case coverings and WOMs 446
17.2 The error case 451
17.3 A model for correcting single errors 452
17.4 Single-error-correcting WOM-codes 453
17.5 Nonlinear WOM-codes 456
17.6 Notes 459
Chapter 18. Subset sums and constrained memories 462
18.1 Cayley graphs 462
18.2 Subset sums 464
18.3 Maximal sum-free sets 469
18.4 Constrained memories (W*Ms) 471
18.5 Translation-invariant constraints 472
18.6 Domatic number and reluctant memories 475
18.7 Defective memories 478
18.8 The error case 479
18.9 Notes 479
Chapter 19. Heterodox coverings 484
19.1 Perfect coverings by L-spheres 484
19.2 Perfect coverings by spheres of two radii 490
19.3 Coverings by spheres all of different radii 493
19.4 Multicovering radius 495
19.5 Perfect coverings of a sphere and constant weight coverings 496
19.6 Notes 498
Chapter 20. Complexity 502
20.1 Basic facts about the polynomial hierarchy 502
20.2 The complexity of computing the covering radius of a binary code 506
20.3 Derandomization 513
20.4 Notes 516
Bibliography 518
Index 560