High-Performance Decoding of Algebraic Codes Beyond their Packing Radii

摘要 这项研究将改进差错控制码的解码，特别是里德-所罗门码，这是最先进的现代通信和存储系统中必不可少的，从深空通信到光和磁存储系统，如光盘和CD-ROM。通过开发在较低信噪比下工作的解码器，这项研究将允许恢复目前不可读的数据和记录。 这项研究将开发一种有效的软解码算法，将显着优于基于GMD的解码算法。该算法是基于苏丹的列表解码技术，产生一个试探性的码字列表，它显示了一些非常有趣的功能，其中最有趣的特点的算法是一个复杂性和性能，可以自由地交易在某些fundamentallimits。因此，由里德-所罗门码提供的编码增益可以在任何应用中由于复杂性而在运行中背叛，其中最大列表大小相应地改变。

Abstract This research will improve the decoding of error-control codes, inparticular, Reed-Solomon codes, which are essential in most advanced moderncommunication and storage systems, ranging from deep space communication to optical and magnetic storage systems, such as the compact disk and CD-ROM.By developing decoders that operate at lower signal to noise ratios, thisresearch will allow the recovery of data and records that currently areunreadable. This research will develop an efficient soft decoding algorithm that will significantly outperform GMD-based decoding algorithms. The algorithmis based on Sudan's list decoding technique that produces a list of tentative codewords and it shows a number of very interesting features.Among the most intriguing characteristics of the algorithm is a complexityand performance that can be traded freely within certain fundamentallimits. Hence, the coding gain provided by the Reed-Solomon code can betraded on the fly for complexity in any application with the maximallist size changing accordingly.