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

University Of Maryland, College Park, College Park MD

Investigators

Abstract

The purpose of the project is to explore one of the new directions in coding theory: code families constructed from bipartite graphs which afford iterative decoding of complexity proportional to (the first degree of) the number of transmitted bits. Potential applications of expander codes include forward error correction in high-speed optical lines, wireless lines, and deep-space applications. It is known that there exist easily constructible code families that reach capacity of the channel under iterative decoding and ensure exponential decline of the error probability of decoding. A distinctive feature of these code families is that convergence of decoding to the correct decision is established relying on expanding properties of the underlying graph. This project concentrates on constructing families of expander codes (parallel concatenations) that match or surpass the error performance of serially concatenated codes in the sense of G. D. Forney, while bringing the decoding complexity down from quadratic to linear-time, and studying the error probability of codes of moderate length (up to 10,000) constructed from bipartite graphs. The specific problems being addressed are: (a) to establish improved estimates of the error probability and of the number of errors correctable under various versions of the basic iterative decoding procedure; (b) to study the error probability of expander codes for code rates in the neighborhood of the channel capacity; (c) to construct practical codes of moderate length based on bipartite graphs and specific short binary codes and to perform computer simulations of their error probability; (d) to generalize the expander code construction from two levels to a multilevel version; to study the error performance of the multilevel construction.