|Lecture notes: Polynomial rings and finite fields|
|Lecture notes: Reed-Solomon codes and the Berlekamp-Massey algorithm.|
|Lecture notes: Iterative decoding.|
|Lecture notes: Noisy coding theorem.|
These three families of codes lead to a great variety of interesting mathematics. The construction and algorithms for encoding and decoding Reed-Solomon codes employ the algebraic theory of finite fields and polynomial rings. The code vectors take values in a finite field and an error switches one field element to another. The Berlekamp-Massey algorithm computes a polynomial that identifies where the error occured.
There is also a beautiful algebraic theory for convolutional codes, but in engineering practice the algebraic aspects are minimized. Convolutional codes are usually binary and they are modeled by circuit diagrams. Errors are probabilistic: the decoder receives a probability that a given bit is a 0 or 1. The Viterbi algorithm then attempts to find the most likely codeword given the input probabilities.
Low-density parity check codes are also studied primarily in the binary case. There is a highly efficient decoding algorithm for these codes, based on probabilistic reasoning, that is similar to the Viterbi algorithm and to algorithms used in artificial intelligence. Decoding can be modeled by messages, passed along the edges of a bipartite graph, that represent ``beliefs'' about the binary values of a codeword. Research into LDPC codes is very active and includes analysis of the decoding algorithm, both experimental and theoretical, and construction of good codes using a variety of methods, random, algebraic, geometric, and combinatorial.
There will be several written assignments, computer simulation of algorithms using Maple (some things may be done in Matlab), and a project to be presented to the class and in writing.