Title :
Generating random Tanner-graphs with large girth
Author :
Bayati, Mohsen ; Keshavan, Raghunandan ; Montanari, Andrea ; Oh, Sewoong ; Saberi, Amin
Author_Institution :
Dept. of Electr. Eng., Stanford Univ., Stanford, CA, USA
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.
Keywords :
graph theory; parity check codes; LDPC codes; high performance low-density parity-check codes; random Tanner-graphs; random generation; Algorithm design and analysis; Bipartite graph; Conferences; Delay; Design optimization; Engineering management; Information theory; Parity check codes; Sampling methods; Statistics;
Conference_Titel :
Information Theory Workshop, 2009. ITW 2009. IEEE
Conference_Location :
Taormina
Print_ISBN :
978-1-4244-4982-8
Electronic_ISBN :
978-1-4244-4983-5
DOI :
10.1109/ITW.2009.5351491
