Collaborative Research: Next Generation Decoders for Reed-Solomon Codes

合作研究：下一代里德-所罗门码解码器

• 批准号: 0514890
• 负责人: Alexander Vardy
• 金额: $ 26.07万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-07-01 至 2008-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0514890&HistoricalAwards=false
• 关键词: Collaborative; Research; Next; Generation; Decoders

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.

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