Site best viewed with IE 6.0, Netscape 6.0, or Mozilla 1.4 or better
University of California, San Diego
Coding theory was born in 1948 with the work of Claude Shannon, who proved that for every information rate R up to channel capacity, there exists a code of rate R that guarantees a vanishing probability of decoding error. Shannon, however, did not tell us how to find such codes nor how to decode them.
It was recognized early on that codes with good Hamming distance can correct many errors, while codes endowed with algebraic structure admit efficient algebraic decoding algorithms. This has led to over 50 years of research in algebraic and combinatorial coding theory. We will survey several key problems and new results in this area. In particular, we'll elaborate upon the recent methods for decoding Reed-Solomon codes using bivariate polynomial interpolation.
About 10 years ago, the field of coding theory was transformed by the discovery of codes defined on certain graphs, with no algebraic structure, that perform extremely close to the Shannon capacity under probabilistic message-passing decoding. We will briefly review this exciting development, and point out the challenges that lie ahead in the area of "probabilistic" coding theory.