We report weaknesses in two algebraic constructions of low-density parity-check codes based on expander graphs. The Margulis construction gives a code with near-codewords, which cause problems for the sum-product decoder; The Ramanujan-Margulis construction gives a code with low-weight codewords, which produce an error-floor.
@inproceedings{MacKayPostol2002,
author={David J. C. MacKay and M. J. Postol},
title={Weaknesses of {M}argulis and {R}amanujan--{M}argulis Low-Density Parity-Check Codes},
booktitle={Proceedings of MFCSIT2002, Galway},
volume={74},
series={Electronic Notes in Theoretical Computer Science},
publisher={Elsevier},
url={http://www.inference.org.uk/mackay/abstracts/margulis.html},
year={2003}
}
All postscript files are compressed with gzip - see this page for advice about gzip, if needed.