Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Symposium on Turbo Codes and Iterative Information Processing

Towards improved LDPC code designs using absorbing set spectrum properties

Lara Dolecek, Jiadong Wang, Zhengya Zhang

Published Sep 1, 2010• 11 citations
Publisher

Abstract

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.

DOI
10.1109/istc.2010.5613896

Related papers

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, 2011•4 citations

Design of LDPC decoders for improved low error rate performance: quantization and algorithm choices

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

Abstract—Many classes of high-performance low-density parity-check (LDPC) codes are based on parity check matrices composed of permutation submatrices. We describe the design of a parallel-serial decoder architecture that can be used to map any LDPC code with such a structure to a hardware emulation platform. High-throughput emulation allows for the exploration of the low bit-error rate (BER) region and provides statistics of the error traces, which illuminate the causes of the error floors of the (2048, 1723) Reed-Solomon based LDPC (RS-LDPC) code and the (2209, 1978) array-based LDPC code. Two classes of error events are observed: oscillatory behavior and convergence to a class of non-codewords, termed absorbing sets. The influence of absorbing sets can be exacerbated by message quantization and decoder implementation. In particular, quantization and the log-tanh function approximation in sum-product decoders

IEEE Transactions on Communications•Nov 1, 2009•110 citations

Techniques for improving ldpc codes performance

Esa Alghonaim

Low Density Parity Check (LDPC) codes are considered to be one of the best classes of error-correcting codes. This thesis deals with two major issues in LDPC codes: decoder design to enhance error correction performance and efficient decoder implementation. Five techniques have been introduced in this thesis. First, an efficient platform for LDPC code design and performance evaluation is developed. This platform implements parallel simulation algorithms to efficiently evaluate the performance of the proposed algorithms for LDPC decoders and code design. Second, an innovative technique is introduced to improve the performance of LDPC decoding in the error-floor region. Special structures in the code graph, called trapping sets, are considered to be the major source of decoding errors in the error-floor region. The proposed technique is based on eliminating the negative effect of trapping sets during LDPC decoding. As a third contribution, a novel approach to improve the decoder performance and/or throughput is introduced. This approach is based on utilizing LDPC decoder idle times by introducing two queues: one at the decoder input and the other at the decoder output. This architecture enables the decoder to run extra iterations beyond the conventional maximum allowable iterations. The fourth proposed technique reduces the bit error rate of LDPC decoders. This technique is based on tracking the number of failed parity check equations in the intermediate decoding iterations, rather than only relying on the final decoder output (after reaching the maximum number of iterations). The last proposed technique deals with the construction of interconnect efficient fully-parallel LDPC codes with high error correction performance. Fully-parallel implementation is very hard due to the complexity of processing elements interconnections. The proposed technique is based on constructing LDPC codes with less complex interconnections and with low impact on the error correction performance. This goal is achieved by putting a constraint on the maximum connection length between any two processing elements.

•Jan 1, 2008•0 citations

On absorbing sets of structured sparse graph codes

Lara Dolecek

In contrast to the capacity approaching performance of iteratively decoded low-density parity check (LDPC) codes, many practical finite-length LDPC codes exhibit performance degradation, manifested in a so-called error floor. Previous work has linked this phenomenon to the presence of certain combinatorial structures within the Tanner graph representation of the code, termed absorbing sets. Absorbing sets are stable under the bit-flipping operations and have been shown to act as fixed points (¿absorbers¿) for a wider class of iterative decoding algorithms. Codes often possess absorbing sets whose size is smaller than the minimum distance: the smallest absorbing sets are deemed most detrimental culprits behind the error floor. This paper focuses on the elementary combinatorial bounds of the smallest (candidate) absorbing sets. For certain classes of practical codes we demonstrate the tightness of these bounds and show how can the structure of the code and the structure of the absorbing sets be utilized to increase the size of the smallest absorbing sets without compromising other code properties such as the node degrees and the girth. As such, this work provides a step towards a better code design by taking into account the combinatorial nature of fixed points of iterative decoding algorithms.

Information Theory and Applications Workshop (ITA)•Jan 1, 2010•21 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.

Globecom•Jan 1, 2008•82 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.0057•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2011•11 citations
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.
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.
Abstract—Many classes of high-performance low-density parity-check (LDPC) codes are based on parity check matrices composed of permutation submatrices. We describe the design of a parallel-serial decoder architecture that can be used to map any LDPC code with such a structure to a hardware emulation platform. High-throughput emulation allows for the exploration of the low bit-error rate (BER) region and provides statistics of the error traces, which illuminate the causes of the error floors of the (2048, 1723) Reed-Solomon based LDPC (RS-LDPC) code and the (2209, 1978) array-based LDPC code. Two classes of error events are observed: oscillatory behavior and convergence to a class of non-codewords, termed absorbing sets. The influence of absorbing sets can be exacerbated by message quantization and decoder implementation. In particular, quantization and the log-tanh function approximation in sum-product decoders
Low Density Parity Check (LDPC) codes are considered to be one of the best classes of error-correcting codes. This thesis deals with two major issues in LDPC codes: decoder design to enhance error correction performance and efficient decoder implementation. Five techniques have been introduced in this thesis. First, an efficient platform for LDPC code design and performance evaluation is developed. This platform implements parallel simulation algorithms to efficiently evaluate the performance of the proposed algorithms for LDPC decoders and code design. Second, an innovative technique is introduced to improve the performance of LDPC decoding in the error-floor region. Special structures in the code graph, called trapping sets, are considered to be the major source of decoding errors in the error-floor region. The proposed technique is based on eliminating the negative effect of trapping sets during LDPC decoding. As a third contribution, a novel approach to improve the decoder performance and/or throughput is introduced. This approach is based on utilizing LDPC decoder idle times by introducing two queues: one at the decoder input and the other at the decoder output. This architecture enables the decoder to run extra iterations beyond the conventional maximum allowable iterations. The fourth proposed technique reduces the bit error rate of LDPC decoders. This technique is based on tracking the number of failed parity check equations in the intermediate decoding iterations, rather than only relying on the final decoder output (after reaching the maximum number of iterations). The last proposed technique deals with the construction of interconnect efficient fully-parallel LDPC codes with high error correction performance. Fully-parallel implementation is very hard due to the complexity of processing elements interconnections. The proposed technique is based on constructing LDPC codes with less complex interconnections and with low impact on the error correction performance. This goal is achieved by putting a constraint on the maximum connection length between any two processing elements.
In contrast to the capacity approaching performance of iteratively decoded low-density parity check (LDPC) codes, many practical finite-length LDPC codes exhibit performance degradation, manifested in a so-called error floor. Previous work has linked this phenomenon to the presence of certain combinatorial structures within the Tanner graph representation of the code, termed absorbing sets. Absorbing sets are stable under the bit-flipping operations and have been shown to act as fixed points (¿absorbers¿) for a wider class of iterative decoding algorithms. Codes often possess absorbing sets whose size is smaller than the minimum distance: the smallest absorbing sets are deemed most detrimental culprits behind the error floor. This paper focuses on the elementary combinatorial bounds of the smallest (candidate) absorbing sets. For certain classes of practical codes we demonstrate the tightness of these bounds and show how can the structure of the code and the structure of the absorbing sets be utilized to increase the size of the smallest absorbing sets without compromising other code properties such as the node degrees and the girth. As such, this work provides a step towards a better code design by taking into account the combinatorial nature of fixed points of iterative decoding algorithms.
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.
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.