Efficient Algorithms for Encoding and Decoding Asymptotically Good Error Correcting Codes

这项工作的主要重点是纠错码的理论设计和分析。香农界限制了这种码的解码能力，给定其速率。这项研究的基本目标，与应用到不同领域的科学和通信，是设计序列的代码是渐近良好的（实现香农界），并具有线性时间编码和解码算法。 最近，线性时间擦除码已经被设计为基于具有明确定义的结构的随机图的构造。 该方法的新奇在于，“智能”是在随机图的结构，和“天真”的算法被用来编码和解码。 所提出的工作开始与相同的基本方法用于纠删码，并试图将其扩展到更难的问题，设计线性时间渐近良好的纠错码。

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.