Finding all small error-prone substructures in LDPC codes

Research output: Contribution to journalArticlepeer-review

43 Scopus citations

Abstract

It is proven in this work that it is NP-complete to exhaustively enumerate small error-prone substructures in arbitrary, finite-length low-density parity-check (LDPC) codes. Two error-prone patterns of interest include stopping sets for binary erasure channels (BECs) and trapping sets for general memoryless symmetric channels. Despite the provable hardness of the problem, this work provides an exhaustive enumeration algorithm that is computationally affordable when applied to codes of practical short lengths ≈500. By exploiting the sparse connectivity of LDPC codes, the stopping sets of size ≤13 and the trapping sets of size ≤ 11 can be exhaustively enumerated. The central theorem behind the proposed algorithm is a new provably tight upper bound on the error rates of iterative decoding over BECs. Based on a tree-pruning technique, this upper bound can be iteratively sharpened until its asymptotic order equals that of the error floor. This feature distinguishes the proposed algorithm from existing non-exhaustive ones that correspond to finding lower bounds of the error floor. The upper bound also provides a worst case performance guarantee that is crucial to optimizing LDPC codes when the target error rate is beyond the reach of Monte Carlo simulation. Numerical experiments on both randomly and algebraically constructed LDPC codes demonstrate the efficiency of the search algorithm and its significant value for finite-length code optimization.

Original languageEnglish (US)
Pages (from-to)1976-1999
Number of pages24
JournalIEEE Transactions on Information Theory
Volume55
Issue number5
DOIs
StatePublished - 2009

All Science Journal Classification (ASJC) codes

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

Keywords

  • Branch-and-bound
  • Error floors
  • Exhaustive search
  • Low-density parity-check (LDPC) codes
  • Stopping distance
  • Stopping/trapping sets
  • Support trees

Fingerprint

Dive into the research topics of 'Finding all small error-prone substructures in LDPC codes'. Together they form a unique fingerprint.

Cite this