Construction of Protograph-Based LDPC Codes With Chordless Short Cycles
Farzane Amirzade, Mohammad‐Reza Sadeghi, Daniel Panario
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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$d_{\min }$ </tex-math></inline-formula> of a code. We provide new analytic lower bounds on <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$d_{\min }$ </tex-math></inline-formula> of LDPC codes with girths 6 and 8 and column weight <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\gamma $ </tex-math></inline-formula> in which the short cycles are all chordless. We prove, analytically, that <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$d_{\min }\geq 2\gamma $ </tex-math></inline-formula> for girth 6 and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$d_{\min }\geq \frac {3(\gamma -1)^{2}}{\gamma \ln \gamma -\gamma +1}$ </tex-math></inline-formula> for girth 8. Comparing these bounds with the existing bound <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\gamma +1$ </tex-math></inline-formula> 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.