On the hardness of approximating stopping and trapping sets in LDPC codes

Andrew McGregor, Olgica Milenkovic

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We prove that approximating the size of the smallest trapping set in Tanner graphs of linear block codes, and more restrictively, LDPC codes, is NP-hard. The proof techniques rely on reductions from three NP-hard problems, the set cover, minimum three-dimensional matching, and the minimum Hamming distance problem. The ramifications of our findings are that methods used for estimating the height of the error-floor of long LDPC codes, centered around trapping set enumeration, cannot provide accurate worst-case performance predictions.

Original languageEnglish (US)
Title of host publication2007 IEEE Information Theory Workshop, ITW 2007, Proceedings
Pages248-253
Number of pages6
DOIs
StatePublished - Dec 1 2007
Externally publishedYes
Event2007 IEEE Information Theory Workshop, ITW 2007 - Lake Tahoe, CA, United States
Duration: Sep 2 2007Sep 6 2007

Publication series

Name2007 IEEE Information Theory Workshop, ITW 2007, Proceedings

Other

Other2007 IEEE Information Theory Workshop, ITW 2007
CountryUnited States
CityLake Tahoe, CA
Period9/2/079/6/07

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Information Systems
  • Information Systems and Management

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

  • Cite this

    McGregor, A., & Milenkovic, O. (2007). On the hardness of approximating stopping and trapping sets in LDPC codes. In 2007 IEEE Information Theory Workshop, ITW 2007, Proceedings (pp. 248-253). [4313082] (2007 IEEE Information Theory Workshop, ITW 2007, Proceedings). https://doi.org/10.1109/ITW.2007.4313082