Algebraic and Computational Methods for Error-Correction

纠错的代数和计算方法

• 批准号: 0514915
• 负责人: Madhu Sudan
• 金额: $ 32.91万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-07-15 至 2008-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0514915&HistoricalAwards=false
• 关键词: Algebraic; Computational; Methods; Error; Correction

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.

当存储信息（例如在CDS或DVD上）或通信信息（通过蜂窝电话或电缆调制解调器）时，错误校正苏丹（MIT）错误的代数和计算方法是不可避免的。应对错误，并设计方法来检测和自动纠正错误，这是信息理论的持续挑战之一。 该项目研究了该理论中的基本问题。 这些问题由他们的目标以及正在考虑的方法统一。中心目标是提高通信效率和相关的计算任务的非常通用的错误模型。要研究的方法包括有限领域的代数技术，以及从计算机科学理论中进行的技术。代数方法长期以来有助于误差校正代码的基础。主要示例是REED - 固体代码及其解码算法，这些算法为数字存储媒体的许多可靠性铺平了道路。所有CD和DVD均用Reed-Solomon代码编码，并且CD-和DVD播放器配备了这些代码的错误校正算法。最近的研究，包括PI的一些先前工作，表明可以将代数方法推进进一步纠正更多错误，并在处理错误的渠道时处理更多的可靠性信息。然而，即使是关于芦苇 - 固体代码，一些基本问题仍然没有得到答复。一个简单的问题是：通过有效算法在Reed-Solomon代码中可以校正的随机误差的比例是多少？该项目研究了这一点以及有关代数法规的其他基本问题。该项目还研究了在编码理论中一些经典挑战的背景下，理论计算机科学中开发的新技术的适用性。