Algebraic and Computational Methods for Error-Correction

纠错的代数和计算方法Madhu Sudan（MIT）在存储信息（如CD或DVD）或交流信息（通过蜂窝电话或电缆调制解调器）时，错误是不可避免的。处理错误，设计方法来检测和自动纠正错误，是信息理论的持续挑战之一。 这个项目研究了这个理论中的一系列基本问题。 这些问题是由它们的目标以及所考虑的方法统一起来的。中心目标是提高通信效率和非常一般的误差模型的相关计算任务。所研究的方法包括有限域上的代数技术和计算机科学理论中的技术。主要的例子是里德-所罗门码及其解码算法，它们为数字存储介质的可靠性铺平了道路。所有的CD和DVD都是用里德-所罗门码编码的，CD和DVD播放机都配备了这些码的纠错算法。最近的研究，包括PI以前的一些工作，已经表明，代数方法可以被进一步推动，以纠正更多的错误，并在处理错误的通道时处理可靠性信息的进一步多样性。然而，一些基本问题仍然没有答案，甚至是关于里德-所罗门码的问题。一个简单的问题是：在里德-所罗门码中，用有效的算法可以纠正的随机错误的比例是多少？这一点，以及其他有关代数码的基本问题，在这个项目中进行了研究。该项目还研究了理论计算机科学中开发的新技术在编码理论中一些经典挑战的背景下的适用性。

Algebraic and computational methods for error-correctionMadhu 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 techniquesfrom 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.