Construction of Protograph-Based LDPC Codes With Chordless Short Cycles

Abstract

There is a concept in graph theory known as a chord which has not been considered before in relation to trapping sets of Tanner graphs. A chord of a cycle is an edge outside the cycle which connects two vertices of that cycle. It is proved that short cycles with a chord are the root of several trapping sets and eliminating them increases the minimum distance$d_{\min }$of a code. We provide new analytic lower bounds on$d_{\min }$of LDPC codes with girths 6 and 8 and column weight$\gamma $in which the short cycles are all chordless. We prove, analytically, that$d_{\min }\geq 2\gamma $for girth 6 and$d_{\min }\geq \frac {3(\gamma -1)^{2}}{\gamma \ln \gamma -\gamma +1}$for girth 8. Comparing these bounds with the existing bound$\gamma +1$for girth-6 LDPC codes shows the positive and significant influence of eliminating these cycles. A method to construct protograph-based LDPC codes with different girths and free of short cycles with a chord is given which is applicable to any type of protographs, simple and multi-edge, regular and irregular. The conditions to remove small trapping sets from the Tanner graph of a multi-edge QC-LDPC code are given. Numerical results indicate that the application of our method to QC-LDPC codes improves existing results.