Introduction to the Theory of Error-Correcting Codes

Last updated

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]

Contents

Topics

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

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]

Related Research Articles

<span class="mw-page-title-main">Coding theory</span> Study of the properties of codes and their fitness

Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are studied by various scientific disciplines—such as information theory, electrical engineering, mathematics, linguistics, and computer science—for the purpose of designing efficient and reliable data transmission methods. This typically involves the removal of redundancy and the correction or detection of errors in the transmitted data.

<span class="mw-page-title-main">Binary Golay code</span> Type of linear error-correcting code

In mathematics and electronics engineering, a binary Golay code is a type of linear error-correcting code used in digital communications. The binary Golay code, along with the ternary Golay code, has a particularly deep and interesting connection to the theory of finite sporadic groups in mathematics. These codes are named in honor of Marcel J. E. Golay whose 1949 paper introducing them has been called, by E. R. Berlekamp, the "best single published page" in coding theory.

In coding theory, the Singleton bound, named after Richard Collom Singleton, is a relatively crude upper bound on the size of an arbitrary block code with block length , size and minimum distance . It is also known as the Joshibound proved by Joshi (1958) and even earlier by Komamiya (1953).

In mathematics and computer science, in the field of coding theory, the Hamming bound is a limit on the parameters of an arbitrary block code: it is also known as the sphere-packing bound or the volume bound from an interpretation in terms of packing balls in the Hamming metric into the space of all possible words. It gives an important limitation on the efficiency with which any error-correcting code can utilize the space in which its code words are embedded. A code that attains the Hamming bound is said to be a perfect code.

Vladimir Iosifovich Levenshtein was a Russian and Soviet scientist who did research in information theory, error-correcting codes, and combinatorial design. Among other contributions, he is known for the Levenshtein distance and a Levenshtein algorithm, which he developed in 1965.

A timeline of events related to  information theory,  quantum information theory and statistical physics,  data compression,  error correcting codes and related subjects.

In computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels.

<span class="mw-page-title-main">Hamming space</span>

In statistics and coding theory, a Hamming space is usually the set of all binary strings of length N, where different binary strings are considered to be adjacent when they differ only in one position. The total distance between any two binary strings is then the total number of positions at which the corresponding bits are different, called the Hamming distance. Hamming spaces are named after American mathematician Richard Hamming, who introduced the concept in 1950. They are used in the theory of coding signals and transmission.

<span class="mw-page-title-main">Vera Pless</span> American mathematician (1931–2020)

Vera Pless was an American mathematician who specialized in combinatorics and coding theory. She was professor emerita at the University of Illinois at Chicago.

Analytic Combinatorics is a book on the mathematics of combinatorial enumeration, using generating functions and complex analysis to understand the growth rates of the numbers of combinatorial objects. It was written by Philippe Flajolet and Robert Sedgewick, and published by the Cambridge University Press in 2009. It won the Leroy P. Steele Prize in 2019.

Ping Zhang is a mathematician specializing in graph theory. She is a professor of mathematics at Western Michigan University and the author of multiple textbooks on graph theory and mathematical proof.

Combinatorics of Finite Geometries is an undergraduate mathematics textbook on finite geometry by Lynn Batten. It was published by Cambridge University Press in 1986 with a second edition in 1997 (ISBN 0-521-59014-0).

<i>Markov Chains and Mixing Times</i> 2009 non-fiction book discussing mathematics

Markov Chains and Mixing Times is a book on Markov chain mixing times. The second edition was written by David A. Levin, and Yuval Peres. Elizabeth Wilmer was a co-author on the first edition and is credited as a contributor to the second edition. The first edition was published in 2009 by the American Mathematical Society, with an expanded second edition in 2017.

Combinatorics of Experimental Design is a textbook on the design of experiments, a subject that connects applications in statistics to the theory of combinatorial mathematics. It was written by mathematician Anne Penfold Street and her daughter, statistician Deborah Street, and published in 1987 by the Oxford University Press under their Clarendon Press imprint.

<i>Polyominoes: Puzzles, Patterns, Problems, and Packings</i> Book on shapes formed from squares

Polyominoes: Puzzles, Patterns, Problems, and Packings is a mathematics book on polyominoes, the shapes formed by connecting some number of unit squares edge-to-edge. It was written by Solomon Golomb, and is "universally regarded as a classic in recreational mathematics". The Basic Library List Committee of the Mathematical Association of America has strongly recommended its inclusion in undergraduate mathematics libraries.

<i>Graph Theory, 1736–1936</i>

Graph Theory, 1736–1936 is a book in the history of mathematics on graph theory. It focuses on the foundational documents of the field, beginning with the 1736 paper of Leonhard Euler on the Seven Bridges of Königsberg and ending with the first textbook on the subject, published in 1936 by Dénes Kőnig. Graph Theory, 1736–1936 was edited by Norman L. Biggs, E. Keith Lloyd, and Robin J. Wilson, and published in 1976 by the Clarendon Press. The Oxford University Press published a paperback second edition in 1986, with a corrected reprint in 1998.

Lectures in Geometric Combinatorics is a textbook on polyhedral combinatorics. It was written by Rekha R. Thomas, based on a course given by Thomas at the 2004 Park City Mathematics Institute, and published by the American Mathematical Society and Institute for Advanced Study in 2006, as volume 33 of their Student Mathematical Library book series.

Convex Polyhedra is a book on the mathematics of convex polyhedra, written by Soviet mathematician Aleksandr Danilovich Aleksandrov, and originally published in Russian in 1950, under the title Выпуклые многогранники. It was translated into German by Wilhelm Süss as Konvexe Polyeder in 1958. An updated edition, translated into English by Nurlan S. Dairbekov, Semën Samsonovich Kutateladze and Alexei B. Sossinsky, with added material by Victor Zalgaller, L. A. Shor, and Yu. A. Volkov, was published as Convex Polyhedra by Springer-Verlag in 2005.

Convex Polytopes is a graduate-level mathematics textbook about convex polytopes, higher-dimensional generalizations of three-dimensional convex polyhedra. It was written by Branko Grünbaum, with contributions from Victor Klee, Micha Perles, and G. C. Shephard, and published in 1967 by John Wiley & Sons. It went out of print in 1970. A second edition, prepared with the assistance of Volker Kaibel, Victor Klee, and Günter M. Ziegler, was published by Springer-Verlag in 2003, as volume 221 of their book series Graduate Texts in Mathematics.

Introduction to Lattices and Order is a mathematical textbook on order theory by Brian A. Davey and Hilary Priestley. It was published by the Cambridge University Press in their Cambridge Mathematical Textbooks series in 1990, with a second edition in 2002. The second edition is significantly different in its topics and organization, and was revised to incorporate recent developments in the area, especially in its applications to computer science. The Basic Library List Committee of the Mathematical Association of America has suggested its inclusion in undergraduate mathematics libraries.

References

  1. 1 2 3 4 5 6 7 8 9 10 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. 1 2 3 Goel, S. N. (1983), "Review of Introduction to the Theory of Error-Correcting Codes (1st ed.)", Mathematical Reviews , MR   0634378
  3. 1 2 3 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. 1 2 Post, K. A., "Review of Introduction to the Theory of Error-Correcting Codes (1st ed.)", zbMATH , Zbl   0481.94004
  5. 1 2 3 4 5 Barg, Alexander (1990), "Review of Introduction to the Theory of Error-Correcting Codes (2nd ed.)", Mathematical Reviews , MR   1013573
  6. 1 2 3 4 5 6 7 8 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. 1 2 Blake, Ian F., "Review of Introduction to the Theory of Error-Correcting Codes (2nd ed.)", zbMATH , Zbl   0698.94007
  8. 1 2 3 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. 1 2 3 4 5 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. 1 2 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
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.