Regular and Irregular Progressive Edge-Growth Tanner Graphs

We propose a general method for constructing Tanner graphs having a 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 of PEG Tanner graphs and on the minimum distance of the resulting low-density parity-check (LDPC) codes are derived in terms of parameters of the graphs. We describe an empirical approach using a variant of the "downhill simplex" search algorithm to design irregular PEG graphs for small codes with fewer than thousands of bits, which complements the asymptotic analysis of "density evolution". 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. Finally, we generalize the regular and irregular LDPC codes by using the same PEG Tanner graph but allowing the symbol nodes to take values over GF(q), q>2. Simulation results show that the resulting LDPC codes of PEG Tanner graphs significantly outperform randomly constructed ones. In particular, we report a short-block-length (1008 bit) rate-1/2 irregular PEG code over GF(2**6) with block-error rate < 10**(-4) at Eb/N0 2 dB, which appears to have the best performance at this short block length to date.