Finding All Small Error-Prone Substructures in LDPC Codes

Chih-Chun Wang; Sanjeev R. Kulkarni; H Vincent Vincent Poort

doi:10.1109/tit.2009.2015993

Abstract

1 min read

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 n ap 500. By exploiting the sparse connectivity of LDPC codes, the stopping sets of size les 13 and the trapping sets of size les11 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.

Finding All Small Error-Prone Substructures in LDPC Codes

Abstract

Discussion(0)

Related publications

Upper Bounding the Performance of Arbitrary Finite LDPC Codes on Binary Erasure Channels

Finite-Dimensional Bounds on ${\BBZ}_m$ and Binary LDPC Codes With Belief Propagation Decoders

Exhausting Error-Prone Patterns in LDPC Codes

Derandomizing Codes for the Adversarial Wiretap Channel of Type II

GaussianSource Coding Based on P-LDPC Code

Related publications

Article2006
Upper Bounding the Performance of Arbitrary Finite LDPC Codes on Binary Erasure Channels
Article2006

Article2007
Finite-Dimensional Bounds on ${\BBZ}_m$ and Binary LDPC Codes With Belief Propagation Decoders
Article2007

Preprint2006
Exhausting Error-Prone Patterns in LDPC Codes
Preprint2006

Article2025
Derandomizing Codes for the Adversarial Wiretap Channel of Type II
Article2025

Article2023
GaussianSource Coding Based on P-LDPC Code
Article2023