Title :
Progressive edge-growth Tanner graphs
Author :
Hu, Xiao Yu ; Eleftheriou, Evangelos ; Arnold, Dieter Michael
Author_Institution :
IBM Res. Div., Ruschlikon, Switzerland
Abstract :
We propose a general method for constructing Tanner (1981) graphs with large girth by progressively establishing edges or connections between symbol and check nodes in an edge-by-edge manner, called progressive edge-growth (PEG) construction. Lower bounds on the girth and on the minimum distance of the resulting low-density parity-check (LDPC) codes are derived in terms or parameters of the graphs. Encoding of LDPC codes based on the PEG principle is also investigated. We show how to exploit the PEG graph construction to obtain LDPC codes that allow linear time encoding. The advantages of PEG Tanner graphs over randomly constructed graphs are demonstrated by extensive simulation results on code performance
Keywords :
computational complexity; error correction codes; error detection codes; graph theory; iterative decoding; linear codes; LDPC codes; check nodes; graph girth; graph parameters; iterative decoding; linear code; linear time encoding; low-complexity encoding; low-density parity-check codes; lower bounds; minimum distance; performance; progressive edge-growth; progressive edge-growth Tanner graphs; randomly constructed graphs; simulation results; sparse parity check matrix; Encoding; Error analysis; Information theory; Iterative algorithms; Iterative decoding; Laboratories; Parity check codes; Sparse matrices; Sum product algorithm; Turbo codes;
Conference_Titel :
Global Telecommunications Conference, 2001. GLOBECOM '01. IEEE
Conference_Location :
San Antonio, TX
Print_ISBN :
0-7803-7206-9
DOI :
10.1109/GLOCOM.2001.965567
