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.