Collaborative Research: Next Generation Decoders for Reed-Solomon Codes

摘要-数字通信，体现在这样的应用，如手机和无线互联网，现在渗透到我们的日常生活，而数字存储设备，如CD，DVD和计算机磁盘驱动器，已成为保存我们的信息的主要手段。在我们大家现在生活的“信息时代”，对数字数据的可靠传输和存储的需要是至关重要的。使这种可靠的传输和存储成为可能的是纠错码，这是Claude Shannon在50多年前首次提出的。事实上，当你阅读这些行的时候，每分钟都有数百万个纠错码被解码，使用的是在定制VLSI电路中实现的高效算法。这些电路中至少有75%解码里德-所罗门码，这是欧文里德和古斯塔夫所罗门在20世纪60年代发明的。自Reed-Solomon码发明以来的四十年中，人们对它进行了广泛的研究，并开发了针对这些码的巧妙的解码算法。然而，直到最近才意识到，里德-所罗门码可以纠正的错误比以前认为的要多得多！在一系列的理论突破中，Sudan、Guruswami-Sudan和Koetter-Vardy使得最先进的Reed-Solomon解码器过时了。至少在原则上，我们现在可以用同样的代码实现更好的性能。该项目的目标是跟进这一令人兴奋的近期工作，并遵循这一研究路线，在理论和实践中发挥其最终潜力。 为了达到这个目标，我们计划了一条广泛的进攻路线。一方面，拟议的调查将解决深层次的理论问题。一个人能超过古鲁斯瓦米-苏丹解码半径吗？代数软判决译码的最佳多重数分配是什么？如何将迭代译码方法应用于Reed-Solomon码？另一方面，我们打算一路走到有史以来第一次VLSI实现的软决策里德-所罗门解码器。建议的VLSI架构的目标是高速和低功耗。因此，复杂性的考虑，固有的动机的做法，超大规模集成电路设计，将是至关重要的，在我们的调查。本文的主要研究内容包括：（1）Guruswami-Sudan半径以外的多元插值译码;（2）代数软判决译码的概率模型和多重数分配方案;（3）Reed-Solomon码软判决译码的迭代方法;（4）最大似然译码器和次优译码器性能的分析界;（5）最大似然译码器和次优译码器性能的分析界;（6）最大似然译码器和次优译码器性能的分析界;（7）最大似然译码器和次优译码器性能的分析界。以及（5）在FPGA和/或ASIC中完成最先进的软判决Reed-Solomon解码器的VLSI实现。

Abstract-------- Digital communication, embodied in such applications as cell phones and wireless Internet, by now pervades our daily lives, while digital storage devices, such as CDs, DVDs, and computer disk drives, have become the principal means of preserving our information. In the "information age" in which we all now live, the need for reliable transmission and storage of digital data is of paramount importance. What makes such reliable transmission and storage possibles are error-correcting codes, first conceived by Claude Shannon over 50 years ago. Indeed, as you are reading these lines, millions of error-correcting codes are decoded every minute, using efficient algorithms implemented in custom VLSI circuits. At least 75% of these circuits decode Reed-Solomon codes, invented by Irving Reed and Gustave Solomon in the 1960s. In the four decades since their invention, Reed-Solomon codes have been extensively studied and ingenious decoding algorithms for these codes have been developed. What has been realized only recently, however, is that Reed-Solomon codes can correct many more errors than previously thought possible! In a series of theoretical breakthroughs, Sudan, Guruswami-Sudan, and Koetter-Vardy have made state-of-the-art Reed-Solomon decoders out of date. At least in principle, we can now achieve much better performance with the same codes. The goal of this project is to follow-up on this exciting recent work and to follow this line of research through to its ultimate potential, in theory as well as in practice. In order to attain this goal, we plan a broad line of attack. On one hand, the proposed investigation will address deep theoretical questions. Can one exceed the Guruswami-Sudan decoding radius? What is the optimal multiplicity assignment for algebraic soft-decision decoding? How can iterative decoding methods be applied to Reed-Solomon codes? On the other hand, we intend to go all the way to the first-ever VLSI implementation of a soft-decision Reed-Solomon decoder. The proposed VLSI architecture aims for high speed and low power dissipation. Thus complexity considerations, inherently motivated by the practice of VLSI design, will be paramount throughout our investigation. Specifically, The main topics to be investigated are: (1) Multivariate interpolation decoding beyond the Guruswami-Sudan radius; (2) Probabilistic model and multiplicity assignment schemes for algebraic soft-decision decoding; (3) Iterative methods for soft decision decoding of Reed-Solomon codes; (4) Analytic bounds on the performance of maximum-likelihood and suboptimal decoders; and (5) Complete VLSI implementation of a state-of-the-art soft-decision Reed-Solomon decoder in an FPGA and/or ASIC.