David MacKay

Search :


David MacKay's Gallager code resources

qeccmove3 Questions about David MacKay's Sparse graph code resources are answered here.


Source code for Progressive Edge Growth parity-check matrix construction

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

The PEG construction creates matrices with very large girth. This construction has proved to produce the best known Gallager codes, and is especially significant for small blocklengths such as 500, 1000, or 2000.

Examples of rate-1/2 codes constructed in this way can be found in the Encyclopedia of Sparse Graph Codes.

| Download tar file | | Download Linux/GCC Makefile |

Patched version: ! Download Patch provided by fokko.beekhof | ! Download tar file containing patched source files | ! explanation by fokko.beekhof |

The source files have been tested through the C++ compiler xlC on IBM RS/6000 running AIX operating system. On other compilers and platforms, minor changes may be needed on Makefile and/or source C++ files.

Here are some examples for the commands:

  1. MainPEG -numM 252 -numN 504 -codeName irReg504252.dat -degFileName DenEvl_15.deg
    Remarks: The density-evolution-optimized symbol-node degree sequence of maximum symbol node degree of 15 is used. PEG does not use check node degree sequence; instead it makes the check-node degree as concentrated as possible.
  2. MainPEG -numM 252 -numN 504 -codeName Reg504252.dat -degFileName Reg_3.dat
    Remarks: Each symbol node has a uniform of degree of 3
  3. MainPEG -numM 252 -numN 504 -codeName Reg504252.dat -degFileName Reg_3.dat -sglConcent 0
    Remarks: By specifying -sglConcent 0, the check-node degree sequence is made strictly concentrated or regular
  4. MainPEG -numM 252 -numN 504 -codeName Reg504252.dat -degFileName Reg_3.dat -sglConcent 0 -tgtGirth 8
    Remarks: Non-greedy PEG with target girth of 8
Example PEG codes included in the encyclopedia are as follows:
  • (Reg252x504.dat, Reg504x1008.dat): Symbol-node degree of 3, check-node almost regular
  • (irReg252x504.dat, irReg504x1008.dat): Irregular PEG using density-evolution optimized degree distribution of maximum degree of 15.
  • (irUppTriang518x1024.dat, irUppTriang1030x2048.dat): Irregular linear-time-encodeable PEG codes using density-evolution optimized degree distribution of maximum degree of 15. Upper triangular form.

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

Other useful sites

Papers on Gallager codes by me and my students

All David MacKay's papers can be found here, and his textbook on information theory is here: Information Theory, Inference, and Learning Algorithms.

Matrices for codes

Matrices `A', `Cn', and `G' are respectively the parity check matrix (in list format), the right hand square bit of A, and the generator matrix for the code.

More matrices

Digital Fountain codes

This page summarises resources for learning about Digital fountain codes.

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