On the hardness of approximating stopping and trapping sets

Andrew McGregor, Olgica Milenkovic

Research output: Contribution to journalArticle

Abstract

We prove that approximating the size of stopping and trapping sets in Tanner graphs of linear block codes, and more restrictively, the class of low-density parity-check (LDPC) codes, is NP-hard. The ramifications of our findings are that methods used for estimating the height of the error-floor of moderate- and long-length LDPC codes, based on stopping and trapping set enumeration, cannot provide accurate worst-case performance predictions for most codes.

Original languageEnglish (US)
Article number5437429
Pages (from-to)1640-1650
Number of pages11
JournalIEEE Transactions on Information Theory
Volume56
Issue number4
DOIs
StatePublished - Apr 1 2010

Keywords

  • Low-density parity-check (LDPC) codes
  • NP hardness
  • Stopping sets
  • Trapping sets

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint Dive into the research topics of 'On the hardness of approximating stopping and trapping sets'. Together they form a unique fingerprint.

  • Cite this