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 Conference on Communications

Quantization Effects in Low-Density Parity-Check Decoders

Zhengya Zhang, Lara Dolecek, Martin J. Wainwright, V. Anantharam, Borivoje Nikolić

Published Jun 1, 2007• 45 citations
Publisher

Abstract

A. class of combinatorial structures, called absorbing sets, strongly influences the performance of low-density parity- check (LDPC) decoders. In particular, the quantization scheme strongly affects which absorbing sets dominate in the error-floor region. Absorbing sets may be characterized as weak or strong. They are a characteristic of the parity check matrix of a code. Conventional quantization schemes applied to a (2209,1978) array-based LDPC code can induce low-weight weak absorbing sets and, as a result, elevate the error floor. Adaptive quantization schemes alleviate the effects of weak absorbing sets, and, as a result, only the strong ones dominate the error floor of an optimized decoder implementation. Another benefit of an adaptive quantization scheme is that it performs well even in very few iterations.

DOI
10.1109/icc.2007.1032

Related papers

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

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

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•113 citations

Transactions Papers Design of LDPC Decoders for Improved Low Error Rate Performance: Quantization and Algorithm Choices

Zhengya Zhang, Lara Dolecek, Venkat Anantharam +1 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

•Jan 1, 2009•1 citation

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•85 citations

Absorbing Set Distributions, Quantization and Practical Message Passing Decoders

Behzad Amiri

It is well recognized that low-density parity-check (LDPC) codes can suffer from an error floor when decoded iteratively. This performance degradation is often attributed to the class of objects known as trapping sets. As a subset of the trapping set collection, there exists a class of graphical structures called the absorbing sets. An absorbing set is a combinatorially-defined object; in particular a fully absorbing set is stable under bit-flipping decoding. By construction, there can exist trapping sets that are not stable under such a decoder. As a result, for finite-precision, iterative decoding algorithms used over additive channels, absorbing sets can describe decoding errors more accurately than the broader class of trapping sets. In the first part of this thesis, we compute the normalized logarithmic asymptotic distributions of absorbing sets and fully absorbing sets, including elementary (fully) absorbing sets. We compare distributions of absorbing and trapping sets for representative code parameters of interest, and quantify the (lack of) discrepancies between the two. Good absorbing set properties are implied for known structured LDPC codes, including repeat accumulate codes and protograph-based constructions. Establishing the distribution of fully absorbing sets (especially when the discrepancy with the trapping set distribution is significant) allows one to further refine the estimates of the error rates under bit-flipping and related decoders.To reduce implementation complexity, the messages in a practical message passing decoder are necessarily quantized. Absorbing regions act as "decoding regions" around absorbing sets. In the second part of this thesis, we take a closer look at the interplay between quantization and absorbing regions. We provide a study of a range of quantization choices, the impact of quantization on the candidate absorbing regions, and derive guidelines for practical decoders. We show that, due to the non-linear dynamics of message passing decoders, coarser quantization may in fact perform better than finer quantization. Results of this type of work can be particularly useful in designing high performance decoders for very high-reliability storage systems, such as emerging data storage hard disk and solid state drives.

•Jan 1, 2012•0 citations

Absorbing Sets and Error Floor Performance of the 5G New Radio Code

Masoome Otarinia

Low density parity check (LDPC) codes are a class of error correction codes. A structured class of LDPC codes known as quasi cyclic LDPC (QC-LDPC) codes have been selected for the data channels of the new generation of cellular communication standards known as 5G New Radio (NR). LDPC codes are generally decoded using iterative message passing algorithms that yield performance that is close to capacity. Previous research has shown that iterative decoders are vulnerable to certain combinatorial objects in the code’s structure resulting in an error floor, a typically abrupt change of slope in the frame error rate performance curve. These substructures are called absorbing sets; specifically, elementary absorbing sets are found to be particularly impactful for structured LDPC codes. The main focus of this thesis is investigating the decoder performance curve of the 5G NR code and identifying the error prone elementary absorbing sets that contribute to its error floor. In this thesis, we introduce the 5G NR QC-LDPC code and its characteristics; we talk about the measures taken in the transmitter to improve the code’s performance such as puncturing and shortening. We will see how practical limitations such as finite precision (quantization) of LLR values affects the performance in the error floor. We also devise an algorithm to identify all the (elementary) absorbing sets in the code.

•Nov 16, 2022•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•20 citations
A. class of combinatorial structures, called absorbing sets, strongly influences the performance of low-density parity- check (LDPC) decoders. In particular, the quantization scheme strongly affects which absorbing sets dominate in the error-floor region. Absorbing sets may be characterized as weak or strong. They are a characteristic of the parity check matrix of a code. Conventional quantization schemes applied to a (2209,1978) array-based LDPC code can induce low-weight weak absorbing sets and, as a result, elevate the error floor. Adaptive quantization schemes alleviate the effects of weak absorbing sets, and, as a result, only the strong ones dominate the error floor of an optimized decoder implementation. Another benefit of an adaptive quantization scheme is that it performs well even in very few iterations.
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
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
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.
It is well recognized that low-density parity-check (LDPC) codes can suffer from an error floor when decoded iteratively. This performance degradation is often attributed to the class of objects known as trapping sets. As a subset of the trapping set collection, there exists a class of graphical structures called the absorbing sets. An absorbing set is a combinatorially-defined object; in particular a fully absorbing set is stable under bit-flipping decoding. By construction, there can exist trapping sets that are not stable under such a decoder. As a result, for finite-precision, iterative decoding algorithms used over additive channels, absorbing sets can describe decoding errors more accurately than the broader class of trapping sets. In the first part of this thesis, we compute the normalized logarithmic asymptotic distributions of absorbing sets and fully absorbing sets, including elementary (fully) absorbing sets. We compare distributions of absorbing and trapping sets for representative code parameters of interest, and quantify the (lack of) discrepancies between the two. Good absorbing set properties are implied for known structured LDPC codes, including repeat accumulate codes and protograph-based constructions. Establishing the distribution of fully absorbing sets (especially when the discrepancy with the trapping set distribution is significant) allows one to further refine the estimates of the error rates under bit-flipping and related decoders.To reduce implementation complexity, the messages in a practical message passing decoder are necessarily quantized. Absorbing regions act as "decoding regions" around absorbing sets. In the second part of this thesis, we take a closer look at the interplay between quantization and absorbing regions. We provide a study of a range of quantization choices, the impact of quantization on the candidate absorbing regions, and derive guidelines for practical decoders. We show that, due to the non-linear dynamics of message passing decoders, coarser quantization may in fact perform better than finer quantization. Results of this type of work can be particularly useful in designing high performance decoders for very high-reliability storage systems, such as emerging data storage hard disk and solid state drives.
Low density parity check (LDPC) codes are a class of error correction codes. A structured class of LDPC codes known as quasi cyclic LDPC (QC-LDPC) codes have been selected for the data channels of the new generation of cellular communication standards known as 5G New Radio (NR). LDPC codes are generally decoded using iterative message passing algorithms that yield performance that is close to capacity. Previous research has shown that iterative decoders are vulnerable to certain combinatorial objects in the code’s structure resulting in an error floor, a typically abrupt change of slope in the frame error rate performance curve. These substructures are called absorbing sets; specifically, elementary absorbing sets are found to be particularly impactful for structured LDPC codes. The main focus of this thesis is investigating the decoder performance curve of the 5G NR code and identifying the error prone elementary absorbing sets that contribute to its error floor. In this thesis, we introduce the 5G NR QC-LDPC code and its characteristics; we talk about the measures taken in the transmitter to improve the code’s performance such as puncturing and shortening. We will see how practical limitations such as finite precision (quantization) of LLR values affects the performance in the error floor. We also devise an algorithm to identify all the (elementary) absorbing sets in the code.
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.