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.