Introduction to the Theory of Error-Correcting Codes

Introduction to the Theory of Error-Correcting Codes is a textbook on error-correcting codes, by Vera Pless. It was published in 1982 by John Wiley & Sons,[1][2][3][4] with a second edition in 1989[5][6][7][8] and a third in 1998.[9][10] The Basic Library List Committee of the Mathematical Association of America has rated the book as essential for inclusion in undergraduate mathematics libraries.[11]

Topics

edit

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  , 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   codes.[9][10]

Audience and reception

edit

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]

edit

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]

References

edit
  1. ^ a b c d e f g h i j Blake, Ian F. (July 1983), "Review of Introduction to the Theory of Error-Correcting Codes (1st ed.)", IEEE Transactions on Information Theory, 29 (4): 630, doi:10.1109/tit.1983.1056686; reprinted in Proceedings of the IEEE (1984), doi:10.1109/PROC.1984.12960
  2. ^ a b c Goel, S. N. (1983), "Review of Introduction to the Theory of Error-Correcting Codes (1st ed.)", Mathematical Reviews, MR 0634378
  3. ^ a b c McEliece, Robert J. (May–June 1984), "Review of Introduction to the Theory of Error-Correcting Codes (1st ed.)", American Scientist, 72 (3): 307, JSTOR 27852724
  4. ^ a b Post, K. A., "Review of Introduction to the Theory of Error-Correcting Codes (1st ed.)", zbMATH, Zbl 0481.94004
  5. ^ a b c d e Barg, Alexander (1990), "Review of Introduction to the Theory of Error-Correcting Codes (2nd ed.)", Mathematical Reviews, MR 1013573
  6. ^ a b c d e f g h Baylis, John (June 1991), "Review of Introduction to the Theory of Error-Correcting Codes (2nd ed.)", The Mathematical Gazette, 75 (472): 231–232, doi:10.2307/3620287, JSTOR 3620287
  7. ^ a b Blake, Ian F., "Review of Introduction to the Theory of Error-Correcting Codes (2nd ed.)", zbMATH, Zbl 0698.94007
  8. ^ a b c N., H. (January 1991), "Review of Introduction to the Theory of Error-Correcting Codes (2nd ed.)", Mathematics of Computation, 56 (193): 399–400, doi:10.2307/2008564, JSTOR 2008564
  9. ^ a b c d e Abbott, Steve (July 1999), "Review of Introduction to the Theory of Error-Correcting Codes (3rd ed.)", The Mathematical Gazette, 83 (497): 351–352, doi:10.2307/3619098, JSTOR 3619098
  10. ^ a b Helleseth, T., "Review of Introduction to the Theory of Error-Correcting Codes (3rd ed.)", zbMATH, Zbl 0928.94008
  11. ^ Introduction to the Theory of Error-Correcting Codes, Mathematical Association of America, retrieved 2020-03-14
edit