Introduction to the Theory of Error-Correcting Codes

This book is mainly centered around algebraic and combinatorial techniques for designing and using error-correcting linear block codes.[1][3][9] It differs from previous works in this area in its reduction of each result to its mathematical foundations, and its clear exposition of the results follow from these foundations.[4]

The first two of its ten chapters present background and introductory material, including Hamming distance, decoding methods including maximum likelihood and syndromes, sphere packing and the Hamming bound, the Singleton bound, and the Gilbert–Varshamov bound, and the Hamming(7,4) code.[1][6][9] They also include brief discussions of additional material not covered in more detail later, including information theory, convolutional codes, and burst error-correcting codes.[6] Chapter 3 presents the BCH code over the field ${\displaystyle GF(2^{4})}$, and Chapter 4 develops the theory of finite fields more generally.[1][6]

Chapter 5 studies cyclic codes and Chapter 6 studies a special case of cyclic codes, the quadratic residue codes. Chapter 7 returns to BCH codes.[1][6] After these discussions of specific codes, the next chapter concerns enumerator polynomials, including the MacWilliams identities, Pless's own power moment identities, and the Gleason polynomials.[1] The final two chapters connect this material to the theory of combinatorial designs and the design of experiments,[1][2] and include material on the Assmus–Mattson theorem, the Witt design, the binary Golay codes, and the ternary Golay codes.[1]

The second edition adds material on BCH codes, Reed–Solomon error correction, Reed–Muller codes, decoding Golay codes,[5][7] and "a new, simple combinatorial proof of the MacWilliams identities".[5] As well as correcting some errors and adding more exercises, the third edition includes new material on connections between greedily constructed lexicographic codes and combinatorial game theory, the Griesmer bound, non-linear codes, and the Gray images of ${\displaystyle \mathbb {Z} ^{4}}$ codes.[9][10]

This book is written as a textbook for advanced undergraduates;[3] reviewer H. N. calls it "a leisurely introduction to the field which is at the same time mathematically rigorous".[8] It includes over 250 problems,[5] and can be read by mathematically-inclined students with only a background in linear algebra[1] (provided in an appendix)[6][8] and with no prior knowledge of coding theory.[2]

Reviewer Ian F. Blake complained that the first edition omitted some topics necessary for engineers, including algebraic decoding, Goppa codes, Reed–Solomon error correction, and performance analysis, making this more appropriate for mathematics courses, but he suggests that it could still be used as the basis of an engineering course by replacing the last two chapters with this material, and overall he calls the book "a delightful little monograph".[1] Reviewer John Baylis adds that "for clearly exhibiting coding theory as a showpiece of applied modern algebra I haven't seen any to beat this one".[6][9]

Other books in this area include The Theory of Error-Correcting Codes (1977) by Jessie MacWilliams and Neil Sloane,[5] and A First Course in Coding Theory (1988) by Raymond Hill.[6]

• Introduction to the Theory of Error-Correcting Codes (2nd ed.) on the Internet Archive