Improved low-density parity-check codes using irregular graphs

We construct new families of error-correcting codes based on Gallager's low -density parity-check codes. We improve on Gallager's results by introducin g irregular parity-check matrices and a new rigorous analysis of hard-decis ion decoding of these codes. We also provide efficient methods for finding good irregular structures for such decoding algorithms, Our rigorous analys is based on martingales, our methodology for constructing good irregular co des, and the demonstration that irregular structure improves performance co nstitute key points of our contribution, We also consider irregular codes under belief propagation. We report the re sults of experiments testing the efficacy of irregular codes on both binary -symmetric and Gaussian channels, For example, using belief propagation, fo r rate 1/4 codes on 16 000 bits over a binary-symmetric channel, previous l ow-density parity-check codes can correct up to approximately 16% errors, w hile our codes correct over 17%, In some cases our results come very close to reported results for turbo codes, suggesting that variations of irregula r low density parity-check codes may be able to match or beat turbo code pe rformance.