IEEE International Symposium on Information Theory (ISIT)

Exhaustive search for small fully absorbing sets and the corresponding low error-floor decoder

Gyu Bum Kyung, Chih-Chun Wang

Published Jun 1, 2010• 24 citations

Abstract

This work provides an exhaustive search algorithm for finding small fully absorbing sets (FASs) of arbitrary low-density parity-check (LDPC) codes. In particular, given any LDPC code, the problem of finding all FASs of size less than t is formulated as an integer programming problem, for which a new branch-&-bound algorithm is devised. New node selection and the tree-trimming mechanisms are designed to further enhance the efficiency of the algorithm. The proposed algorithm is capable of finding all FASs of size ≤ 11 with no larger than 2 induced odd-degree check nodes for LDPC codes of length ≤ 1000. The resulting exhaustive list of small FASs is then used to devise a new post-processing decoder. Numerical results show that by taking advantage of the exhaustive list of small FASs, the proposed decoder significantly lowers the error floor for codes of practical lengths and outperforms the state-of-the-art low-error-floor decoders.

DOI: 10.1109/isit.2010.5513611

Related papers

Finding the Exhaustive List of Small Fully Absorbing Sets and Designing the Corresponding Low Error-Floor Decoder

Gyu Bum Kyung, Chih-Chun Wang

This work provides an efficient exhaustive search algorithm for finding all small fully absorbing sets (FASs) of any arbitrary low-density parity-check (LDPC) code. The proposed algorithm is based on the branch-&-bound principle for solving NP-complete problems. In particular, given any LDPC code, the problem of finding all FASs of size less than t is formulated as an integer programming problem, for which a new branch-&-bound algorithm is devised with new node selection and tree-trimming mechanisms. The resulting algorithm is capable of finding all FASs of size <; 7 for LDPC codes of length <; 1000. When limiting the FASs of interest to those with the number of violated parity-check nodes <; 3, the proposed algorithm is capable of finding all such FASs of size <; 14 for LDPC codes of lengths <; 1000. The resulting exhaustive list of small FASs is then used to devise a new efficient post-processing low-error floor LDPC decoder. The numerical results show that by exploiting the exhaustive list of small FASs, the proposed post-processing decoder can significantly lower the error-floor performance of a given LDPC code. For various example codes of length <; 3000, the proposed post-processing decoder lowers the error floor by a couple of orders of magnitude when compared to the standard belief propagation decoder and by an order of magnitude when compared to other existing low error-floor decoders.

IEEE Transactions on CommunicationsJun 1, 201242 citations

Efficient Algorithms to Find All Small Error-Prone Substructures in LDPC Codes

Xiaojie Zhang, Paul H. Siegel

Exhaustively enumerating all small error-prone sub structures in arbitrary, finite-length low-density parity-check (LDPC) codes has been proven to be NP-complete. In this paper, we present two exhaustive search algorithms to find such small error-prone substructures of an arbitrary LDPC code given its parity-check matrix. One algorithm is guaranteed to find all error-prone substructures including stopping sets, trapping sets, and absorbing sets, which have no more than αmaxvariable nodes and up to bmaxinduced odd-degree neighboring check nodes. The other algorithm is specially designed to find fully absorbing sets (FAS). Numerical results show that both of our proposed algorithms are more efficient in terms of execution time than another recently proposed exhaustive search algorithm [13]. Moreover, by properly initialization of the algorithm, the efficiency can be further improved for quasi-cyclic (QC) codes.

GlobecomDec 1, 201123 citations

Finding All Small Error-Prone Substructures in LDPC Codes

Chih-Chun Wang, Sanjeev R. Kulkarni, H. Vincent Poor

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 lengthsnap 500. By exploiting the sparse connectivity of LDPC codes, the stopping sets of sizeles13and the trapping sets of sizeles11can be exhaustively enumerated. The central theorem behind the proposed algorithm is a new provably tightupperboundon 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 findinglowerboundsof 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.

IEEE Transactions on Information TheoryApr 22, 200958 citations

Exhausting Error-Prone Patterns in LDPC Codes

Chih-Chun Wang, Sanjeev R. Kulkarni, H. Vincent Poor

It is proved in this work that exhaustively determining bad patterns in arbitrary, finite low-density parity-check (LDPC) codes, including stopping sets for binary erasure channels (BECs) and trapping sets (also known as near-codewords) for general memoryless symmetric channels, is an NP-complete problem, and efficient algorithms are provided for codes of practical short lengths n~=500. By exploiting the sparse connectivity of LDPC codes, the stopping sets of size <=13 and the trapping sets of size <=11 can be efficiently exhaustively determined for the first time, and the resulting exhaustive list is of great importance for code analysis and finite code optimization. The featured tree-based narrowing search distinguishes this algorithm from existing ones for which inexhaustive methods are employed. One important byproduct is a pair of upper bounds on the bit-error rate (BER) & frame-error rate (FER) iterative decoding performance of arbitrary codes over BECs that can be evaluated for any value of the erasure probability, including both the waterfall and the error floor regions. The tightness of these upper bounds and the exhaustion capability of the proposed algorithm are proved when combining an optimal leaf-finding module with the tree-based search. These upper bounds also provide a worst-case-performance guarantee which is crucial to optimizing LDPC codes for extremely low error rate applications, e.g., optical/satellite communications. Extensive numerical experiments are conducted that include both randomly and algebraically constructed LDPC codes, the results of which demonstrate the superior efficiency of the exhaustion algorithm and its significant value for finite length code optimization.

arXiv:cs/0609046Sep 11, 200641 citations

Efficient Algorithm for Finding Dominant Trapping Sets of LDPC Codes

Mehdi Karimi, Amir H. Banihashemi

This paper presents an efficient algorithm for finding the dominant trapping sets of a low-density parity-check (LDPC) code. The algorithm can be used to estimate the error floor of LDPC codes or as a tool to design LDPC codes with low error floors. For regular codes, the algorithm is initiated with a set of short cycles as the input. For irregular codes, in addition to short cycles, variable nodes with low degree and cycles with low approximate cycle extrinsic message degree (ACE) are also used as the initial inputs. The initial inputs are then expanded recursively to dominant trapping sets of increasing size. At the core of the algorithm lies the analysis of the graphical structure of dominant trapping sets and the relationship of such structures to short cycles, low-degree variable nodes, and cycles with low ACE. The algorithm is universal in the sense that it can be used for an arbitrary graph and that it can be tailored to find a variety of graphical objects, such as absorbing sets and Zyablov-Pinsker trapping sets, known to dominate the performance of LDPC codes in the error floor region over different channels and for different iterative decoding algorithms. Simulation results on several LDPC codes demonstrate the accuracy and efficiency of the proposed algorithm. In particular, the algorithm is significantly faster than the existing search algorithms for dominant trapping sets.

IEEE Transactions on Information TheoryAug 3, 2012107 citations

An Efficient Algorithm for Finding Dominant Trapping Sets of LDPC Codes

Karimi, Mehdi, Amir H. Banihashemi

This paper presents an efficient algorithm for finding the dominant trapping sets of a low-density parity-check (LDPC) code. The algorithm can be used to estimate the error floor of LDPC codes or to be part of the apparatus to design LDPC codes with low error floors. For regular codes, the algorithm is initiated with a set of short cycles as the input. For irregular codes, in addition to short cycles, variable nodes with low degree and cycles with low approximate cycle extrinsic message degree (ACE) are also used as the initial inputs. The initial inputs are then expanded recursively to dominant trapping sets of increasing size. At the core of the algorithm lies the analysis of the graphical structure of dominant trapping sets and the relationship of such structures to short cycles, low-degree variable nodes and cycles with low ACE. The algorithm is universal in the sense that it can be used for an arbitrary graph and that it can be tailored to find other graphical objects, such as absorbing sets and Zyablov-Pinsker (ZP) trapping sets, known to dominate the performance of LDPC codes in the error floor region over different channels and for different iterative decoding algorithms. Simulation results on several LDPC codes demonstrate the accuracy and efficiency of the proposed algorithm. In particular, the algorithm is significantly faster than the existing search algorithms for dominant trapping sets.

arXiv:1108.4478Aug 23, 20115 citations