Collaborative Research: CDI-Type I: Realizing the Ultimate Potential of List Error-Correction: Theory, Practice, and Applications

合作研究：CDI-I 型：实现列表纠错的终极潜力：理论、实践和应用

• 批准号: 0835843
• 负责人: Alexander Vardy
• 金额: $ 33.25万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-10-01 至 2011-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0835843&HistoricalAwards=false
• 关键词: Collaborative; Research; CDI; Type; Realizing

Error-correcting codes, studied in a branch of science and engineering known as coding theory, safeguard data against the adverse effects of noise and enable reliable storage and communication of information. Such codes pervade our daily lives, with applications ranging from computer hard-disks and UPS bar-codes to cell phones and the Internet to deep space communication. One of the most fundamental questions in coding theory is the following: What is the largest possible fraction of errors that a code of information rate R can correct? Recent theoretical breakthroughs provide a complete answer to this question, namely that the ultimate error-correction radius of 1-R can be reached (by codes over sufficiently large alphabets). Moreover, it can be reached constructively with polynomial-time list decoding, via codes closely related to Reed-Solomon codes, which are ubiquitous in practice.From a practical standpoint, this promises a factor of two improvement over classical error-correction algorithms that are in widespread use today. While this is extremely encouraging, numerous challenges must be overcome in order to bring the theoretical promise of the recent results to practice. This project, led by a multi-disciplinary team, involves an integrated collection of research activities targeted at progress towards the long term goal of attaining the fundamental limit of error-correction. At the theoretical end, the goals include improving the complexity of the decoding algorithms as one approaches the optimal error-correction radius of 1-R, and devising faster algorithms and heuristics for the key steps involved in algebraic list decoding. The project also studies methods to reap the practical benefits of combining the new codes with soft-decision decoding, putting to use the ample amount of probabilistic symbol reliability estimates often available to decoders. Furthermore, the research lays the groundwork for eventual implementation of such algorithms in high-speed/low-power VLSI, thereby enabling the potential deployment of the new codes in a broad range of communication and storage systems. On the education front, the project provides a stimulating research environment for graduate students, encouraging team-work across university boundaries and collaboration across disciplines (computer science, communication theory, and VLSI design).

在科学和工程分支中研究的错误校正代码，称为编码理论，保护数据免受噪声的不利影响，并启用可靠的存储和信息通信。 这些代码遍布我们的日常生活，应用程序从计算机硬盘和UPS钢筋编码到手机以及互联网到深空通信。编码理论中最基本的问题之一是：信息率r可以纠正的信息守则最大的错误部分是什么？最近的理论突破为这个问题提供了一个完整的答案，即可以达到1-R的最终误差校正半径（通过足够大的字母上的代码）。此外，可以通过与芦苇 - 固体代码密切相关的多项式时间列表来建设性地实现它，这些代码在实践中无处不在。从实际的角度来看，这有望在当今广泛使用的经典错误纠正算法上有两个改进的因素。尽管这是极为令人鼓舞的，但必须克服许多挑战，以便将最新结果的理论承诺带入实践。该项目由一个多学科团队领导，涉及针对进步的一系列集成的研究活动，以实现达到错误纠正的基本限制的长期目标。在理论端，目标包括在接近1-R的最佳误差校正半径时提高解码算法的复杂性，并为代数列表解码的关键步骤设计更快的算法和启发式方法。该项目还研究了将新代码与软否决解码相结合的实际好处的方法，从而使用了大量的概率符号可靠性估计，通常可用于解码器。此外，该研究为在高速/低功率VLSI中最终实施此类算法奠定了基础，从而使新代码的潜在部署在广泛的通信和存储系统中。在教育方面，该项目为研究生提供了刺激的研究环境，鼓励整个大学界限的团队合作以及跨学科的合作（计算机科学，通信理论和VLSI设计）。