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

纠错码是在被称为编码理论的科学和工程分支中研究的，它保护数据不受噪声的不利影响，并使信息的可靠存储和通信成为可能。这种代码渗透到我们的日常生活中，应用范围从计算机硬盘和UPS条形码到手机和互联网，再到深空通信。编码理论中最基本的问题之一是：信息率R的代码可以纠正的错误的最大可能比例是多少？最近的理论突破为这个问题提供了一个完整的答案，即可以(通过足够大的字母表上的代码)达到1-R的最终纠错半径。此外，它可以通过与里德-所罗门码密切相关的码，通过多项式时间列表译码来建设性地实现，从实用的角度来看，这是目前广泛使用的经典纠错算法的两倍改进。虽然这是非常令人鼓舞的，但必须克服许多挑战，才能将最近结果的理论承诺付诸实践。该项目由一个多学科小组领导，涉及一系列综合研究活动，旨在朝着达到纠错的基本限度这一长期目标取得进展。在理论上，目标包括在接近1-R的最佳纠错半径时提高译码算法的复杂度，以及为代数表译码所涉及的关键步骤设计更快的算法和启发式算法。该项目还研究了将新码与软判决译码相结合的实际好处的方法，利用译码人员通常可以获得的大量概率符号可靠性估计。此外，该研究为最终在高速/低功耗VLSI中实现这种算法奠定了基础，从而使新代码能够在广泛的通信和存储系统中潜在地部署。在教育方面，该项目为研究生提供了一个鼓舞人心的研究环境，鼓励跨大学边界的团队合作和跨学科(计算机科学、通信理论和超大规模集成电路设计)的合作。

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).