Course number 23586

Spring 2002

Meeting: MW, 3:30-4:45 pm.

Bus. Adm./Math Building #255

San Diego State University

Other times: by appointment or good fortune (I will normally be in my office and available).

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.

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,

O. Pretzel,

J. Walker,

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