Regular ultra-sparse graphs and related non-binary LDPC codes

This page collects some good ultra-sparse graphs that were obtained with a randomized Progressive
Edge Growth (PEG) algorithm [1]. By ultra-sparse graph, we mean a bipartite graph with two constant connection
degrees (dv,dc), and with dv=2. When the obtained graph has minimum size (smallest number of nodes), we
indicate that the size is minimum*.

These particular graphs can have multiple possible applications, including building good non-binary LDPC codes in high order fields [2,3]. The graphs are stored in the MacKay A-list format (http://www.inference.phy.cam.ac.uk/mackay/CodesFiles.html).

[1] A. Venkiah, D. Declercq and C. Poulliat, "Design of Cages with a Randomized Progressive Edge-Growth Algorithm", in IEEE Commun. Letters, vol. 12(4), pp. 1-3, April 2008.

[2] X.-Y. Hu, E. Eleftheriou, D.-M. Arnold, "Regular and Irregular Progressive Edge-Growth Tanner Graphs", IEEE Trans. Info. Theo., 51(1), pp. 386-398, January 2005.

[3] C. Poulliat, M. Fossorier and D. Declercq, "Design of regular (2,dc)-LDPC codes over GF(q) using their binary images", accepted in IEEE Trans. Commun., 2007.

These particular graphs can have multiple possible applications, including building good non-binary LDPC codes in high order fields [2,3]. The graphs are stored in the MacKay A-list format (http://www.inference.phy.cam.ac.uk/mackay/CodesFiles.html).

[1] A. Venkiah, D. Declercq and C. Poulliat, "Design of Cages with a Randomized Progressive Edge-Growth Algorithm", in IEEE Commun. Letters, vol. 12(4), pp. 1-3, April 2008.

[2] X.-Y. Hu, E. Eleftheriou, D.-M. Arnold, "Regular and Irregular Progressive Edge-Growth Tanner Graphs", IEEE Trans. Info. Theo., 51(1), pp. 386-398, January 2005.

[3] C. Poulliat, M. Fossorier and D. Declercq, "Design of regular (2,dc)-LDPC codes over GF(q) using their binary images", accepted in IEEE Trans. Commun., 2007.

Graphs with (dv=2,dc=3)

[girth=6,N=6] | graph with (dv=2,dc=3,girth=6) and minimum* size N=6 |

[girth=8,N=9] | graph with (dv=2,dc=3,girth=8) and minimum* size N=9 |

[girth=10,N=15] | graph with (dv=2,dc=3,girth=10) and minimum* size N=15 |

[girth=12,N=21] | graph with (dv=2,dc=3,girth=12) and minimum* size N=21 |

[girth=14,N=36] | graph with (dv=2,dc=3,girth=14) and minimum* size N=36 |

[girth=16,N=45] | graph with (dv=2,dc=3,girth=16) and minimum* size N=45 |

[girth=18,N=114] | graph with (dv=2,dc=3,girth=18) and size N=114 |

[girth=20,N=201] | graph with (dv=2,dc=3,girth=20) and size N=201 |

[girth=22,N=447] | graph with (dv=2,dc=3,girth=22) and size N=447 |

[girth=24,N=726] | graph with (dv=2,dc=3,girth=24) and size N=726 |

[girth=26,N=1602] | graph with (dv=2,dc=3,girth=26) and size N=1602 |

Graphs with (dv=2,dc=4)

[girth=6,N=10] | graph with (dv=2,dc=4,girth=6) and minimum* size N=10 |

[girth=8,N=16] | graph with (dv=2,dc=4,girth=8) and minimum* size N=16 |

[girth=10,N=38] | graph with (dv=2,dc=4,girth=10) and minimum* size N=38 |

[girth=12,N=52] | graph with (dv=2,dc=4,girth=12) and minimum* size N=52 |

[girth=14,N=260] | graph with (dv=2,dc=4,girth=14) and size N=260 |

[girth=16,N=160] | graph with (dv=2,dc=4,girth=16) and minimum* size N=160 |

Graphs with (dv=2,dc=5)

[girth=6,N=15] | graph with (dv=2,dc=5,girth=6) and minimum* size N=15 |

[girth=8,N=25] | graph with (dv=2,dc=5,girth=8) and minimum* size N=25 |

[girth=10,N=90] | graph with (dv=2,dc=5,girth=10) and size N=90 |

[girth=12,N=105] | graph with (dv=2,dc=5,girth=12) and minimum* size N=105 |

Graphs with (dv=2,dc=6)

[girth=6,N=21] | graph with (dv=2,dc=6,girth=6) and minimum* size N=21 |

[girth=8,N=36] | graph with (dv=2,dc=6,girth=8) and minimum* size N=36 |

[girth=10,N=189] | graph with (dv=2,dc=6,girth=10) and size N=189 |

[girth=12,N=186] | graph with (dv=2,dc=6,girth=12) and minimum* size N=186 |

Graphs with (dv=2,dc=7)

[girth=6,N=28] | graph with (dv=2,dc=7,girth=6) and minimum* size N=28 |

[girth=8,N=49] | graph with (dv=2,dc=7,girth=8) and minimum* size N=49 |

[girth=10,N=385] | graph with (dv=2,dc=7,girth=10) and size N=385 |

[girth=12,N=840] | graph with (dv=2,dc=7,girth=12) and size N=840 |

Graphs with (dv=2,dc=8)

[girth=6,N=36] | graph with (dv=2,dc=8,girth=6) and minimum* size N=36 |

[girth=8,N=64] | graph with (dv=2,dc=8,girth=8) and minimum* size N=64 |

[girth=10,N=680] | graph with (dv=2,dc=8,girth=10) and size N=680 |

Graphs with (dv=2,dc=9)

[girth=6,N=45] | graph with (dv=2,dc=9,girth=6) and minimum* size N=45 |

[girth=8,N=81] | graph with (dv=2,dc=9,girth=8) and minimum* size N=81 |

Graphs with (dv=2,dc=10)

[girth=6,N=55] | graph with (dv=2,dc=10,girth=6) and minimum* size N=55 |

[girth=8,N=100] | graph with (dv=2,dc=10,girth=8) and minimum* size N=100 |

Graphs with (dv=2,dc=20)

[girth=6,N=210] | graph with (dv=2,dc=20,girth=6) and minimum* size N=210 |

[girth=8,N=400] | graph with (dv=2,dc=20,girth=8) and minimum* size N=400 |

Graphs with (dv=2,dc=30)

[girth=6,N=465] | graph with (dv=2,dc=30,girth=6) and minimum* size N=465 |

[girth=8,N=900] | graph with (dv=2,dc=30,girth=8) and minimum* size N=900 |

Graphs with (dv=2,dc=40)

[girth=6,N=820] | graph with (dv=2,dc=40,girth=6) and minimum* size N=820 |

[girth=8,N=1600] | graph with (dv=2,dc=40,girth=8) and minimum* size N=1600 |

Graphs with (dv=2,dc=50)

[girth=6,N=1275] | graph with (dv=2,dc=50,girth=6) and minimum* size N=1275 |

[girth=8,N=2500] | graph with (dv=2,dc=50,girth=8) and minimum* size N=2500 |