Preface

The goals of this second edition are much the same as the first edition: to provide a comprehensive introduction to error correction coding suitable for the engineering practitioner and to provide a solid foundation leading to more advanced treatments or research. Since the first edition, the content has been modernized to include substantially more on LDPC code design and decoder algorithms, as well as substantial coverage of polar codes. The thorough introduction to finite fields and algebraic codes of the first edition has been retained, with some additions in finite geometries used for LDPC code design. As observed in the first edition, the sophistication of the mathematical tools used increases over time. While keeping with the sense that this is the first time most readers will have seen these tools, a somewhat higher degree of sophistication is needed in some places.

The presentation is intended to provide a background useful both to engineers, who need to understand algorithmic aspects for the deployment and implementation of error correction coding, and to researchers, who need sufficient background to prepare them to read, understand, and ultimately contribute to the research literature. The practical algorithmic aspects are built upon a firm foundation of mathematics, which are carefully motivated and developed.

Pedagogical Features

Since its inception, coding theory has drawn from richly interacting variety of mathematical areas, including detection theory, information theory, linear algebra, finite geometries, combinatorics, optimization, system theory, probability, algebraic geometry, graph theory, statistical designs, Boolean functions, number theory, and modern algebra. The level of sophistication has increased over time: algebra has progressed from vector spaces to modules; practice has moved from polynomial interpolation to rational interpolation; Viterbi makes way for SOVA and BCJR. This richness can be bewildering to students, particularly engineering students who may be unaccustomed to posing problems and thinking abstractly. It is important, therefore, to motivate the mathematics carefully.

Some of the major pedagogical features of the book are as follows.

• While most engineering-oriented error-correction-coding textbooks clump the major mathematical concepts into a single chapter, in this book the concepts are developed over several chapters so they can be put to more immediate use. I have attempted to present the mathematics "just in time," when they are needed and well-motivated. Groups and linear algebra suffice to describe linear block codes. Cyclic codes motivate polynomial rings. The design of cyclic codes motivates finite fields and associated number-theoretical tools. By interspersing the mathematical concepts with applications, a deeper and broader understanding is possible.
• For most engineering students, finite fields, the Berlekamp-Massey algorithm, the Viterbi algorithm, BCJR, and other aspects of coding theory are abstract and subtle. Software implementations of the algorithms bring these abstractions closer to a meaningful reality, bringing deeper understanding than is possible by simply working homework problems and taking tests. Even when students grasp the concepts well enough to do homework on paper, these programs provide a further emphasis, as well as tools to help with the homework. The understanding becomes experiential, more than merely conceptual.

  Understanding of any subject typically improves when the student him- or herself has the chance to teach the material to someone (or something) else. A student must develop an especially clear understanding of a concept in order to "teach" it to something as dim-witted and literal-minded as a computer. In this process the computer can provide feedback to the student through debugging and program testing that reinforces understanding.

  In the coding courses I teach, students implement a variety of encoders and decoders, including Reed-Solomon encoders and decoders, convolutional encoders, turbo code decoders, and LDPC decoders. As a result of these programming activities, students move beyond an on-paper understanding, gaining a perspective of what coding theory can do and how to put it to work. A colleague of mine observed that many students emerge from a first course in coding theory more confused than informed. My experience with these programming exercises is that my students are, if anything, overconfident, and feel ready to take on a variety of challenges.

  In this book, programming exercises are presented in a series of 13 Laboratory Exercises. These are supported with code providing most of the software "infrastructure," allowing students to focus on the particular algorithm they are implementing.

  These labs also help with the coverage of the course material. In my course I am able to offload classroom instruction of some topics for students to read, with the assurance that the students will learn it solidly on their own as they implement it. (The Euclidean algorithm is one of these topics in my course.)

  Research in error control coding can benefit from having a flexible library of tools for the computations, particularly since analytical results are frequently not available and simulations are required. The laboratory assignments presented here can form the foundation for a research library, with the added benefit that having written major components, the researcher can easily modify and extend them.

  It is in light of these pedagogic features that this book bears the subtitle Mathematical Methods and Algorithms.

There is sufficient material in this book for a one- or two-semester course based on the book, even for instructors who prefer to focus less on implementational aspects and the laboratories.

Over 200 programs, functions and data files are associated with the text. The programs are written in MATLAB,1 C, or C++. Some of these include complete executables which provide "tables" of primitive polynomials (over any prime field), cyclotomic cosets and minimal polynomials, and BCH codes (not just narrow sense), avoiding the need to tabulate this material. Other functions include those used to make plots and compute results in the book. These provide example of how the theory is put into practice. Other functions include those used for the laboratory exercises. The files are highlighted in the book by the icon

as in the marginal note above. The files are available at https://github.com/tkmoon/eccbook. Other aspects of the book include the following:

• Many recent advances in coding have resulted from returning to the perspective of coding as a detection problem. Accordingly, the book starts off with a digital communication framework with a discussion of detection theory.
• Recent codes such as polar codes or LDPC codes are capable of achieving capacity, or nearly so. It is important, therefore, to understand what capacity is and what it means to transmit at capacity. Chapter 1 also summarizes information theory, to put coding into its historical and modern context. Added in this second edition is an introduction to nonasymptotic information theory, which will be increasingly important in developing communication systems. The information theory informs EXIT chart analysis of turbo and LDPC codes.
• Pedagogically, Hamming codes are used to set the stage for the book by using them to demonstrate block codes, cyclic codes, trellises and Tanner graphs.
• Homework exercises are drawn from a variety of sources and are at a variety of levels. Some are numerical, testing basic understanding of concepts. Others provide the opportunity to prove or extend results from the text. Others extend concepts or provide new results. Because of the programming laboratories, exercises requiring decoding by hand of given bit sequences are few, since I am of the opinion that is better to know how to tell the computer than to do it by hand. I have drawn these exercises from a variety of sources, including problems that I faced as a student and those which I have given to students on homework and exams over the years.
• Number theoretic concepts such as divisibility, congruence, and the Chinese remainder theorem are developed at a point in the development where students can appreciate it.
• Occasionally connections between the coding theoretic concepts and related topics are pointed out, such as public key cryptography and shift register sequences. These add spice and motivate students with the understanding that the tools they are learning have broad applicability.
• There has been considerable recent progress made in decoding Reed-Solomon codes by re-examining their original definition. Accordingly, Reed-Solomon codes are defined both in this primordial way (as the image of a polynomial function) and also using a generator polynomial having roots that are consecutive powers of a primitive element. This sets the stage for several decoding algorithms for Reed-Solomon codes, including frequency-domain algorithms, Welch-Berlekamp algorithm and the soft-input Guruswami-Sudan algorithm.
• Turbo codes, including EXIT chart analysis, are presented, with both BCJR and SOVA decoding algorithms. Both probabilistic and likelihood decoding viewpoints are presented.
• LDPC codes are presented with an emphasis on the decoding algorithm. Density...