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

点击翻译按钮获取中文摘要

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.