Randomized Progressive Edge-Growth (RandPEG)

The progressive edge-growth (PEG) construction is a well known algorithm for constructing bipartite graphs with good girth properties. In this paper, we propose some improvements in the PEG algorithm which greatly improve the girth properties of the resulting graphs: given a graph size, they increase the girth g achievable by the algorithm, and when the girth cannot be increased, our modified algorithm minimizes the number of cycles of length g. First, we consider regular column-weight two graphs, which are a class of graphs used for the design of non-binary LDPC codes: for a given target girth g_t, this new instance of the PEG algorithm allows to construct graphs with the minimal size such that a graph of girth g_t exists, which is the best result one might hope for. We illustrate the interest of such minimal constructions with simulation results. Then, we illustrate the usefulness of our algorithm for constructing regular binary LDPC codes that perform well in the error floor region.