Asilomar Conference on Signals, Systems and Computers (ACSSC)

Achieving flexibility in LDPC code design by absorbing set elimination

Jiajun Zhang, Jiadong Wang, Shayan Garani Srinivasa, Lara Dolecek

Published Nov 1, 2011• 4 citations

Abstract

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.

DOI: 10.1109/acssc.2011.6190087

Related papers

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

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

Towards improved LDPC code designs using absorbing set spectrum properties

Lara Dolecek, Jiadong Wang, Zhengya Zhang

This paper focuses on methods for a systematic modification of the parity check matrix of regular LDPC codes for improved performance in the low BER region (i.e., the error floor). A judicious elimination of dominant absorbing sets strictly improves the absorbing set spectrum and thereby improves the code performance. This absorbing set elimination is accomplished without compromising code properties and parameters such as the girth, node degree, and the structure of the parity check matrix. For a representative class of practical codes we substantiate theoretical analysis with experimental results obtained in the low BER region. Our results demonstrate at least an order of magnitude improvement of the error floor relative to the original code designs. Given that the conventional code parameters remain intact, the new code can easily be implemented on the existing software or hardware platforms employing high-throughput, compact architectures. As such, the proposed approach provides a step towards the improved code design that is compatible with practical implementation constraints.

International Symposium on Turbo Codes and Iterative Information ProcessingSep 1, 201010 citations

Optimized Design of Finite-Length Separable Circulant-Based Spatially-Coupled Codes: An Absorbing Set-Based Analysis

Behzad Amiri, Amirhossein Reisizadehmobarakeh, Homa Esfahanizadeh +2 more

In this paper, we characterize the finite-length performance of separable circulant-based spatially-coupled (SCB-SC) LDPC codes for transmission over the additive white Gaussian noise channel. For a general class of finite-length graph-based codes, it is known that the existence of small absorbing sets causes a performance degradation in the error floor regime. We first present the mathematical conditions for the existence of absorbing sets in binary SCB-SC codes. This analysis enables us to find the exact number of absorbing sets as a function of the design parameters. In particular, our results show that the choice of the cutting vector affects the number of absorbing sets and, therefore, the error floor performance of the code. For a fixed column weight, we find provably optimal cutting vectors that result in the least number of absorbing sets. Furthermore, we extend our analysis to nonbinary SCB-SC codes, where we show that the choice of the cutting vector is not as critical as in the binary case. We provide an algorithm which provably removes the problematic nonbinary absorbing sets from nonbinary SCB-SC codes by informed selection of edge labels. Our simulation results show the superior error floor performance of our designed binary and nonbinary SCB-SC codes compared with binary unstructured and nonbinary quasi-cyclic SC codes available in the open literature.

IEEE Transactions on CommunicationsJan 1, 201621 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