Irregular progressive edge-growth Tanner graphs

Abstract

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, was recently proposed by the authors. In this paper 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 hits, 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 and demonstrate that such codes offer comparable performance to the standardized Turbo codes with essentially the same encoding/decoding complexity. 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(26) with a block-error rate < 10-4 at Eb/N0 2 dB, which appears to have the best performance at this short block length to date.