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).

David MacKay's: home page, publications. bibtex file.
Canadian mirrors: home page, publications. bibtex file.