CIF: Small: List Decoding for Algebraic Geometry Codes: Theoretical Analysis, Efficient Algorithms, Practical Implementation

CIF：小：代数几何代码的列表解码：理论分析、高效算法、实际实现

• 批准号: 0916492
• 负责人: Michael O'Sullivan
• 金额: $ 22.4万
• 依托单位: San Diego State University Foundation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-07-01 至 2014-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0916492&HistoricalAwards=false
• 关键词: CIF; Small; List; Decoding; Algebraic

CIF:Small:Decoding of Algebraic Geometry Codes:Theoretical Analysis, Efficient Algorithms, Practical ImplementationError control coding ensures the reliability of data transmitted in a noisy environment and is therefore a critical component of communications systems. By adding a bit of redundancy to data, and using sophisticated mathematical algorithms to encode and decode, errors in the system can be reduced to an arbitrarily low threshold. This project concerns algebraic geometry (AG) codes, a large and powerful family of codes that includes Reed-Solomon (RS) codes, which are the standard code used in commercial products today. The standard decoding algorithm for Reed-Solomon codes is the Berlekamp-Massey algorithm, which decodes up to the sphere-packing bound. In the 1980's and 1990's, AG codes were discovered that yielded better error correction performance than RS codes, and efficient algorithms generalizing Berlekamp-Massey were developed. A method for efficiently decoding beyond the sphere-packing bound, called list decoding, was discovered in the 1990's by Sudan.This project advances the theoretical, algorithmic and applied understanding of list decoding for AG codes. There is strong evidence that Sudan's method, when used on high-rate AG codes, can perform much better than current analysis predicts, so a primary focus is improving the theoretical underpinnings of list decoding to discover its maxim capabilities for AG codes. The investigators also improve the efficiency of current algorithms and tailor them to hardware implementation by combining classical Berlekamp-Massey type methods and recent innovations due to several researchers. The investigators work with hardware and communication engineers in industry and in academia to identify applications where the special properties of AG codes will be particularly advantageous.

CIF：小：代数几何代码的解码：理论分析、高效算法、实际实现差错控制编码可确保在噪声环境中传输数据的可靠性，因此是通信系统的关键组成部分。通过向数据添加一点冗余，并使用复杂的数学算法进行编码和解码，系统中的错误可以减少到任意低的阈值。该项目涉及代数几何 (AG) 代码，这是一个庞大而强大的代码系列，其中包括里德-所罗门 (RS) 代码，这是当今商业产品中使用的标准代码。 Reed-Solomon 码的标准解码算法是 Berlekamp-Massey 算法，该算法最多可解码至球填充边界。在 20 世纪 80 年代和 90 年代，人们发现 AG 码比 RS 码具有更好的纠错性能，并且开发了推广 Berlekamp-Massey 的高效算法。苏丹于 1990 年代发现了一种超越球填充界限的有效解码方法，称为列表解码。该项目推进了对 AG 码列表解码的理论、算法和应用理解。有强有力的证据表明，Sudan 的方法在用于高速率 AG 码时，性能比当前分析预测的要好得多，因此主要重点是改进列表解码的理论基础，以发现其对 AG 码的最大能力。研究人员还通过结合经典的 Berlekamp-Massey 类型方法和几位研究人员的最新创新，提高了当前算法的效率，并根据硬件实现对其进行了定制。研究人员与工业界和学术界的硬件和通信工程师合作，以确定 AG 代码的特殊属性将特别有利的应用。