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
STARRED SECTIONS MAY BE SKIPPED ON FIRST READING.
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 Reordering the Columns of the Parity-Check
Matrix of Hamming Codes ............................... 119
5.2 Reordering 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 Equivalence 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 ƒ(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 ................. 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
Problem .................................................... 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  (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 ........................ 388
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 В .................................................... 442
References .................................................... 443
References to the Second Edition .............................. 453
Index ......................................................... 461
| 
