Collaborative Research: Next Generation Decoders for Reed-Solomon Codes

摘要-数字通信体现在手机和无线互联网等应用中，现在已经渗透到我们的日常生活中，而数字存储设备，如CD、DVD和计算机磁盘驱动器，已经成为保存我们信息的主要手段。在我们现在所处的“信息时代”，可靠地传输和存储数字数据是至关重要的。使这种可靠的传输和存储成为可能的是纠错码，它最初是由克劳德·香农在50多年前构思的。事实上，当您阅读这些行时，使用在定制VLSI电路中实现的高效算法，每分钟都会解码数百万个纠错码。这些电路中至少有75%对欧文·里德和古斯塔夫·所罗门在20世纪60年代发明的里德-所罗门码进行译码。在里德-所罗门码发明以来的四十年里，人们对其进行了广泛的研究，并开发出了巧妙的译码算法。然而，直到最近才意识到的是，里德-所罗门码可以纠正比以前认为可能的更多的错误！在一系列理论突破中，苏丹、苏丹古鲁斯瓦米和科特-瓦尔迪已经使最先进的里德-所罗门解码器过时了。至少在原则上，我们现在可以用相同的代码实现更好的性能。该项目的目标是对最近这项令人振奋的工作进行后续工作，并沿着这一研究路线，在理论和实践中发挥其最终潜力。为了实现这一目标，我们计划了广泛的攻击路线。一方面，拟议的调查将解决深层次的理论问题。可以超过古鲁斯瓦米-苏丹的解码半径吗？代数软判决译码的最佳多重数分配是多少？如何将迭代译码方法应用于里德-所罗门码？另一方面，我们打算实现有史以来第一个软判决里德-所罗门解码器的VLSI实现。所提出的VLSI结构以高速和低功耗为目标。因此，由VLSI设计实践内在驱动的复杂性考虑在整个调查过程中将是最重要的。具体地说，主要研究内容包括：(1)超出Guruswami-苏丹半径的多元内插译码；(2)代数软判决译码的概率模型和重数分配方案；(3)Reed-Solomon码软判决译码的迭代方法；(4)最大似然译码和次优译码性能的解析界；(5)最先进的软判决译码的VLSI在FPGA和/或ASIC中的实现。

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.