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

从扩展图构建低复杂度、可实现容量的代码系列

• 批准号: 0310961
• 负责人: Alexander Barg
• 金额: $ 21.06万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-09-15 至 2006-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0310961&HistoricalAwards=false
• 关键词: Construction; Low; Complexity; Capacity; Achieving

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.

该项目的目的是探索编码理论中的一个新方向：由二分图构造的码族，它提供了与传输比特数成比例的复杂度的迭代解码。 扩展码的潜在应用包括在高速光线路、无线线路和深空应用中的前向纠错，已知存在易于构造的码族，它们在迭代译码下达到信道容量，并确保译码错误概率指数下降。这些码族的一个显著特点是译码收敛到正确判决依赖于底层图的扩展性质，本项目致力于构造扩展码（并行级联）族，它们在G. D. Forney的方法，同时将译码复杂度从二次降低到线性时间，并研究了由二部图构造的中等长度（最大为10，000）码的错误概率。 具体的问题是：（a）建立在各种基本迭代译码过程下的差错概率和可纠正差错数的改进估计：（B）研究在信道容量附近码率下扩展码的差错概率;（c）第（1）款基于二部图和特定的二进制短码构造实用的中长码，并对其误差进行计算机模拟概率;（4）将扩展码的结构从两级扩展到多级扩展，研究多级扩展的误码性能。