Good Error-Correcting
Codes based on Very Sparse Matrices
David J C MacKay
Published in IEEE transactions on Information Theory, March 1999
We study two families of error-correcting codes
defined in terms of very sparse matrices. `MN' (MacKay--Neal)
codes are
recently invented, and `Gallager codes' were first investigated
in 1962, but
appear to have been largely forgotten, in spite of their excellent
properties. The decoding of both codes
can be tackled with a practical sum-product algorithm.
We prove that these codes are `very good', in that sequences
of codes exist which, when optimally decoded, achieve
information rates up to the Shannon limit. This result holds
not only for the binary symmetric channel
but also for any channel with symmetric stationary ergodic
noise.
We give experimental results for binary symmetric channels and
Gaussian channels demonstrating that practical performance
substantially better than that of standard convolutional and
concatenated codes can be achieved; indeed the performance of
Gallager codes is almost as close to the Shannon limit as that of
Turbo codes.
postscript. (55 pages)
| pdf|
DJVU |
Also available: an earlier version of this paper in massively shortened form:
postscript. (This paper, authors MacKay and Neal,
appeared in the proceedings of the 5th IMA conference on Coding and Cryptography, December 1995. But the present paper has a lot more in it.)
Chinese translation
by Dong Xiangyu (rioshering-at-hotmail.com)
David MacKay's:
home page,
publications.
bibtex file.
Canadian mirrors:
| ps mirror, Canada
| pdf
| DJVU |
home page,
publications.
bibtex file.