Coding Theory

Math 696: Special Topics
Course number 23586
Spring 2002
Meeting: MW, 3:30-4:45 pm.
Bus. Adm./Math Building #255
San Diego State University

Professor: Mike O'Sullivan
Office: Bus. Adm./Math Building #217, ext. 594-6697
Office Hours: MWF 10:00-10:30, 12:00- 14:00.
                             Other times: by appointment or good fortune (I will normally be in my office and available).

Course Description

This course will cover two topics in coding theory that have generated great excitement in the last two decades. The first is the use of algebraic geometry in coding theory, and the second is the use of efficient belief-propagation algorithms to decode low-density parity check codes.

Reed-Solomon codes are ubiquitous in modern communication devices. Their construction and algorithms for encoding and decoding make use of the theory of finite fields. In the early 1980's Goppa discovered that methods from algebraic geometry could be used to construct a vast family of codes similar to RS codes, but with better parameters. During the 1990's methods for encoding and decoding of RS codes were generalized to algebraic geometry codes, so that now AG codes are ready for implementation in communication systems. We will spend a few weeks on finite fields and Reed-Solomon codes. After that, we will study some fundamental results from algebraic geometry and extend what we know about RS codes to Hermitian codes, which are the most promising AG codes for application.

The other widely used approach to error-correction employs convolutional codes. This area has a very different flavor from Reed-Solomon coding, employing probabilistic techniques and little algebra. I hope to spend a few days on these codes, but I want to focus on a coding technique that was resurrected in the mid-90's that uses probabilistic techniques in a somewhat different way. A low-density parity check code is the nullspace of a matrix whose entries are almost all 0. There is a highly efficient decoding algorithm for these codes based on probabilistic reasoning that is similar to algorithms used in artificial intelligence. There is tremendous interest in these codes because LDPC codes have been discovered whose performance is quite close to the limit imposed by Shannon's theorem. The theory explaining the excellent performance of these codes is quite undeveloped, and there are no clear techniques for constructing provably good codes. The codes that perform so well are constructed "randomly." We will look at some systematic methods, using algebra and geometry, that have been proposed for constructing good LDPC codes.

Course Materials

No textbooks cover exactly what I want, so the course will be based on my lectures. I'm writing some notes for the course and I may copy some articles.
Here is the first installment of the notes (finite fields) (pdf file)
Here is the second installment of the notes (more on finite fields) (pdf file)
Here is the third installment of the notes (Reed-Solomon codes) (pdf file)
Here is the fourth installment of the notes (the generalised distributive law and LDPC codes). (pdf file)
Here is the fifth installment of the notes (the iterative decoding of LDPC codes). (pdf file)

I will add to the following list of references as the course progresses.
Recommended Texts:
R. Blahut, Theory and Practice of Error Control Codes, Addison-Wesley, 1983. Unfortunately out of print and not in our library. I have a copy.
O. Pretzel, Codes and Algebraic Curves, Oxford Lecture Series in Mathematics and Its Applications, 1998. QA268 .P7 1998
J. Walker, Codes and Curves, American Mathematical Society, Student Mathematical Library, Vol. 7, 2000.

Schedule, Assignments, Maple information


We will have several written assignments, some Maple programming, a project and presentation of projects during the final exam period.