Efficient Algorithms for Encoding and Decoding Asymptotically Good Error Correcting Codes

用于编码和解码渐近良好纠错码的高效算法

• 批准号: 9800452
• 负责人: Michael Luby
• 金额: $ 20.38万
• 依托单位: International Computer Science Institute
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-08-15 至 2000-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9800452&HistoricalAwards=false
• 关键词: Efficient; Algorithms; Encoding; Decoding; Asymptotically

The primary focus of this work is on the theoretical design and analysis of error-correcting codes. The Shannon bound puts limits on the decoding capabilities of such a code, given its rate. The fundamental goal of this research, with applications to different areas of science and communication, is to design sequences of codes that are asymptotically good (achieve the Shannon bound) and have linear time encoding and decoding algorithms. Recently, linear time erasure codes have been designed based on the construction of random graphs with well-defined structure. The novelty of the approach is that the ``intelligence'' is in the structure of the random graph, and ``naive'' algorithms are used to encode and decode. The proposed work starts with the same basic approach used for erasure codes and attempts to extend it to the harder problem of designing linear time asymptotically good error-correcting codes.

这项工作的主要重点是对纠错码的理论设计和分析。在给定码率的情况下，香农边界限制了这种码的解码能力。本研究的基本目标是设计渐近良好（达到香农界）并具有线性时间编码和解码算法的代码序列，并应用于科学和通信的不同领域。近年来，基于结构明确的随机图的构造设计了线性时间擦除码。该方法的新颖之处在于“智能”存在于随机图的结构中，并且使用“幼稚”算法进行编码和解码。提出的工作从用于擦除码的相同基本方法开始，并试图将其扩展到设计线性时间渐近好的纠错码的更难的问题。