Regular and irregular progressive edge-growth tanner graphs

TLDR

The paper proposes the progressive edge‑growth (PEG) algorithm to construct Tanner graphs with large girth. The authors derive girth and minimum‑distance bounds for PEG Tanner graphs, explore variations that yield linear‑time encodable LDPC codes, and study regular and irregular PEG‑based LDPC codes over GF(q). Simulations confirm that PEG produces high‑performance short‑block‑length LDPC codes.

Abstract

We propose a general method for constructing Tanner graphs having a large girth by establishing edges or connections between symbol and check nodes in an edge-by-edge manner, called progressive edge-growth (PEG) algorithm. 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. Simple variations of the PEG algorithm can also be applied to generate linear-time encodeable LDPC codes. Regular and irregular LDPC codes using PEG Tanner graphs and allowing symbol nodes to take values over GF(q) (q>2) are investigated. Simulation results show that the PEG algorithm is a powerful algorithm to generate good short-block-length LDPC codes.