Encyclopedia of Sparse Graph Codes

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

This is a database of sparse graph codes. Properties recorded include the codes' parity check matrices, their rates and minimum distances, their empirical performance on the binary input Gaussian noise channel, and histograms of decoding times.

These Codes and Related Data are made freely available under the conditions that (1) when they are used, the authors of the codes and the data and this archive are acknowledged; (2) the authors of the codes and data are not liable for any inaccuracies in the materials presented here or any failure of the codes to work as hoped.

Note: there are more codes that I have simulated that have not yet made it into this archive. If you have any requests for additions, email me. With appropriate incentives (eg financial support for my group), I can probably help.

Key for ascii performance files: see this file.
Further information about alist format.

Note on high rate codes:
the following numbers give the highest rate codes I have made with column weights 3 and 4.

   Rate  j N    M
  0.889  4 1998 222 
  0.876  4 3584 444
  0.889  3 999  111
  0.9098 3 998   90  
  0.889  3 900  100
  0.8745 3 494   62
  0.878  3 492   60
  0.927  4 4096 300
  0.936  4 4376 282

Acknowledgements: The work of the inference group is supported by IBM Zurich research laboratory.

Under construction

• Gallager codes
  • Gallager codes with rate 1/2
    • Column weight t=3
    • Column weight t=4
    • Column weight t=5
    • Column weight t=6
    • Irregular codes with rate 1/2
    • Regular and Irregular codes with rate 1/2, Progressive Edge Growth (PEG) construction
  • Gallager codes with rate 1/3
    • Column weight t=2,3 or 3
    • Column weight t=4
    • Column weight 4, tiny block length
    • Column weight t=6
  • Assorted Regular Gallager codes
  • Gallager codes with Rate 1/4
  • High rate Gallager codes (R=0.7,0.77)
    • (273,191) (R~0.7)
    • (1057,813) (R~0.77)
  • Very high rate Gallager codes (R~=0.89,0.94)
    • Column Weight 3, N=495, Rate=0.87
    • Column Weight 3, N=999, Rate=0.89
    • Column Weight 4, N~=1998, Rate=0.89
    • Column Weight 4, N~=4000, Rate~=0.9
    • Column Weights less than 4, N=1998, Rate=0.89
  • More high rate codes (R=.82-.93)
    • Length 4095 with Rate=0.82
    • Length 16383 with rate=0.87
    • Length 32000 with rate=0.93.
• Gallager-like codes and Algebraically constructed codes
  • Tiny regular codes
  • DSC codes
• Repeat-accumulate codes (Divsalar, D., Jin, H., and McEliece, R. J., 1998)