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）代码，一个庞大而强大的代码家族，包括Reed-Solomon（RS）代码，这是当今商业产品中使用的标准代码。Reed-Solomon码的标准解码算法是Berlekamp-Massey算法，其解码到球形填充边界。在20世纪80年代和90年代，发现AG码产生比RS码更好的纠错性能，并且开发了推广Berlekamp-Massey的有效算法。Sudan在20世纪90年代发现了一种有效地解码超出球形包装界限的方法，称为列表解码。该项目推进了对AG码列表解码的理论，算法和应用理解。有强有力的证据表明，苏丹的方法，当用于高速率AG码，可以执行比目前的分析预测，所以一个主要的焦点是改善列表解码的理论基础，以发现其最大的能力AG码。研究人员还提高了当前算法的效率，并通过将经典的Berlekamp-Massey类型方法和几位研究人员最近的创新相结合，将其定制为硬件实现。研究人员与工业界和学术界的硬件和通信工程师合作，以确定AG码的特殊属性将特别有利的应用。