Globecom

Fast Identification of Error-Prone Patterns for LDPC Codes under Message Passing Decoding

Jing Lei, Wen Gao

Published Jan 1, 2008• 4 citations

Abstract

Although density evolution accurately predicts the asymptotic performance of LDPC codes, it provides limited information for codes of short or moderate block length. For this reason, combinatorial methods have been employed to analyze the performance of finite-length LDPC codes under message passing decoding. The error floor phenomenon is a key issue of finite-length effects, which is caused largely by poorly connected subgraphs residing in the LPDC codes structure. Because of the unequal noise immunity of different bit levels, error floors become more pronounced for LDPC-coded high-order modulation. Nevertheless, the enumeration of error-prone patterns that lead to error floors has been proven to be NP-hard, which motivates us to find substitute metrics with manageable complexity. Considering trapping sets always comprise loops of low extrinsic message degree (EMD) and the connectivity of a loop with the residual graph can be characterized by its approximate EMD (ACE), in this paper we propose a fast method to identify loops with low ACE for a given code. In light of this, the vulnerable variable nodes residing on low-ACE loops are judiciously mapped to bit levels benefitting from stronger error protection. As a result, the error floor can be significantly improved at the cost of a minor increase of hardware complexity.

DOI: 10.1109/glocom.2008.ecp.216

Related papers

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

Selective Avoidance of Cycles in Irregular LDPC Code Construction

T. Tian, C.R. Jones, John D. Villasenor +1 more

This letter explains the effect of graph connectivity on error-floor performance of low-density parity-check (LDPC) codes under message-passing decoding. A new metric, called extrinsic message degree (EMD), measures cycle connectivity in bipartite graphs of LDPC codes. Using an easily computed estimate of EMD, we propose a Viterbi-like algorithm that selectively avoids small cycle clusters that are isolated from the rest of the graph. This algorithm is different from conventional girth conditioning by emphasizing the connectivity as well as the length of cycles. The algorithm yields codes with error floors that are orders of magnitude below those of random codes with very small degradation in capacity-approaching capability.

IEEE Transactions on CommunicationsAug 1, 2004396 citations

Analysis of error-prone patterns for LDPC codes under belief propagation decoding

Huanlin Li, Yanyan Cao, Jeffrey C. Dill

Lowering the error floor of LDPC codes is extremely attractive to some systems, such as deep space communication systems and storage systems, which desire very low error rates. The error floor phenomenon of LDPC codes, which is associated with their message passing decoding algorithms, is mainly caused by some unfavorable combinatorial characteristics (or error-prone patterns) of LDPC codes. In this paper, a mathematical analysis method which enables the identification of some significant features of error-prone patterns is presented with the help of the beliefs passed in their decoders. Based on the analysis, an improved decoder is proposed which can effectively deal with the traversable trapping sets and achieve significantly improved error floor performance compared with current decoders. More importantly, this proposed decoder does not require the information of all the possible trapping sets of an individual LDPC code when correcting the error bits in its trapping sets.

IEEE Military Communications Conference (MILCOM)Oct 1, 20101 citation

An efficient algorithm for finding dominant trapping sets of irregular LDPC codes

Mehdi Karimi, Amir H. Banihashemi

This paper presents an efficient algorithm for finding the dominant trapping sets of irregular low-density parity-check (LDPC) codes. The algorithm can be used to estimate the error floor of irregular LDPC codes or to be part of the apparatus to design irregular LDPC codes with low error floors. The algorithm is initiated with a set of short cycles, variable nodes with low degree, and cycles with low approximate cycle extrinsic message degree (ACE), as the input. The input structures are then expanded recursively to dominant trapping sets of increasing size. The algorithm is devised based on the careful inspection 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. In particular, the important role of degree-2 variable nodes in the structure of dominant trapping sets is discussed. 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 International Symposium on Information Theory (ISIT)Jul 1, 201115 citations

Constructing Short-Length Irregular LDPC Codes with Low Error Floor

Xia Zheng, Francis C. M. Lau, Chi Kong Tse

Trapping sets (TSs) are known to cause error floors in regular and irregular low-density parity-check (LDPC) codes. By avoiding major error-contributing TSs during the code construction process, codes with low error floors can effectively be built. In it has been shown that TSs labeled as [w;u] are considered as being equivalent under the automorphism of the graph and are therefore contributing equally to the error floor. However, TSs with the same label [w;u] are not identical in general, particularly for the case of irregular LDPC codes. In this paper, we introduce a parameter e that can identify the number of "distinguishable" cycles in the connected subgraph induced by an elementary trapping set. Further, we propose a code construction algorithm, namely the Progressive-Edge-Growth Approximate-minimum-Cycle-Set-Extrinsic-message-degree (PEG-ACSE) method, that aims to avoid small elementary trapping sets (ETSs), particularly detrimental ETSs. We also develop theorems evaluating the minimum possible ETSs formed by PEG construction algorithms in general. We compare the characteristics of the codes built using the proposed method and those built using PEG-only or PEG-Approximate-minimum-Cycle-Extrinsic-message-degree (PEG-ACE) methods. Results from simulations show that the codes constructed using the proposed PEG-ACSE method produce lower error rates, particularly at the high signal-to-noise (SNR) region, compared with codes constructed using other PEG-based algorithms.

IEEE Transactions on CommunicationsSep 20, 201061 citations