MSRI-UP 2009: Coding Theory

Prerequisite: A solid course in linear algebra and a course where a student develops skill in reading and constructing proofs. 

Communication of information often takes place over noisy channels that can corrupt the messages sent over them. For reliability of communication, it is often desirable to encode the transmitted information in such a way that errors can be detected and/or corrected when they occur. Finding methods that achieve error control without introducing undue redundancy, and that admit efficient encoding and decoding, is the main goal of coding theory. 

Consider a communications environment in which messages are divided into words or blocks of a fixed length, k, formed using a finite alphabet with q symbols. The simplest case (the one best adapted to electronic hardware) is an alphabet with two symbols, the binary digits 0, 1. Indeed, in the codes used for the transfer of digital information within computer systems, and for storing information on compact disks, or other media and retrieving it for use at a later time, q is either 2 or a power of 2. The alphabet with exactly two symbols can be identified with the finite field, but the theory is substantially the same if the alphabet is any finite field. 

In order to detect and/or correct errors when they occur, some redundancy must be built into the information that is transmitted over the channel. One possible approach is to make the encoded form of a message consist of blocks or n-tuples of length n>k over the same alphabet used for the message itself. Codes obtained in this way are called block codes of length n over the alphabet. 

The summer will start with a quick (two week) short course giving an introduction to the theory of block codes over and other finite fields including: the Hamming distance, the parameters n,k,d of codes and some elementary bounds (Gilbert-Varshamov, Hamming, Singleton, etc.) on the parameters, linear codes, generator and parity check matrices for encoding and syndrome decoding, some important examples such as Hamming and Golay codes, cyclic codes and associated polynomial algebra, general finite fields, Reed-Solomon and BCH codes, algebraic decoding algorithms. The basic decoding method for Reed-Solomon codes (leading up to the Berlekamp-Massey algorithm) is designed to correct up to t=[(d-1)/2]=[(n-k)/2] errors in a received word. By results on the error-correcting capacity of a code in terms of its minimum distance, this restriction on the number of errors is necessary if we ask for a method that returns only one closest codeword for each received word. 

There has been a surge of interest in different algorithms for Reed-Solomon and other codes in recent years. Starting with work of Sudan in the late 1990’s and followed by work of Guruswami & and Sudan and Roth & Ruckstein, a significant amount of work has been devoted to methods that produce a list of all codewords within some specified distance (possibly >t above) of the received word.