A Sub-Graph Expansion-Contraction Method for Error Floor Computation

In this paper, we present a computationally efficient method for estimating error floors of low-density parity-check (LDPC) codes over the binary symmetric channel (BSC) without any prior knowledge of its trapping sets (TSs). Given the Tanner graph G of a code, and the decoding algorithm mathcal {D} , the method starts from a list of short cycles in G , and expands each cycle by including its sufficiently large neighborhood in G. Variable nodes of the expanded sub-graphs mathcal {G}_{text{EXP}} are then corrupted exhaustively by all possible error patterns, and decoded by mathcal {D} operating on mathcal {G}_{text{EXP}}. Union of support of the error patterns for which mathcal {D} fails on each mathcal {G}_{text{EXP}} defines a subset of variable nodes that is a TS. The knowledge of the minimal error patterns and their strengths in each TSs is used to compute an estimation of the frame error rate. This estimation represents the contribution of error events localized on TSs, and therefore serves as an accurate estimation of the error floor performance of mathcal {D} at low BSC cross-over probabilities. We also discuss trade-offs between accuracy and computational complexity. Our analysis shows that in some cases the proposed method provides a million-fold improvement in computational complexity over standard Monte-Carlo simulation.