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

Absorbing Sets of Generalized LDPC Codes

Marco Ferrari, Alessandro Tomasoni, Luca Barletta, S. Bellini

Published Feb 1, 2018• 1 citation
Publisher

Abstract

In this paper we propose a definition of Absorbing Sets for binary Generalized LDPC (GLDPC) codes.We show that under practical Max-Log iterative decoding, our AS definition enables a local description of the message evolution with the iterations, with a simplified model very similar to the one used for the analysis of Min-Sum LDPC decoding.Accordingly, these ASs exhibit a threshold behavior also in GLDPC codes.

DOI
10.3929/ethz-b-000245076

Related papers

Thresholds of Absorbing Sets Under Scaled Min-Sum LDPC Decoding

Marco Ferrari, Alessandro Tomasoni, Ramon Marenzi +1 more

In this paper, the definition of threshold of elementary absorbing sets is extended to scaled Min-Sum low-density parity-check (LDPC) decoding. Based on the analysis of the behavior of scaled Min-Sum LDPC decoders in the Tanner graph of the absorbing set, it is proven that correct decoding is guaranteed with received channel messages above threshold. A fast algorithm for the threshold computation is derived. Many examples of absorbing sets taken from LDPC codes of various variable node degrees are investigated, and it is shown that all of them can be deactivated with low enough scaling factors.

IEEE Transactions on Communications•Jul 12, 2019•8 citations

Thresholds of Absorbing Sets in Low-Density Parity-Check Codes

Alessandro Tomasoni, S. Bellini, Marco Ferrari

The error floor phenomenon in many low-density parity-check (LDPC) codes is caused by combinatorial objects in their Tanner graph, known as absorbing sets. In this paper, we highlight a threshold behavior for the min-sum decoding algorithm in the graph of an absorbing set with fixed-point representation of messages. For an absorbing set of interest in a binary LDPC code we can compute the threshold, a novel real-valued parameter that is closely related to its harmfulness. We show that absorbing sets with negative thresholds cannot trap the decoder if the dynamic range of the extrinsic messages is large enough. We also prove that, in regular LDPC codes, absorbing sets with negative thresholds exist if the variable node degree is odd. The examples presented in this paper show that odd-column-weight LDPC codes can have many absorbing sets with negative thresholds, but that these absorbing sets do not trap a well-designed decoder. Simulations show a good agreement between the results of the analysis presented in this paper and the performance of practical decoders with fixed-point messages.

arXiv:1401.8168•IEEE Transactions on Communications•Jan 1, 2017•22 citations

Message Flow Analysis in Practical LDPC Decoders for the Interpretation of Absorbing Set Thresholds

Marco Ferrari, Ramon Marenzi, Luca Barletta

Absorbing sets (ASs) cause the error floor phenomenon in many low-density parity-check (LDPC) codes by entrapping iterative decoders. A recent simplified system model for practical min-sum (MS) LDPC decoding predicts that if all variable nodes in an AS have channel messages above a certain threshold, the AS cannot entrap the decoder. The threshold is an AS parameter that depends on its Tanner graph, and is the result of a nonlinear optimization. In this paper, we analyze the messages exchanged in the directed graph (digraph) of the AS during MS decoding while evaluating the AS threshold. By doing this, we unveil the meaning of the threshold value, which is the minimum channel message for which positive feedback loops in the digraph involve all the messages exchanged.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•0 citations

Density Evolution for GLDPC Codes

Alexeev Ivan, Khartov Alexey

In modern communication systems Low-Density Parity Check (LDPC) codes are widely used. It is because of their performance under iterative decoding, hardware-friendly structure and well-known construction methods. For one to construct good LDPC code Density Evolution (DE) can be used, it estimates the decoding threshold, that is it estimates performance of the code. LDPC codes can be further extended to Generalized LDPC (GLDPC) codes, where simple SPC code is replaced with some component code. With more complex structure common DE is no longer correct. This letter presents the upper bound for decoding error and, therefore, an upper bound of a iterative threshold (in dB). It will be shown that the Gaussian approximation gives an upper bound for a decoding error. As one of the results it means that EXIT-charts analysis also gives an upper bound for an iterative threshold for a GLDPC code.

International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON)•Sep 30, 2024•0 citations

Analysis of practical LDPC decoders in tanner graphs with absorbing sets

Marco Ferrari, Alessandro Tomasoni, S. Bellini

Absorbing sets (ASs) cause the error floor phenomenon in many Low-Density Parity-Check (LDPC) codes. A recent, simplified system model for Min-Sum (MS) LDPC decoding [1] predicts that ASs exhibit a threshold behavior: if all variable nodes in an AS have channel messages above the threshold, the AS cannot trap the decoder. The threshold is a real-valued parameter that depends on the topology of the AS, and can be evaluated by a nonlinear optimization. In this paper we describe a simple, fast algorithm for evaluating the AS threshold. Additionally, we show that the algorithm is valid also for scaled-MS decoding. We show with an example that the threshold values under scaled-MS decoding are smaller than under MS decoding. Accordingly, scaling decreases the error floor.

IEEE Information Theory Workshop (ITW)•Nov 1, 2017•3 citations

Trapping and Absorbing Set Enumerators for Protograph-Based Generalized Low-Density Parity-Check Code Ensembles

Emna Ben Yacoub

Generalized low-density parity-check (GLDPC) codes have outstanding performance outperforming the standard low-density parity-check (LDPC) codes. However, the performance of these codes under iterative decoding can be degraded because of the presence of trapping, absorbing and fully absorbing sets in the code Tanner graphs. The (elementary) trapping and (fully) absorbing sets of protograph-based GLDPC codes are studied. The finite-length and asymptotic distributions of (elementary) trapping and (fully) absorbing sets for protograph-based GLDPC code ensembles are derived and evaluated. The asymptotic distributions can be efficiently computed by solving a system of equations. The relative minimum Δ-trapping/(fully) absorbing set size can be directly computed by adding one equation to the system of equations. This is useful for the code design where we can restrict the search to ensembles for which the minimum Δ-trapping and (fully) absorbing set sizes grow linearly with the blocklength. The normalized logarithmic asymptotic distributions of (elementary) trapping and (fully) absorbing sets for an example GLDPC code ensemble are evaluated.

International Symposium on Problems of Redundancy in Information and Control Systems (REDUNDANCY)•Oct 24, 2023•1 citation
In this paper we propose a definition of Absorbing Sets for binary Generalized LDPC (GLDPC) codes.We show that under practical Max-Log iterative decoding, our AS definition enables a local description of the message evolution with the iterations, with a simplified model very similar to the one used for the analysis of Min-Sum LDPC decoding.Accordingly, these ASs exhibit a threshold behavior also in GLDPC codes.
In this paper, the definition of threshold of elementary absorbing sets is extended to scaled Min-Sum low-density parity-check (LDPC) decoding. Based on the analysis of the behavior of scaled Min-Sum LDPC decoders in the Tanner graph of the absorbing set, it is proven that correct decoding is guaranteed with received channel messages above threshold. A fast algorithm for the threshold computation is derived. Many examples of absorbing sets taken from LDPC codes of various variable node degrees are investigated, and it is shown that all of them can be deactivated with low enough scaling factors.
The error floor phenomenon in many low-density parity-check (LDPC) codes is caused by combinatorial objects in their Tanner graph, known as absorbing sets. In this paper, we highlight a threshold behavior for the min-sum decoding algorithm in the graph of an absorbing set with fixed-point representation of messages. For an absorbing set of interest in a binary LDPC code we can compute the threshold, a novel real-valued parameter that is closely related to its harmfulness. We show that absorbing sets with negative thresholds cannot trap the decoder if the dynamic range of the extrinsic messages is large enough. We also prove that, in regular LDPC codes, absorbing sets with negative thresholds exist if the variable node degree is odd. The examples presented in this paper show that odd-column-weight LDPC codes can have many absorbing sets with negative thresholds, but that these absorbing sets do not trap a well-designed decoder. Simulations show a good agreement between the results of the analysis presented in this paper and the performance of practical decoders with fixed-point messages.
Absorbing sets (ASs) cause the error floor phenomenon in many low-density parity-check (LDPC) codes by entrapping iterative decoders. A recent simplified system model for practical min-sum (MS) LDPC decoding predicts that if all variable nodes in an AS have channel messages above a certain threshold, the AS cannot entrap the decoder. The threshold is an AS parameter that depends on its Tanner graph, and is the result of a nonlinear optimization. In this paper, we analyze the messages exchanged in the directed graph (digraph) of the AS during MS decoding while evaluating the AS threshold. By doing this, we unveil the meaning of the threshold value, which is the minimum channel message for which positive feedback loops in the digraph involve all the messages exchanged.
In modern communication systems Low-Density Parity Check (LDPC) codes are widely used. It is because of their performance under iterative decoding, hardware-friendly structure and well-known construction methods. For one to construct good LDPC code Density Evolution (DE) can be used, it estimates the decoding threshold, that is it estimates performance of the code. LDPC codes can be further extended to Generalized LDPC (GLDPC) codes, where simple SPC code is replaced with some component code. With more complex structure common DE is no longer correct. This letter presents the upper bound for decoding error and, therefore, an upper bound of a iterative threshold (in dB). It will be shown that the Gaussian approximation gives an upper bound for a decoding error. As one of the results it means that EXIT-charts analysis also gives an upper bound for an iterative threshold for a GLDPC code.
Absorbing sets (ASs) cause the error floor phenomenon in many Low-Density Parity-Check (LDPC) codes. A recent, simplified system model for Min-Sum (MS) LDPC decoding [1] predicts that ASs exhibit a threshold behavior: if all variable nodes in an AS have channel messages above the threshold, the AS cannot trap the decoder. The threshold is a real-valued parameter that depends on the topology of the AS, and can be evaluated by a nonlinear optimization. In this paper we describe a simple, fast algorithm for evaluating the AS threshold. Additionally, we show that the algorithm is valid also for scaled-MS decoding. We show with an example that the threshold values under scaled-MS decoding are smaller than under MS decoding. Accordingly, scaling decreases the error floor.
Generalized low-density parity-check (GLDPC) codes have outstanding performance outperforming the standard low-density parity-check (LDPC) codes. However, the performance of these codes under iterative decoding can be degraded because of the presence of trapping, absorbing and fully absorbing sets in the code Tanner graphs. The (elementary) trapping and (fully) absorbing sets of protograph-based GLDPC codes are studied. The finite-length and asymptotic distributions of (elementary) trapping and (fully) absorbing sets for protograph-based GLDPC code ensembles are derived and evaluated. The asymptotic distributions can be efficiently computed by solving a system of equations. The relative minimum Δ-trapping/(fully) absorbing set size can be directly computed by adding one equation to the system of equations. This is useful for the code design where we can restrict the search to ensembles for which the minimum Δ-trapping and (fully) absorbing set sizes grow linearly with the blocklength. The normalized logarithmic asymptotic distributions of (elementary) trapping and (fully) absorbing sets for an example GLDPC code ensemble are evaluated.