

David MacKay's Gallager code resources
Questions about
David MacKay's Sparse graph code resources are answered here.
Contents:

Source code for Progressive Edge Growth paritycheck matrix construction
 kindly supplied by XiaoYu 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 rate1/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:

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

Source code for approximating the MinDist problem of LDPC codes
 kindly supplied by XiaoYu 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 NPhard, the software thus produces an estimate and an
upper bound of the minimum distance based on true (lowweight)
codewords found by a finetuned 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
RamanujanMargulis (13, 5) code, and 204 codewords of weight 24 for the
RamanujanMargulis (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

A mirror of Gallager's classic book is here,
Gallager, R. G., Low Density Parity Check Codes, Monograph, M.I.T. Press, 1963.
 IMA 1999 workshop on Codes, Systems
and Graphical Models,
 Rudi Urbanke's profile optimizer

S Y Chung's profile optimizer
and
info.
 Igor's Matlab software for creating matrices, making
generators, etc. Uses its own format, but can convert from alist.
 Radford Neal's
software for low density
parity check codes written to test
out sparse encoding methods.
 makeH.tcl  tool to assist manual construction
of paritycheck matrices.
All David MacKay's papers can be found here,
and his textbook on information theory is here: Information Theory,
Inference, and Learning Algorithms.
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.

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. MacKaySite last modified Tue Aug 19 18:43:54 BST 2008

