Analysis of Low Density Codes and Improved Designs Using Irregular Graphs

Authors: Michael G. Luby, Michael Mitzenmacher, M. Amin Shokrollahi, Daniel A. Spielman.

Bibliographic Information: Appeared in the The Thirtieth Annual ACM Symposium on Theory of Computing (STOC) Incorporated into the journal article Improved Low-Density Parity-Check Codes Using Irregular Graphs.

Abstract

In 1960, Gallager introduced a family of codes based on sparse bipartite graphs, which he called low-density parity-check codes. He suggested a natural decoding algorithm for these codes, and proveed a good bound on the fraction of errors that can be corrected. As the codes that Gallager builds are derived from regular graphs, we refer to them as iregular codes.

Following the general approach introduced in \cite{LMSSS} for the design and analysis of erasure codes, we consider error-correcting codes based on random irregular bipartite graphs, which we call {\em irregular codes}. We introduce tools based on linear programming for designing linear time irregular codes with better error-correcting capabilities than possible with regular codes. For example, the decoding algorithm for the rate 1/2 regular codes of Gallager can provably correct up to 5.17% errors asymptotically, whereas we have found irregular codes for which our decoding algorithm can provably correct up to 6.27% errors asymptotically. We include the results of simulations demonstrating the effectiveness of our codes on systems of reasonable size.

You can download this paper as Postscript, compressed Postscript, PDF, or compressed PDF.