Foundations of coding: theory and applications of error-correcting codes

Contents......Page 5
Preface......Page 4
Introduction......Page 11
Part I Coding and Information Theory......Page 13
1.1 Coding......Page 14
1.2 Unique Decoding......Page 15
1.3 Block Codes and Instantaneous Codes......Page 16
1.4 Some Important Block Codes......Page 18
1.5 Construction of Instantaneous Codes......Page 20
1.6 Kraft's Inequality......Page 21
1.7 McMillan's Theorem......Page 22
Exercises......Page 23
Notes......Page 25
2.2 Huffman Codes......Page 26
2.3 Construction of Binary Huffman Codes......Page 27
2.4 Example......Page 30
2.5 Construction of General Huffman Codes......Page 31
Notes......Page 33
3.1 An Example of Data Compression......Page 34
3.2 The Idea of Entropy......Page 35
3.3 The Definition of Entropy......Page 37
3.4 An Example......Page 38
3.5 Maximum and Minimum Entropy......Page 39
3.6 Extensions of a Source......Page 41
3.7 Entropy and Average Length......Page 42
3.8 Shannon's Noiseless Coding Theorem......Page 43
Exercises......Page 45
Notes......Page 47
4 Reliable Communication Through Unreliable Channels......Page 48
4.1 Binary Symmetric Channels......Page 49
4.2 Information Rate......Page 51
4.3 An Example of Increased Reliability......Page 53
4.4 Hamming Distance......Page 55
4.5 Detection of Errors......Page 57
4.6 Correction of Errors......Page 58
4.7 Channel Capacity......Page 59
4.8 Shannon's Fundamental Theorem......Page 65
Exercises......Page 67
Notes......Page 69
Part II Error-Correcting Codes......Page 70
5.1 Binary Addition and Multiplication......Page 71
5.2 Codes Described by Equations......Page 72
5.3 Binary Linear Codes......Page 73
5.4 Parity Check Matrix......Page 75
5.5 Hamming Codes-Perfect Codes for Single Errors......Page 77
5.6 The Probability of Undetected Errors......Page 83
Exercises......Page 85
Notes......Page 86
6.1 Commutative Groups......Page 87
6.2 Subgroups and Cosets......Page 89
6.3 Decoding by Standard Arrays......Page 92
Exercises......Page 95
Notes......Page 97
7.1 Fields and Rings......Page 98
7.2 The Fields Zp......Page 100
7.3 Linear Spaces......Page 102
7.4 Finite-Dimensional Spaces......Page 105
7.5 Matrices......Page 108
7.6 Operations on Matrices......Page 112
7.7 Orthogonal Complement......Page 115
Exercises......Page 118
Notes......Page 121
8.1 Generator Matrix......Page 122
8.2 Parity Check Matrix......Page 126
8.3 Syndrome......Page 128
8.4 Detection and Correction of Errors......Page 129
8.5 Extended Codes and Other Modifications......Page 132
8.6 Simultaneous Correction and Detection of Errors......Page 135
8-7 MacWilliams Identity......Page 137
Exercises......Page 140
Notes......Page 142
9 Reed-Muller Codes: Weak Codes with Easy Decoding......Page 143
9.1 Boolean Functions......Page 144
9.2 Boolean Polynomials......Page 146
9.3 Reed-Muller Codes......Page 150
9.4 Geometric Interpretation: Three-Dimensional Case......Page 153
9.5 Geometric Interpretation: General Case......Page 157
9.6 Decoding Reed-Muller Codes......Page 160
Exercises......Page 165
Notes......Page 166
10.1 Generator Polynomial......Page 167
10.2 Encoding Cyclic Codes......Page 173
10.3 Parity Check Polynomial......Page 177
10.4 Decoding Cyclic Codes......Page 181
10.5 Error-Trapping Decoding......Page 186
10.6 Golay Code: A Perfect Code for Triple Errors......Page 188
10.7 Burst Errors......Page 191
10.8 Fire Codes: High-Rate Codes for Burst Errors......Page 194
Exercises......Page 198
Notes......Page 200
11.1 Zeros of Polynomials......Page 202
11.2 Algebraic Extensions of a Field......Page 206
11.3 Galois Fields......Page 211
11.4 Primitive Elements......Page 212
11.5 The Characteristic of a Field......Page 216
11.6 Minimal Polynomial......Page 218
11.7 Order......Page 221
11.8 The Structure of Finite Fields......Page 224
11.9 Existence of Galois Fields......Page 226
Exercises......Page 228
Notes......Page 232
12 BCH Codes: Strong Codes Correcting Multiple Errors......Page 233
12.1 Hamming Codes as Cyclic Codes......Page 234
12.2 Double-Error-Correcting BCH Codes......Page 236
12.3 BCH Codes......Page 243
12.4 Reed-Solomon Codes and Derived Burst-Error-Correcting Codes......Page 249
12.5 Generalized Reed-Muller Codes......Page 250
12.6 Goppa Codes: Asymptotically Good Codes......Page 252
Exercises......Page 259
Notes......Page 260
13 Fast Decoding of BCH Codes......Page 261
13.1 Error Location and Error Evaluation......Page 262
13.2 Euclidean Algorithm......Page 264
13.3 The Decoding Algorithm......Page 267
Exercises......Page 270
Notes......Page 271
14.1 Linear Codes and Convolutional Codes......Page 272
14.2 Generator Polynomials and Generator Matrices......Page 277
14.3 Maximum-Likelihood Decoding of Convolutional Codes......Page 282
14.4 The Viterbi Decoding Algorithm......Page 286
Exercises......Page 291
Notes......Page 293
Part III Cryptography......Page 294
15 Cryptography......Page 295
15.1 A Noisy Wiretap......Page 296
15.2 Secret-Key Encryption......Page 298
15.3 Public-Key Encryption......Page 305
15.4 Encryption Based on Large Prime Numbers......Page 307
15.5 Encryption Based on Knapsack Problems......Page 309
15.6 Data Encryption Standard......Page 311
Exercises......Page 318
Notes......Page 319
Appendixes......Page 320
A Galois Fields......Page 321
B BCH Codes and Reed-Muller Codes......Page 325
Bibliography......Page 327
List of Symbols......Page 330
Index......Page 331