Theoretical Bounds for the Size of Elementary Trapping Sets by Graph Theory Methods

Elementary trapping sets (ETSs) are the principal culprits for the performance of LDPC codes in the error floor region. Due to their large quantity, intricate structures, and high computational complexity, determining how to eliminate dominant ETSs in the design of LDPC codes has become a critical issue in improving error floor behavior. In this paper, we address this problem by avoiding particular theta graphs <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(\theta(1,2,2)$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\theta(2,2,2))$</tex> in the Tanner graph to eliminate specific ETSs. These can be characterized by a pivotal tool in graph theory - Turán numbers. Theoretically, we derive the exact Turán number for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\theta(1,2,2)$</tex> and demonstrate that all <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(a, b)$</tex>-ETSs in a Tanner graph with variable-reaular degree <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$d_{L}(v)=\gamma$</tex> must satisfy the inequality <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$b\geq a\gamma-\frac{1}{2}a^{2}$</tex>. This result improves the lower bound previously obtained by Amirzade when the girth is 6. For girth 8, by constraining the relationship between any two 8-cycles in the Tanner graph, we establish a similar inequality <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$b\geq a\gamma-\frac{a(\sqrt{8a-7}-1)}{2}$</tex>. Our simulation results indicate that codes designed with these considerations exhibit improved performance and a lower error floor over additive white Gaussian noise channels.