Analysis of Low Density Codes and Improved Designs Using Irregular Graphs

TitleAnalysis of Low Density Codes and Improved Designs Using Irregular Graphs
Publication TypeTechnical Report
Year of Publication1997
AuthorsLuby, M., Mitzenmacher M., M. Shokrollahi A., & Spielman D. A.
Other Numbers1109

In [6] Gallager introduces a family of codes based on sparse bipartite graphs, which he calls low-density parity-check codes. He suggests a natural decoding algorithm for these codes, and proves 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 regular codes. Following the general approach introduced in [7] for the design and analysis of loss-resilient codes, we consider error-correcting codes based on random irregular bipartite graphs, which we call 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, whereas we have found irregular codes for which our decoding algorithm can provably correct up to 6.27%.

Bibliographic Notes

ICSI Technical Report TR-97-045

Abbreviated Authors

M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman

ICSI Publication Type

Technical Report