CONTENTS
Preface = ⅶ
Introduction = 1
Part 1 Information Theory
Chapter 1
Entropy = 11
1.1 Entropy of a Source = 11
The Entropy Function H(P₁,…, Pn ) = 12
The Units of Entropy = 16
The Entropy of a Random Variable : Joint Entropy = 18
1.2 Properties of Entropy = 22
The Range of the Entropy Function = 23
A Grouping Axiom for Entropy = 23
Properties of Joint Entropy = 23
The Convexity of the Entropy Function = 26
Entropy as an Expected Value = 28
1.3 Additional Properties of Entropy = 30
The Entropy of Countably Infinite Distributions = 30
Typical Sequences = 33
Chapter 2
Noiseless Coding = 39
2.1 Variable Length Encoding = 39
Strings and Codes = 39
Average Codeword Length = 40
Fixed and Variable Length Codes = 41
Unique Decipherability = 41
Instantaneous Codes ; The Prefix Property = 43
Kraft's Theorem = 44
McMilan's Theorem = 47
2.2 Huffman Encoding = 52
An Example of Huffman Encoding = 52
Motivation for the General Case = 54
The General Case = 56
Huffman's Algorithm = 59
2.3 The Noiseless Coding Theorem = 62
Extensions of a Source = 64
Chapter 3
Noisy Coding = 69
3.1 The Discrete Memoryless Channel and Conditional Entropy = 69
Discrete Memoryless Channels = 69
Conditional Entropy = 72
Some Special Channels = 76
3.2 Mutual Information and Channel Capacity = 81
Mutual Information = 81
A Summary of Properties = 83
The Capacity of a Channel = 84
3.3 The Noisy Coding Theorem = 89
The Channel = 91
The Decision Scheme = 92
The Probability of a Decision Error = 93
The Rate of a Code = 95
The Noisy Coding Theorem = 96
The Weak Converse of the Noisy Coding Theorem = 98
The strong Converse of the Noisy Coding Theorem = 101
3.4 Proof of the Noisy Coding Theorem and Its Strong Converse = 105
More on the Probability of Error = 106
Proof of the Noisy Coding Theorem = 107
Proof of the Strong Converse = 111
Part 2 Coding Theory
Chapter 4
General Remarks on Codes = 119
4.1 Error Detection and Correction = 119
Block Codes = 119
The Channel = 119
Burst Errors = 122
The Decision Scheme = 122
Probabilities Associated with Error Detection = 123
Probabilities Associated with Error Correction = 123
The Noisy Coding Theorem = 126
4.2 Minimum Distance Decoding = 129
Minimum Distance Decoding = 129
t-Error-Correcting and t-Error-Detecting Codes = 131
Using a Code for Simultaneous Error Correction / Detection = 132
The Relationship Between Minimum Distance and the Probability of Error = 134
The Packing and Covering Radii of a Code = 136
Perfect and Quasi-Perfect Codes = 138
4.3 Families of Codes = 143
Systematic Codes = 143
Finite Fields = 143
Equivalence of Codes = 144
Types of Codes = 145
Linear Codes = 145
Nonlinear Codes = 149
Families of Codes = 150
Repetition Codes = 150
Hamming Codes = 150
Golay Codes = 151
Reed-Muller Codes = 151
BCH Codes and Reed - Solomon Codes = 152
Quadratic Residue Codes = 152
Goppa Codes = 153
Justesen Codes = 154
Perfect Codes = 154
Obtaining New Codes from Old Codes = 154
Extending a Code = 155
Puncturing a Code = 155
Expunging a Code = 156
Augmenting a Code = 156
Shortening a Code = 157
The (u, u+v) - Construction = 158
The Automorphism Group fo a Code = 158
Transitive Permutation Groups = 159
4.4 Codes and Designs = 163
t-Designs = 163
The Intersection Numbers of a t-Design = 165
Designs and Codes = 167
4.5 The Main Coding Theory Problem = 170
Overview = 170
Elementary Results = 170
A Lower Bound on Aq (n, d) = 171
Upper Bound on Aq (n, d) = 171
Elementary Results = 172
Small Values of Aq (n, d) = 173
A Lower Bound on Aq (n, d) = 173
Upper Bounds on Aq (n, d) = 174
The Singleton Bound = 174
The Sphere-Packing Bound = 175
The Numbers A(n, d, w) = 176
The Johnson Bound = 178
The Plotkin Bound = 181
Equality in the Poltkin Bound - Hadamard codes = 183
The Elias Bound = 188
Chapter 5
Linear Codes = 197
5.1 Linear Codes and Their Duals = 197
The Generator Matrix of a Linear Code = 197
The Dual of a Linear Code = 199
Syndrome Decoding = 202
The Probability of Correct Decoding = 205
The Probability of Error Detection = 206
Majority Logic Decoding = 206
Self-Dual Codes = 208
The Number of Binary Self-Dual Codes = 210
Burst Error Detection and Correction = 212
5.2 Weight Distributions = 216
Characters = 216
The Group Algebra = 218
The Transform of an Element of the Group Algebra = 219
Weight Enumerators and Weight Distributions = 220
The Krawtchouk Polynomials = 222
Linear Codes = 223
Moments of the Weight Distribution = 225
Distance Distributions = 226
The Four Fundamental Parameters of a Code = 228
The Linear Programming Bound = 230
5.3 Maximum Distance Separable Codes = 235
The Trivial MDS Codes = 235
Characterizations of MDS Codes = 235
Existence of Nontrivial MDS Codes = 237
The Weight Distribution of an MDS Code = 239
MDS Codes from Vandermonde Matrices = 240
5.4 Invariant Theory and Self-Dual Codes = 245
Introduction = 245
Invariant Theory = 246
The Weight Enumerator of a Self-Dual Code = 250
The Weight Enumerator of an Even Self-Dual Code = 251
Chapter 6
Some Linear Codes = 253
6.1 Hamming and Golay Codes = 253
Hamming Codes = 253
Decoding with a Hamming Code = 254
A Nonlinear Code with the Hamming Parameters = 256
Hamming Codes and Designs = 256
Simplex Codes = 256
Golay Codes = 258
The Binary Golay Code g2 4 = 262
Decoding the Binary Golay Code g2 4 = 260
The Binary Golay Code g2 3 = 262
The Ternary Golay Codes = 262
Perfect Codes = 263
The Nordstrom-Robinson Code = 263
6.2 Reed-Muller Codes = 267
Boolean Functions and Boolean Polynomials = 267
Boolean Functions = 267
Boolean Polynomials = 268
The Vector Spaces Bm and Bm = 269
Reed-Muller Codes = 270
The Reed-Muller Codes as (u, u+v)-Constructions = 272
The Dual of R(r, m) = 274
Euclidean Geometry = 275
A Geometric Look at the Reed-Muller Codes = 276
Decoding the Reed-Muller Codes = 278
Chapter 7
Finite Fields and Cyclic Codes = 285
7.1 Basic Properties of Finite Fields = 285
A Characterization of Finite Fields = 286
The Subfields of a Finite Field = 287
The Multiplicative Structure of a Finite Field = 288
Describing the Elements of a Finite Field = 289
7.2 Irreducible Polynomial over Finite Fields = 296
The Splitting Field of an Irreducible Polynomial = 296
The Nature of the Roots of an Irreducible Polynomial = 297
Computing Minimal Polynomials = 299
The Automorphism Group of Pq n = 300
Normal Bases = 301
Linearized Polynomials = 302
The Number of Irreducible Polynomials = 304
7.3 The Roots of Unity = 308
Roots of Unity = 308
Primitive Field Elements and Primitive Roots of Unity = 309
A Method for Factoring Xⁿ-1 = 310
The Order of and Irreducible Polynomial = 312
Computing the Order of an Irreducible Polynomial = 314
The Cyclotomic Polynomials = 315
7.4 Cyclic Codes = 320
The Generator Polynomial of a Cyclic Code = 321
The Check Polynomial of a Cyclic Code = 325
The Zeros of a Cyclic code = 327
Hamming Codes as Cyclic Codes = 328
The Idempotent Generator of a Cyclic Code = 331
Minimal Cyclic Codes = 333
Finding Generating Idempotents = 335
A Formula for Primitive Idempotents = 336
7.5 More on Cyclic Codes = 342
Mattson-Solomon Polynomials = 342
Encoding with a Cyclic Code = 344
A Nonsystematic Method = 344
A Systematic Method = 344
Decoding with a Cyclic Code = 345
Error Trapping = 347
Burst Error Detection and Correction with Cyclic Codes = 349
Interleaving = 349
Chapter 8
Some Cyclic Codes = 353
8.1 BCH Codes = 353
The BCH Bound = 353
BCH Codes = 354
Binary BCH Codes = 356
The Automorphisms of Binary BCH Codes = 358
The True Minimum Distance of a BCH Code = 360
The Quality of BCH Codes = 362
Double-Error-Correcting BCH Codes = 362
Decoding BCH Codes = 363
No Errors = 363
Exactly One Error = 363
Exactly Two Errors = 363
The General Case = 365
8.2 Reed-Solomon and Justesen Codes = 369
Reed-Solomon Codes = 369
Properties of the Reed-Solomon Codes = 370
The Reed-Solomon Codes are MDS Codes = 370
The Dual of a Reed-Solomon Code = 370
Extending a Reed-Solomon Code = 371
Obtaining a Binary Code form a 2m -ary Code = 372
Burst Error Correction = 374
Idempotents of Reed-Solomon Codes = 375
Encoding Reed-Solomon Codes = 376
Decoding Reed-Solomon Codes = 377
Asymptotically Good Codes = 379
Finding Good Families of Codes = 379
Concatenation of Codes = 380
Justesen Codes = 381
An Asymptotically Good Family of Justesen Codes = 382
8.3 Alternant Codes and Goppa Codes = 386
Alternant Codes = 386
Goppa Codes = 389
The Parameters of Г(G.L) = 390
Binary Goppa Codes = 393
Fast Decoding of Alternant Codes = 395
The Euclidean Algorithm = 396
Decoding of Alternant Codes-The Initial Setup = 398
Decoding of Alternant Codes-The Decoding step = 401
8.4 Quadratic Residue Codes = 407
Quadratic Residue = 407
Quadratic Residue Codes = 409
The Golay Codes as Quadratic Residue Codes = 412
The Square Root Bound = 412
The Idempotents of a Binary Quadratic Residue Codes = 414
Duals of the Quadratic Residue Codes = 417
The Extended Quadratic Residue Codes = 417
Appendix
Preliminaries = 421
A.1 Algebraic Preliminaries = 421
Groups = 421
Euler's Formula = 422
Cyclic Groups = 423
Rings and Fields = 425
Homomorphisms = 425
Ideals = 425
Factor Rings = 426
The Characteristic of a Ring = 427
Extension Fields = 428
The Prime Eield = 429
Simple Extensions = 429
The Roots of Polynomials = 430
Splitting Fields = 430
Polynomials = 430
The Division Algorithm and its Consequences = 430
The Euclidean Algorithm = 431
Irreducible Polynomials = 431
Common Roots = 432
The Minimal Polynomial = 433
Multiple Roots = 433
A.2 M o ·· bius Inversion = 435
Partially Ordered Sets = 435
The Incidence Algebra of a Partially Ordered Set = 436
Classical M o ·· bius Inversion = 440
Multiplicative Version of M o ·· bius Inversion = 441
A.3 Binomial Inequalities = 442
Inequalities Involving a Single Binomial Coefficient = 443
Inequalities Involving Sums of Binomial Coefficient = 445
Bounds on the Volume of a Sphere = 446
A.4 More on Finite Fields = 449
Computing Minimal Polynomials = 449
An Algorithm for Factoring Polynomials = 452
Finding Primitive Polynomials = 456
Tables = 459
Monic Irreducible Polynomials = 459
Primitive Polynomials = 463
Finite Field Tables = 464
Factorization of Xⁿ-1 = 468
Krawtchouk Polynomials = 469
References = 475
Symbol Index = 479
Index = 481
