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