The theory of information and coding

Cover......Page 1
ENCYCLOPEDIA OF MATHEMATICS AND ITS APPLICATIONS 86......Page 2
The Theory of Information and Coding - Second Edition......Page 4
Copyright - ISBN: 0521000955......Page 5
Contents......Page 6
Editor\'s statement......Page 9
Foreword......Page 10
Preface to the first edition......Page 11
Preface to the second edition......Page 13
Introduction......Page 14
Problems......Page 25
Notes......Page 26
Part one - Information theory......Page 28
1.1 Discrete random variables......Page 30
1.2 Discrete random vectors......Page 46
1.3 Nondiscrete random variables and vectors......Page 50
Problems......Page 57
Notes......Page 62
2.1 The capacity-cost function......Page 63
2.2 The channel coding theorem......Page 71
Problems......Page 81
Notes......Page 86
3.1 The rate-distortion function......Page 88
3.2 The source coding theorem......Page 97
Problems......Page 104
Notes......Page 106
4.1 The Gaussian channel......Page 108
4.2 The Gaussian source......Page 112
Problems......Page 118
Notes......Page 123
5. The source-channel coding theorem......Page 125
Problems......Page 133
Notes......Page 135
6.2 The channel coding theorem......Page 136
6.3 The source coding theorem......Page 144
Part two - Coding theory......Page 150
7.1 Introduction: The generator and parity-check matrices......Page 152
7.2 Syndrome decoding on q-ary symmetric channels......Page 156
7.3 Hamming geometry and code performance......Page 159
7.4 Hamming codes......Page 161
7.5 Syndrome decoding on general q-ary channels......Page 162
7.6 Weight enumerators and the MacWilliams identities......Page 166
Problems......Page 171
Notes......Page 178
8.1 Introduction......Page 180
8.2 Shift-register encoders for cyclic codes......Page 194
8.3 Cyclic Hamming codes......Page 207
8.4 Burst-error correction......Page 211
8.5 Decoding burst-error-correcting cyclic codes......Page 227
Problems......Page 232
Notes......Page 240
9.1 Introduction......Page 242
9.2 BCH codes as cyclic codes......Page 246
9.3 Decoding BCH codes, Part one: the key equation......Page 248
9.4 Euclid\'s algorithm for polynomials......Page 256
9.5 Decoding BCH codes, Part two: the algorithms......Page 261
9.6 Reed-Solomon codes......Page 265
9.7 Decoding when erasures are present......Page 278
9.8 The (23, 12) Golay code......Page 289
Problems......Page 294
Notes......Page 304
10.1 Introduction......Page 305
10.2 State diagrams, trellises, and Viterbi decoding......Page 312
10.3 Path enumerators and error bounds......Page 319
10.4 Sequential decoding......Page 325
Problems......Page 334
Notes......Page 341
11.1 Introduction......Page 342
11.2 Uniquely decodable variable-length codes......Page 343
11.3 Matching codes to sources......Page 346
11.4 The construction of optimal UD codes (Huffman\'s algorithm)......Page 349
Problems......Page 354
Notes......Page 357
12.2 Block codes......Page 359
12.3 Convolutional codes......Page 369
12.4 A comparison of block and convolutional codes......Page 371
12.5 Source codes......Page 375
Appendix A - Probability theory......Page 378
Appendix B - Convex functions and Jensen\'s inequality......Page 382
C.1 Construction......Page 387
C.3 Conjugation and minimal polynomials......Page 388
C.4 Factorization of x^n - 1 over F_q......Page 390
Appendix D - Path enumeration in directed graphs......Page 392
2. An annotated bibliography of the theory of information and coding......Page 396
3. Original papers cited in the text......Page 398
Index of theorems......Page 400
Index......Page 402