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

Nithin Raveendran, David Declercq, Bane Vasic

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


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.

Original languageEnglish (US)
Article number9072180
Pages (from-to)3984-3995
Number of pages12
JournalIEEE Transactions on Communications
Issue number7
StatePublished - Jul 2020


  • Error floor computation
  • Iterative decoding
  • Iterative decoding failures
  • LDPC codes
  • Trapping set

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'A Sub-Graph Expansion-Contraction Method for Error Floor Computation'. Together they form a unique fingerprint.

Cite this