David MacKay

Search :


Source code for approximating the MinDist problem of LDPC codes

- kindly supplied by Xiao-Yu Hu [xhu:-:AT:-:zurich.ibm.com]

This free software is to compute approximately the minimum distance and the corresponding multiplicity of iteratively decodeable linear codes, for instance LDPC codes. Recall that the general MinDist problem of linear codes is NP-hard, the software thus produces an estimate and an upper bound of the minimum distance based on true (low-weight) codewords found by a fine-tuned local search. The algorithm proved to be powerful in the sense that it found 2 codewords of weight 20 for MacKay (3,6)-regular (504, 252) code, 1 codeword of weight 34 for MacKay (3, 6)-regular (1008, 504) code, 66 codewords of weight 40 for the Margulis (p=11) code, 2184 codewords of weight 14 for the Ramanujan-Margulis (13, 5) code, and 204 codewords of weight 24 for the Ramanujan-Margulis (17, 5) code.

Download original tar file |

Or Download tar file for linux users (supplied by Oscar Takeshita)

[patch specifying the differences]

associated pdf file

The Inference Group is supported by the Gatsby Foundation
and by a partnership award from IBM Zurich Research Laboratory
David J.C. MacKay
Site last modified Tue Aug 19 18:43:54 BST 2008