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

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

• 批准号: 0953155
• 负责人: Venkatesan Guruswami
• 金额: $ 31.38万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-06-15 至 2012-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0953155&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的最终纠错半径（通过足够大的字母上的代码）。此外，它可以通过与Reed-Solomon码密切相关的代码，通过多项式时间表解码来实现，这种代码在实践中无处不在。从实际的角度来看，这有望比目前广泛使用的经典纠错算法提高两个因素。虽然这是非常令人鼓舞的，但必须克服许多挑战，才能将最近结果的理论希望付诸实践。该项目由一个多学科团队领导，涉及一系列综合研究活动，旨在实现实现纠错基本限制的长期目标。在理论方面，目标包括在接近1-R的最佳纠错半径时提高解码算法的复杂性，并为代数列表解码的关键步骤设计更快的算法和启发式算法。该项目还研究了将新编码与软判决解码相结合的实际好处的方法，利用解码器通常可用的大量概率符号可靠性估计。此外，该研究为在高速/低功耗VLSI中最终实现此类算法奠定了基础，从而使新代码能够在广泛的通信和存储系统中得到潜在的部署。在教育方面，该项目为研究生提供了一个刺激的研究环境，鼓励跨大学边界的团队合作和跨学科的合作（计算机科学，通信理论和VLSI设计）。