Preface
The purpose of this book is to provide a comprehensive introduction to error correction
coding, including both classical block- and trellis-based codes and the recent developments
in iteratively decoded codes such as turbo codes and low-density parity-check codes. 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, un-
derstand, 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 a rich and interacting variety of mathemat-
ical 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 mod-
ules; practice has moved from polynomial interpolation to rational interpolation; Viterbi
makes way for BCJR. This richness can be bewildering to students, particularly engineering
students who are 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 mo-
tivate polynomial rings. The design of cyclic codes motivates finite fields and as-
sociated 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 initially abstract
and subtle. Software implementations of the algorithms brings 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
