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.
We will have several written assignments, some Maple programming, a project and presentation of projects during the final exam period.