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.

纠错的代数和计算方法Madhu苏丹（麻省理工学院）在存储信息（例如在CD或DVD上）或通信信息（通过蜂窝电话或电缆调制解调器）时，错误是不可避免的。处理错误并设计检测和自动纠正错误的方法是信息论面临的持续挑战之一。 该项目研究了该理论中的一系列基本问题。 这些问题通过其目标和所考虑的方法来统一。中心目标是提高非常通用的错误模型的通信和相关计算任务的效率。要研究的方法包括有限域上的代数技术和计算机科学理论的技术。代数方法长期以来一直为纠错码的基础做出了贡献。主要的例子是里德-所罗门码及其解码算法，它们为数字存储介质的可靠性铺平了道路。所有 CD 和 DVD 均采用 Reed-Solomon 代码进行编码，并且 CD 和 DVD 播放器配备了针对这些代码的纠错算法。最近的研究，包括 PI 之前的一些工作，表明代数方法可以进一步推广以纠正更多错误，并在处理错误通道时处理更多多样性的可靠性信息。然而，一些基本问题仍未得到解答，即使是关于里德-所罗门码的问题也是如此。一个简单的问题是：在 Reed-Solomon 码中可以通过高效算法纠正的随机错误比例是多少？这个项目以及其他有关代数代码的基本问题都在本项目中进行了研究。该项目还研究了理论计算机科学中开发的新技术在编码理论中一些经典挑战的背景下的适用性。