Generating random Tanner-graphs with large girth

Mohsen Bayati, Raghunandan Keshavan, Andrea Montanari, Sewoong Oh, Amin Saberi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present a simple and efficient algorithm for randomly generating Tanner-graphs with given symbol-node and check-node degrees and without small cycles. These graphs can be used to design high performance Low-Density Parity-Check (LDPC) codes. Our algorithm generates a graph by sequentially adding the edges to an empty graph. Recently, these types of sequential methods for counting and random generation have been very successful [35], [18], [11], [7], [4], [6].

Original languageEnglish (US)
Title of host publication2009 IEEE Information Theory Workshop, ITW 2009
Pages154-157
Number of pages4
DOIs
StatePublished - Dec 7 2009
Event2009 IEEE Information Theory Workshop, ITW 2009 - Taormina, Sicily, Italy
Duration: Oct 11 2009Oct 16 2009

Publication series

Name2009 IEEE Information Theory Workshop, ITW 2009

Other

Other2009 IEEE Information Theory Workshop, ITW 2009
CountryItaly
CityTaormina, Sicily
Period10/11/0910/16/09

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Information Systems
  • Electrical and Electronic Engineering

Cite this

Bayati, M., Keshavan, R., Montanari, A., Oh, S., & Saberi, A. (2009). Generating random Tanner-graphs with large girth. In 2009 IEEE Information Theory Workshop, ITW 2009 (pp. 154-157). [5351491] (2009 IEEE Information Theory Workshop, ITW 2009). https://doi.org/10.1109/ITW.2009.5351491