Girth Characterization of (3,29)-Regular Bipartite Graphs and Their Associated LDPC Codes

Abstract

This paper studies a family of (3,29)-regular bipartite graphs introduced by Tanner for low-density parity-check (LDPC) codes. For a prime p≡1(mod87), the graph has 3p left vertices and 29p right vertices. In the associated LDPC code, the right vertices (there are 29p of them, each of degree 3) serve as the variable nodes, while the left vertices (3p vertices, each of degree 29) serve as the check nodes. Using the Euclidean division algorithm, we completely determine the girth characterization of these graphs. A detailed cycle analysis yields necessary and sufficient conditions for the existence of cycles of lengths 4, 6, 8 and 10, which are translated into polynomial equations over Fp involving a primitive 87th root of unity. By computing integer resultants via the Euclidean division algorithm, we identify the prime sets S6, S8 and S10 for which the girth equals 6, 8 or 10, respectively. The sets are constructed recursively so that no prime associated with a shorter cycle is included in a set corresponding to a longer cycle. For all other admissible primes, the girth attains the maximum possible value of 12. Finally, we construct explicit LDPC codes from these graphs and evaluate their error-correcting performance via extrinsic information transfer (EXIT) charts and additive white Gaussian noise (AWGN) simulations. The results indicate competitive performance in the simulated high-rate setting and suggest potential for high-rate applications.