Algebraic and Computational Methods for Error-Correction

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

Algebraic and computational methods for error-correction Madhu Sudan (MIT) Errors are inescapable when storing information (such as on CDs or DVDs) or communicating information (through cellular phones or cable modems). Coping with errors, and devising methods to detect and automatically correct errors, is one of the persistent challenges to the theory of information. This project investigates a collection of fundamental problems in this theory. The problems are unified by their goals as well as methods under consideration. The central goal is to improve the efficiency of communication and of the associated computational tasks for very general error models. The methods to be investigated include algebraic techniques over finite fields, and techniques from the theory of computer science. Algebraic methods have long contributed to the foundations of error-correcting codes. The principal examples are the Reed-Solomon codes and their decoding algorithms which have paved the way for much of the reliability of digital storage media. All CDs and DVDs are encoded with Reed-Solomon codes, and CD- and DVD-players come equipped with error-correcting algorithms for these codes. Recent research, including some previous work of the PI, has shown that the algebraic methods can be pushed even further to correct more error, and deal with a further diversity of reliability information when dealing with erroneous channels. Yet some fundamental questions remain unanswered, even about Reed-Solomon codes. A simple question is: What is the fraction of random error that can be corrected in Reed-Solomon codes, with efficient algorithms? This, and other such fundamental questions about algebraic codes, are investigated in this project. The project also investigates the applicability of new techniques developed in theoretical computer science in the context of some classical challenges in coding theory.