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.