Table of Contents
Preface to the Revised Edition vii
Preface to the Second Edition xiii
Preface xv
Acknowledgments xix
1 Basic Binary Codes 1
1.1 Repetition Codes and Single-Parity-Check Codes 1
1.2 Linear Codes 4
1.3 Hamming Codes 8
1.4 Manipulative Introduction to Double-Error-Correcting BCH Codes 12
Problems 20
2 Arithmetic Operations Modulo an Irreducible Binary Polynomial 21
2.1 A Closer Look at Euclid's Algorithm 21
*2.2 Logical Circuitry 30
*2.3 Multiplicative Inversion 36
*2.4 Multiplication 44
*2.5 The Solution of Simultaneous Linear Equations 51
*2.6 Special Methods for Solving Simultaneous Linear Equations When the Coefficient Matrix is Mostly Zeros 63
Problems 69
3 The Number of Irreducible q-ary Polynomials of Given Degree 70
3.1 A Brute-Force Attack 70
3.2 Generating Functions 73
3.3 The Number of Irreducible Monic q-ary Polynomials of Given Degree?A Refined Approach 76
3.4 The Moebius Inversion Formulas 81
Problems 85
4 The Structure of Finite Fields 87
4.1 Definitions 87
4.2 Multiplicative Structure of Finite Fields 88
4.3 Cyclotomic Polynomials 90
4.4 Algebraic Structure of Finite Fields 96
4.5 Examples 105
*4.6 Algebraic Closure 111
*4.7 Determining Minimal Polynomials 112
Problems 117
5 Cyclic Binary Codes 119
5.1 Recording the Columns of the Parity-Check Matrix of Hamming Codes 119
5.2 Recording the Columns of the Parity-Check Matrix of Double-Error-Correcting Binary BCH Codes 125
5.3 General Properties of Cyclic Codes 129
5.4 The Chien Search 132
5.5 Outline of General Decoder for Any Cyclic Binary Code 136
5.6 Example 138
5.7 Example 139
5.8 Equlvalence of Cyclic Codes Defined in Terms of Different Primitive nth Roots of Unity 141
Problems 144
6 The Factorization of Polynomials Over Finite Fields 146
6.1 A General Algorithm 146
*6.2 Determining the Period of a Polynomial 150
*6.3 Trinomials Over GF(2) 153
*6.4 Factoring xn ? 1 Explicitly 154
*6.5 Determining the Degrees of the Irreducible Factors of the Cyclotomic Polynomials 156
*6.6 Is the Number of Irreducible Factors of f (x) Over GF (q) Odd or Even? 159
6.7 Quadratic Reciprocity 171
Problems 173
7 Binary BCH Codes for Correcting Multiple Errors 176
7.1 Examples 176
7.2 The Key Equation for Decoding Binary BCH Codes 178
7.3 Heuristic Solution of the Key Equation 180
7.4 An Algorithm for Solving the Key Equation Over Any Field 184
*7.5 Relation to Matrix Decoding Methods 188
*7.6 Simplifications in Algorithm 7.4 for Binary BCH Codes 192
7.7 Implementation of Binary BCH Decoders Problems 195
Problems 199
8 Nonbinary Coding 200
8.1 Modulation Schemes 200
8.2 Weight Functions 204
Problem 206
9 Negacyclic Codes for the Lee Metric 207
9.1 Error Locations and the Error-Locator Polynomial 207
9.2 Double-Error-Correcting Codes 209
9.3 Negacyclic Codes 211
Problems 217
10 Gorenstein-Zierler Generalized Nonbinary BCH Codes for the Hamming Metric 218
10.1 The Generalized BCH Codes and An Algorithm to Decode Them 218
10.2 Examples 221
*10.3 Alternate BCH Codes and Extended BCH Codes 223
10.4 Decoding Erasures as Well as Errors 229
10.5 Decoding More Than t Errors 231
10.6 Examples 237
Problems 240
11 Linearized Polynomials and Affine Polynomials 241
11.1 How to Find Their Roots 241
11.2 The Least Affine Multiple 245
*11.3 Abstract Properties of Linearized and Affine Polynomials 247
*11.4 Transformations of f (z) 255
*11.5 Root Counting 257
*11.6 Low-Weight Codewords in Certain Codes 262
Problems 271
12 The Enumeration of Information Symbols in BCH Codes 273
12.1 Converting the Problem to an Enumeration of Certain Integers mod n 273
*12.2 Converting the Problem for Primitive BCH Codes to an Enumeration of Certain q-ary Sequences 275
*12.3 Sequence Enumeration Theorems 278
*12.4 Examples 284
*12.5 The Enumeration of Information Symbols in Nonprimitive BCH Codes 287
12.6 Asymptotic Results 290
*12.7 Actual Distance 294
Problems 296
13 The Information Rate of the Optimum Codes 298
13.1 The Hamming-Rao High-Rate Volume Bound 298
*13.2 Perfect Codes 302
*13.3 The Bound D ≤ n + 1 - k 309
13.4 Plotkin's Low-Rate Average Distance Bound 311
*13.5 Equidistant Codes 315
13.6 The Elias Bound 318
13.7 The Gilbert Bound 321
13.8 Asymptotic Error Bounds and Finite Special Cases 324
14 Codes Derived by Modifying or Combining Other Codes 331
14.1 Extending a Code by Annexing More Check Digits 333
14.2 Puncturing a Code by Deleting Check Digits 334
14.3 Augmenting Additional Codewords to the Code 335
14.4 Expurgating Codewords from the Code 335
14.5 Lengthening the Code by Annexing More Message Digits 336
14.6 Shortening the Code by Omitting Message Digits 336
14.7 Subfield Subcodes 336
14.8 Direct-Product Codes and Their Relatives 338
14.9 Concatenated Codes 347
15 Other Important Coding and Decoding Methods 350
15.1 Srivastava Codes?Noncyclic Codes with an Algebraic Decoding Algorithm 350
15.2 Residue Codes?Good Codes Which are Hard to Decode 352
15.3 Reed-Muller Codes?Weak Codes Which are Easy to Decode 361
15.4 Threshold Decoding?The Best Known Algorithm for Decoding Certain Codes 367
15.5 Orthogonalizable Codes Based on Finite Geometries 375
15.6 Convolutional Codes?A Survey 394
Problems 394
16 Weight Enumerators 397
16.1 The Relationship between Weight Enumerators and the Probability of Decoding Failure 397
16.2 The MacWilliams-Pless Equations for the Weight Enumerators of Dual Codes 400
*16.3 Weight Restrictions 407
*16.4 Kasami's Weight Enumerators for Certain Subcodes of the Second-Order RM Code 417
*16.5 The Weight Enumerator for the Reed-Solomon Codes 429
Appendix A 441
Appendix B 442
References 443
References to the Second Edition 453
Index 461
