Information Theory and Applications Workshop (ITA)

LDPC absorbing sets, the null space of the cycle consistency matrix, and Tanner's constructions

Jiadong Wang, Lara Dolecek, Richard D. Wesel

Published Feb 1, 2011• 6 citations

Abstract

Dolecek et al. introduced the cycle consistency condition, which is a necessary condition for cycles - and thus the absorbing sets that contain them - to be present in separable circulant-based (SCB) LDPC codes. This paper introduces a cycle consistency matrix (CCM) for each possible absorbing set in an SCB LDPC code. The CCM efficiently enforces the cycle consistency condition for all cycles in a specified absorbing set by spanning its associated binary cycle space. Under certain conditions, a CCM not having full column rank is a necessary and sufficient condition for the LDPC code to contain the absorbing set associated with that CCM. This paper uses the CCM approach to carefully analyze LDPC codes based on the Tanner construction for r = 4 rows of sub-matrices (i.e., Tanner-construction LDPC codes with column weight 4).

DOI: 10.1109/ita.2011.5743618

Related papers

Controlling LDPC Absorbing Sets via the Null Space of the Cycle Consistency Matrix

Jiadong Wang, Lara Dolecek, Richard D. Wesel

Regular LDPC codes tend to have better error-floor behavior than irregular LDPC codes. However, for moderate block lengths and high rates, the error floor remains a concern even for regular LDPC codes. This is especially the case for applications such as memory media that require very low frame error rates (FERs). This paper focuses on a class of regular LDPC codes: separable, circulant-based (SCB) codes. For a specified circulant matrix, SCB codes all share a common mother matrix and include array-based LDPC codes as well as many common quasi-cyclic codes. SCB codes retain standard properties of quasi-cyclic LDPC codes such as girth, code structure, and compatibility with existing high-throughput hardware implementations. This paper introduces a cycle consistency matrix (CCM) for each possible absorbing set in an SCB LDPC code. For an absorbing set to be present in an SCB LDPC code, the associated CCM must not be full column-rank. Using this novel observation, a new code construction approach selects rows and columns from the SCB mother matrix to systematically eliminate dominant absorbing sets by forcing the associated CCMs to be full column-rank. Simulation results demonstrate that the new codes have steeper error-floor slopes and provide at least one order of magnitude of improvement in the low FER region. Identifying absorbing-set-spectrum equivalence classes within the family of SCB codes with a specified circulant matrix significantly reduces the search space of possible code matrices.

International Conference on CommunicationsJun 1, 201120 citations

The Cycle Consistency Matrix Approach to Absorbing Sets in Separable Circulant-Based LDPC Codes

Jiadong Wang, Lara Dolecek, Richard D. Wesel

For low-density parity-check (LDPC) codes operating over additive white Gaussian noise channels and decoded using message-passing decoders with limited precision, absorbing sets have been shown to be a key factor in error floor behavior. Focusing on this scenario, this paper introduces the cycle consistency matrix (CCM) as a powerful analytical tool for characterizing and avoiding absorbing sets in separable circulant-based (SCB) LDPC codes. SCB codes include a wide variety of regular LDPC codes such as array-based LDPC codes as well as many common quasi-cyclic codes. As a consequence of its cycle structure, each potential absorbing set in an SCB LDPC code has a CCM, and an absorbing set can be present in an SCB LDPC code only if the associated CCM has a nontrivial null space. CCM-based analysis can determine the multiplicity of an absorbing set in an SCB code, and CCM-based constructions avoid certain small absorbing sets completely. While these techniques can be applied to an SCB code of any rate, lower rate SCB codes can usually avoid small absorbing sets because of their higher variable-node degree. This paper focuses attention on the high-rate scenario in which the CCM constructions provide the most benefit. Simulation results demonstrate that under limited-precision decoding the new codes have steeper error-floor slopes and can provide one order of magnitude of improvement in the low-frame-error-rate region.

arXiv:1208.6094IEEE Transactions on Information TheoryMar 13, 201345 citations

Absorbing set spectrum approach for practical code design

Jiadong Wang, Lara Dolecek, Zhengya Zhang +1 more

This paper focuses on controlling the absorbing set spectrum for a class of regular LDPC codes known as separable, circulant-based (SCB) codes. For a specified circulant matrix, SCB codes all share a common mother matrix, examples of which are array-based LDPC codes and many common quasi-cyclic codes. SCB codes retain the standard properties of quasi-cyclic LDPC codes such as girth, code structure, and compatibility with efficient decoder implementations. In this paper, we define a cycle consistency matrix (CCM) for each absorbing set of interest in an SCB LDPC code. For an absorbing set to be present in an SCB LDPC code, the associated CCM must not be full column-rank. Our approach selects rows and columns from the SCB mother matrix to systematically eliminate dominant absorbing sets by forcing the associated CCMs to be full column-rank. We use the CCM approach to select rows from the SCB mother matrix to design SCB codes of column weight 5 that avoid all low-weight absorbing sets (4; 8), (5; 9), and (6; 8). Simulation results demonstrate that the newly designed code has a steeper error-floor slope and provides at least one order of magnitude of improvement in the low error rate region as compared to an elementary array-based code.

arXiv:1106.0057IEEE International Symposium on Information Theory (ISIT)Jul 1, 201110 citations

Trapping sets of structured LDPC codes

Qin Huang, Qiuju Diao, Shu Lin +1 more

THIS PAPER IS ELIGIBLE FOR THE STUDENT PAPER AWARD. This paper analyzes trapping set structure of binary regular LDPC codes whose parity-check matrices satisfy the constraint that no two rows (or two columns) have more than one place where they both have non-zero components, which is called row-column (RC) constraint. For a (γ,ρ)-regular LDPC code whose parity-check matrix satisfies the RC-constraint, its Tanner graph contains no (κ, τ) trapping set with size κ ≤ γ and number τ of odd degree check nodes less than γ. For several classes of RC-constrained regular LDPC codes constructed algebraically, we show that their Tanner graphs contain no trapping sets of sizes smaller than their minimum weights.

IEEE International Symposium on Information Theory (ISIT)Jul 1, 201115 citations

Achieving flexibility in LDPC code design by absorbing set elimination

Jiajun Zhang, Jiadong Wang, Shayan Garani Srinivasa +1 more

Low-density parity-check (LDPC) codes are attractive since their performance is known to approach the Shannon limits for suitably large block lengths. However, for moderate block lengths, error floors still jeopardize the performance even of well-designed LDPC codes. Previous work has shown that the error floor of a broad class of LDPC codes is due to certain graphical structures called absorbing sets. Separable, circulant-based (SCB) codes represent a general family of high-performance, hardware-friendly LDPC codes built out of circulants. A recently proposed technique applies row selection and column elimination methods to SCB codes to dramatically decrease error floors by avoiding certain small dominant absorbing sets in a principled way. This paper focuses on improving the greedy column elimination method to achieve greater flexibility in code rate while provably avoiding small dominant absorbing sets. Flexibility and low implementation complexity are therefore possible without sacrificing SCB code performance.

Asilomar Conference on Signals, Systems and Computers (ACSSC)Nov 1, 20114 citations

On the Smallest Absorbing Sets of LDPC Codes From Finite Planes

Haiyang Liu, Yan Li, Lianrong Ma +1 more

Absorbing sets, a class of combinatorial structures of the Tanner graph representation of a low-density parity-check (LDPC) code, are known to influence the performance of the code under message passing iterative decoding. In this paper, we study the smallest absorbing sets of LDPC codes constructed from projective planes and Euclidean planes. The lower bounds on the parameters of smallest absorbing sets given by Dolecek are proven to be tight for these two families of LDPC codes. We also analyze the combinatorial properties of the smallest absorbing sets and give conditions necessary and sufficient for a set of bit nodes in the Tanner graph to be a smallest absorbing set. For LDPC codes from projective planes, we further give a condition necessary and sufficient for a smallest absorbing set to be a fully absorbing set. In addition, we show that these smallest absorbing sets are asymptotically not stable, which may explain to some extent the good performance as well as the low error floor expectation of these two families of LDPC codes.

IEEE Transactions on Information TheoryMar 9, 201211 citations