Communication of information often takes place over noisy channels. That noise can introduce errors in messages sent over the channel. This is the case for instance in transmission of pictures from deep-space exploration craft like the Voyagers, in the transfer of digital information within computer systems, and in the process of storing information (music, images, etc.) on compact disks, digital audio tape, or other media, and retrieving it for use at a later time. In these situations, for reliability of communication, it is necessary to encode the transmitted information in such a way that errors can be detected and/or corrected when they occur. Designing coding schemes that achieve error control without introducing undue redundancy, and that admit efficient encoding and decoding, is the main goal of coding theory.
The BCH codes (including the Reed-Solomon codes, which are
a special case) are among the most powerful tools
known for the situations described above where errors
tend to occur in ``bursts'' rather than randomly, and
they have been used in engineering practice in those applications.
The construction of BCH codes depends heavily on the
algebra of polynomials with coefficients in a finite field
Fq. For instance, the set of codewords of a Reed-Solomon code
can be identified with the elements of an ideal in the quotient ring
In this course, we will begin with an introduction to binary linear block codes, for which the set of codewords forms a vector subspace of F2n for some n, and we will show how to measure the error-correcting capability of a code using the Hamming distance function. We will study some interesting examples of codes in detail. Then, after developing the basics of the theory of more general finite fields, we will focus on the BCH codes and discuss both their algebraic structure and the best currently known encoding and decoding methods. There is a week-by-week schedule at the end of this syllabus with more information on the topics we will cover.
The text for the course is Coding Theory and Cryptography, The Essentials, 2nd edition, by Hankerson, Hoffman, Leonard, Lindner, Phelps, Rodger, and Wall (Marcel Dekker, 2000). We will study almost all the material in Part I of this book over the course of the semester (in class, and in the final projects). Since the text was designed to minimize the mathematical prerequisites needed to get to the ``meat'' of the subject (the course at Auburn University where this book originated had an audience partially composed of electrical engineering students), you should find the discussions there to be very concrete and accessible. But there are times when using a more sophisticated mathematical idea from the outset can streamline the presentation considerably. So, occasionally, we will develop some ideas in class by different methods than those introduced in the text. (This applies mainly to the material on general finite fields and the algebra of polynomials.)
In order for a student to get as much as possible out of this or any course, regular active participation and engagement with the ideas we discuss are necessary. To get you directly involved in the subject matter of the course, regularly throughout the semester, the class will break down into groups of 3 or 4 students for one or more days, and each group will work on a set of group discussion exercises. I will be responsible for designing and preparing these exercises, and I will be available for questions and other help during these periods. At the conclusion of some discussions, the class as a whole will reconvene to talk about what has been done, to sum up the results, to hear short oral reports from each group, etc. Each group will keep a written record of the group's observations, results, questions, etc. which will be handed in. Some of the meetings of the class will also be structured as lectures when that seems appropriate.
The assignments for the course will consist of:
If you ever have a question about the grading policy, or about your standing in the course, please feel free to consult with me.
The following is an approximate schedule. Some rearrangement, expansion, or contraction of topics may become necessary. I will announce any changes in class, and on the course homepage.
| Week | Dates | Class Topics | Reading (HHLLPRW) |
|---|---|---|---|
| 1 | 1/16,18 | Course Introduction | 1.1 - 1.6 |
| 2 | 1/21,23,25 | Hamming distance, error correction and detection | 1.7 - 1.12 |
| 3 | 1/28,30,2/1 | Binary linear codes | 2.1 - 2.4 |
| 4 | 2/4,6,8 | Generator and parity check matrices | 2.5 - 2.8 |
| 5 | 2/11,13,15 | Syndrome decoding | 2.10 - 2.12 |
| 6 | 2/18,20,22 | Bounds on codes, perfect codes, Hamming codes | 3.1 - 3.4 |
| 7 | 2/25,27,3/1 | Golay and Reed-Muller codes | 3.5 - 3.8 |
| 3/4,6,8 | No class -- Spring Break | ||
| 8 | 3/11,13,15 | Polynomials and cyclic codes | 4.1 - 4.2 |
| 9 | 3/18,20,22 | Polynomials and cyclic codes, continued | 4.3 - 4.4 |
| 10 | 3/25,27 | General finite (Galois) fields | 5.1 |
| 3/29,4/1 | No class -- Easter Break | ||
| 11 | 4/3,5 | Construction of BCH codes | 5.2 - 5.4 |
| 12 | 4/8,10,12 | Reed-Solomon Codes | 6.1 - 6.4 |
| 13 | 4/15,17,19 | The Berlekamp-Massey decoder | 6.5 |
| 14 | 4/22,24,26 | Final project presentations | |
| 15 | 4/29 | Semester wrap-up |