Good Codes based on Very Sparse Matrices
David J C MacKay and Radford M Neal
We present a new family of error-correcting codes for the
binary symmetric channel. These codes are designed to encode a
sparse source, and are defined in terms of very sparse
invertible matrices, in such a way that the decoder can
treat the signal and the noise symmetrically. The decoding
problem involves only very sparse matrices and sparse vectors,
and so is a promising candidate for practical decoding.
It can be proved that these codes are `very good', in that
sequences of codes exist which, when optimally decoded,
achieve information rates up to the Shannon limit.
We give experimental results using a free energy
minimization algorithm and a belief propagation algorithm
for decoding, demonstrating practical performance
superior to that of both
Bose-Chaudhury-Hocquenghem codes and Reed-Muller codes over a
wide range of noise levels.
postscript (Cambridge UK).
postscript (Canada mirror).