Complexity and Algorithms of Decoding Algebraic Codes

代数码解码的复杂性和算法

• 批准号: 0830581
• 负责人: Shuhong Gao
• 金额: $ 22.18万
• 依托单位: Clemson University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-08-15 至 2013-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830581&HistoricalAwards=false
• 关键词: Complexity; Algorithms; Decoding; Algebraic; Codes

A signal, when transfered over a long distance, is likely to be corrupted. Error-correcting codes have been designed to solve this problem, so modern communications are possible as we see today. Algebraic codes are mathematically interesting and intriguing, and they form the backbone of coding theory and its applications. The best algorithms for many algebraic codes are very powerful but not very practical. Also, the exact decoding complexity is not well understood for these codes, including the simple but extremely important Reed-Solomon codes. The project will strive to identify the complexity of decoding algebraic codes and to design more efficient algorithms for a large class of algebraic codes. The main focus is on algebraic codes with natural parameters. The complexity results for these natural codes thus are more relevant to communication practice. It is expected that the project will lead to a number of substantial new results linking coding theory, computer sciences and mathematics. The project is also expected to develop graduate courses and train students in this cross-disciplinary research area.

信号在远距离传输时，很可能会被破坏。纠错码就是为了解决这个问题而设计的，所以我们今天所看到的现代通信是可能的。代数码在数学上是有趣的和迷人的，它们构成了编码理论及其应用的支柱。许多代数码的最佳算法非常强大，但不太实用。此外，对于这些码，包括简单但非常重要的里德-所罗门码，确切的解码复杂度还没有很好地理解。该项目将努力确定解码代数码的复杂性，并为一大类代数码设计更有效的算法。主要的重点是代数码与自然参数。因此，这些自然码的复杂度结果与通信实践更相关。预计该项目将导致一系列将编码理论、计算机科学和数学联系起来的新的实质性成果。预计该项目还将开发研究生课程，并在这一跨学科研究领域培训学生。