IEEE Transactions on Communications

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

Gyu Bum Kyung, Chih-Chun Wang

Published Jun 1, 2012• 42 citations

Abstract

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.

DOI: 10.1109/tcomm.2012.042712.100672

Related papers

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

Gyu Bum Kyung, Chih-Chun Wang

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.

IEEE International Symposium on Information Theory (ISIT)Jun 1, 201024 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

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

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

Lowering LDPC Error Floors by Postprocessing

Zhengya Zhang, Lara Dolecek, Borivoje Nikolić +2 more

A class of combinatorial structures, called absorbing sets, strongly influences the performance of low-density parity-check (LDPC) decoders at low error rates. Past experiments have shown that a class of (8,8) absorbing sets determines the error floor performance of the (2048,1723) Reed-Solomon based LDPC code (RS-LDPC). A postprocessing approach is formulated to exploit the structure of the absorbing set by biasing the reliabilities of selected messages in a message-passing decoder. The approach converges quickly and can be efficiently implemented with minimal overhead. Hardware emulation of the decoder with postprocessing shows more than two orders of magnitude improvement in the very low bit error rate performance and error- floor-free operation below a BER of 10-12.

GlobecomJan 1, 200885 citations

An Efficient Algorithm to Find All Small-Size Stopping Sets of Low-Density Parity-Check Matrices

Eirik Rosnes, Øyvind Ytrehus

In this work, we introduce an efficient algorithm to find all stopping sets, of size less than some threshold, of a fixed low-density parity-check (LDPC) matrix. The solution is inspired by the algorithm proposed by Rosnes and Ytrehus in 2005 to find an exhaustive list of all small-size turbo stopping sets in a turbo code. The efficiency of the proposed algorithm is demonstrated by several numerical examples. For instance, we have applied the algorithm to the well-known (3, 5)-regular (155, 64) Tanner code and found all stopping sets of size at most 18 in about 1 min on a standard desktop computer. Also, we have verified that the minimum stopping set size of the (4896, 2474) Ramanujan-Margulis code is indeed 24, and that the corresponding multiplicity is exactly 204. Furthermore, we have applied the algorithm to the IEEE 802.16e LDPC codes and determined the minimum stopping set size and the corresponding multiplicity exactly for these codes. Finally, as an application, we present a greedy algorithm to find a small number of redundant parity checks to add to the original parity-check matrix in order to remove all stopping sets in the corresponding Tanner graph of size less than the minimum distance. An extensive case study of the (155, 64) Tanner code illustrates the usefulness of the algorithm, and we present a 110 times 155 redundant parity-check matrix for this code with no stopping sets of size less than the minimum distance. Simulation results of iterative decoding on the binary erasure channel show performance improvements for low-to-medium erasure probabilities when this redundant parity-check matrix is used for decoding.

IEEE Transactions on Information TheoryAug 24, 200963 citations