1. Introduction to Coding Theory

1.1 Introduction
1.2 Basic assumptions
1.3 Correcting and detecting error patterns
1.4 Information rate
1.5 The effects of error correction and detection
1.6 Finding the most likely codeword transmitted
1.7 Some basic algebra
1.8 Weight and distance
1.9 Maximum likelihood decoding
1.10 Reliability of MLD
1.11 Error-detecting codes
1.12 Error-correcting codes

2.1 Linear codes
2.2 Two important subspaces
2.3 Independence, basis, dimension
2.4 Matrices
2.5 Bases for C = <S> and C⁺
2.6 Generating matrices and encoding
2.7 Parity-check matrices
2.8 Equivalent codes
2.9 Distance of a linear code
2.10 Cosets
2.11 MLD for linear codes
2.12 Reliability of IMLD for linear codes

3.1 Some bounds for codes
3.2 Perfect codes
3.3 Hamming codes
3.4 Extended codes
3.5 The extended Golay code
3.6 Decoding the extended Golay code
3.7 The Golay code
3.8 Reed-Muller codes
3.9 Fast decoding for RM(1, m)

4.1 Polynomials and words
4.2 Introduction to cyclic codes
4.3 Generating and parity check matrices for cyclic codes
4.4 Finding cyclic codes
4.5 Dual cyclic codes

5.1 Finite fields
5.2 Minimal polynomials
5.3 Cyclic Hamming codes
5.4 BCH codes
5.5 Decoding 2 error-correcting BCH code

6.1 Codes over GF(2^r)
6.2 Reed-Solomon codes
6.3 Decoding Reed-Solomon codes
6.4 Transform approach to Reed-Solomon codes
6.5 Berlekamp-Massey algorithm
6.6 Erasures

7.1 Introduction
7.2 Interleaving
7.3 Application to compact discs

8.1 Shift registers and polynomials
8.2 Encoding convolutional codes
8.3 Decoding convolutional codes
8.4 Truncated Viterbi decoding

9.1 Reed-Muller codes
9.2 Decoding Reed-Muller codes
9.3 Extended Preparata codes
9.4 Encoding extended Preparata codes
9.5 Decoding extended Preparata codes

10 Classical Cryptography

10.1 Encryption schemes
10.2 Symmetric-key encryption
10.3 Feistel ciphers and DES
10.3.1 The New Data Seal
10.3.2 The Data Encryption Standard
10.4 Notes

11.1 Algorithms, complexity, and modular arithmetic
11.2 Quadratic residues
11.3 Primality testing
11.4 Factoring and square roots
11.4.1 Pollard's rho
11.4.2 Random squares
11.4.3 Square roots
11.5 Discrete logarithms
11.5.1 Baby-step giant-step
11.5.2 Index calculus
11.6 Notes

12.1 One-way and hash functions
12.2 RSA
12.3 Provable security
12.4 ElGamal
12.5 Cryptographic protocols
12.5.1 Diffie-Hellman key agreement
12.5.2 Zero-knowledge proofs
12.5.3 Coin-tossing and mental poker
12.6 Notes

Bibliography
Index

The ``just in time'' philosophy consists of introducing the necessary mathematics just in time to be applied; i.e., juxtaposed, with the applications. We don't have 200 pages of mathematics (most of which is irrelevant) followed by 200 pages of coding theory and cryptography. So the format is roughly: mathematics, applications, mathematics, applications, etc. Avoiding unnecessary generalizations means that we don't find it necessary, for example, to describe a cyclic code as a principal ideal. In other words, we have for the most part omitted the mathematical generalizations and terminology that would normally be used in teaching a course to a class consisting entirely of advanced mathematics majors.

Part I (Chapters 1--9) of this text has been used to teach a two-semester sequence in coding theory at Auburn University. The minimal prerequisite for students taking this course is a rather elementary knowledge of linear algebra. However, the more linear algebra, as well as general modern algebra, students bring to the course the better. Students with more mathematical background and maturity will be able to move rather quickly through the early material.

The coding theory portion deals exclusively with binary codes and codes over fields of characteristic 2, stressing the construction, encoding and decoding of several important families of codes. Primarily, we have chosen families of codes that are of interest in engineering and computer science, such as Reed-Solomon codes and convolutional codes, which have been used in deep space communications and consumer electronics (to name but two areas of application). This choice of codes also reflects a broad range of algorithms for encoding and decoding.

Part II (Chapters 10--12) has its origins in an introductory semester-length course on cryptography taught at Auburn University. The course attracts a diverse audience of graduate and undergraduate students from computer science, engineering, education, and mathematics, some of whom will have had only an introductory course in algebra or number theory at the sophomore level. Fortunately, this level of sophistication is sufficient to develop a respectable course in cryptography---indeed, most of the material here requires only a review (included in Chapter 11) of basic results concerning the integers modulo n. The intent has been to write a concise and self-contained introduction to modern cryptography, with an emphasis on public-key methods. In Chapter 12 especially, the main points are covered in relatively short sections, with additional topics outlined (usually in some detail and with references) in the exercises.

In a broad sense, coding theory and cryptography are both concerned with the electronic transfer of information---one with reliability, the other with security. We recognize that not every degree program has the luxury of including courses devoted to each topic, so this text has been written to accommodate several course designs. In a single semester, one could choose to investigate coding theory in depth, covering Chapters 1 to 4 and then either Chapters 5 and 6 or Chapters 7 and 8. One could also delve into cryptography by covering just Chapters 10--12. It is also possible to gain some knowledge in each of the two areas in one semester, in which case we recommend that Chapters 1--3, 10, and 12 be covered, with topics selected from Chapter 11 as needed.

The authors would very much appreciate any comments that users of this text care to pass along. Our email address is rodgec1@auburn.edu.

Acknowledgments

Rosie Torbert did exceptional work in creating the sources for the first edition of this book. Her never failing good cheer in enduring the slings and arrows of constant revisions places her in the saint category. We'd like to thank Heather Conner for doing such a great job in preparing this second edition. We especially appreciate the cover designs of Cindy Otterson and thank her for her work with us on several projects.

D. Hankerson, D.G. Hoffman, D.A. Leonard
C.C. Lindner, K.T. Phelps
C.A. Rodger, J.R. Wall