Construction of Low-Complexity, Capacity-Achieving Code Families from Expander Graphs

该项目的目的是探索编码理论的新方向之一：由双分图构建的码族，它提供与传输比特数成比例的迭代解码复杂度（第一次）。扩展码的潜在应用包括高速光学线路、无线线路和深空应用中的前向纠错。已知存在易于构造的码族，在迭代译码时达到信道容量，并保证译码错误概率呈指数下降。这些码族的一个显著特征是，解码收敛到正确的决定是依靠底层图的展开属性建立的。本项目致力于构建符合或超过g.d. Forney意义上的串行连接码的错误性能的扩展码族（并行连接），同时将解码复杂度从二次时间降低到线性时间，并研究由二部图构造的中等长度（最多10,000）码的错误概率。正在解决的具体问题是：(a)建立对错误概率和在各种版本的基本迭代解码程序下可纠正的错误数量的改进估计；(b)研究扩展码在信道容量邻域中码率的错误概率；(c)基于二部图和特定的短二进制码构建实用的中等长度代码，并对其错误概率进行计算机模拟；(d)将扩展器代码结构从两级推广到多级版本；研究多层结构的误差性能。

The purpose of the project is to explore one of the newdirections in coding theory: code families constructed from bipartitegraphs which afford iterative decoding of complexity proportional to(the first degree of) the number of transmitted bits. Potentialapplications of expander codes include forward error correction inhigh-speed optical lines, wireless lines, and deep-space applications.It is known that there exist easily constructible code families thatreach capacity of the channel under iterative decoding and ensureexponential decline of the error probability of decoding. Adistinctive feature of these code families is that convergence ofdecoding to the correct decision is established relying on expandingproperties of the underlying graph.This project concentrates on constructing families of expander codes(parallel concatenations) that match or surpass the error performanceof serially concatenated codes in the sense of G. D. Forney, whilebringing the decoding complexity down from quadratic to linear-time,and studying the error probability of codes of moderate length (up to10,000) constructed from bipartite graphs. The specific problemsbeing addressed are: (a) to establish improved estimates of the errorprobability and of the number of errors correctable under variousversions of the basic iterative decoding procedure; (b) to study theerror probability of expander codes for code rates in the neighborhoodof the channel capacity; (c) to construct practical codes of moderatelength based on bipartite graphs and specific short binary codes andto perform computer simulations of their error probability; (d) togeneralize the expander code construction from two levels to amultilevel version; to study the error performance of the multilevelconstruction.