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

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