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

IEEE International Symposium on Information Theory (ISIT)

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

Marco Ferrari, Ramon Marenzi, Luca Barletta

Published Jun 1, 2020• 0 citations
Publisher

Abstract

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.

DOI
10.1109/isit44484.2020.9174483

Related papers

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

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

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

A Deviation-Based Conditional Upper Bound on the Error Floor Performance for Min-Sum Decoding of Short LDPC Codes

Eric T. Psota, Jȩdrzej Kowalczuk, Lance C. Pérez

Conditional upper bounds are given for min-sum decoding of low-density parity-check codes in the error floor region. It is generally thought that absorbing sets, i.e., small collections of variable nodes connected to a relatively small number of unsatisfied check nodes, are the primary source of errors in the error floor region. The conditional upper bounds presented here are based on the assumption that all error floor errors are caused by absorbing sets. In order to bound the probability of error associated with each absorbing set, a directed-edge Tanner graph is used to link absorbing sets to low-weight deviations. These low-weight deviations result when a proportionally large number of nodes within a stopping set belong to an absorbing set contained inside the stopping set. A complete collection of the most problematic absorbing sets, and the minimum deviation weights that result from them, are used to derive a conditional upper bound on the probability of error for min-sum decoding of low-density parity-check codes. Simulation results are given to demonstrate the accuracy of the bound.

IEEE Transactions on Communications•Sep 14, 2012•5 citations

An Absorbing Set Analysis of Quantized LDPC Decoders

Homayoon Hatami

The performance of low-density parity-check (LDPC) codes at high signal-to- noise ratios (SNRs) is known to be limited by the presence of certain sub-graphs that exist in the Tanner graph representation of the code, for example trapping sets and absorbing sets. This dissertation derives a lower bound on the frame error rate (FER) of any LDPC code containing a given problematic sub-graph, assuming a particular iterative message passing (MP) decoder and decoder quantization. A crucial aspect of the lower bound is that it is code-independent, in the sense that it can be derived based only on a problematic sub-graph and then applied to any code containing it. Due to the complexity of evaluating the exact bound, assumptions are proposed to approximate it, from which we can estimate decoder performance. For LDPC codes, the attenuated min-sum algorithm (AMSA) and the offset min- sum algorithm (OMSA) are known to outperform the conventional min-sum algorithm (MSA) at low SNRs, i.e., in the waterfall region of the FER curve. This dis- sertation demonstrates that, for quantized LDPC decoders, the AMSA and OMSA underperform the MSA at high SNRs, i.e., in the error floor region of the FER curve, and that the MSA, AMSA, and OMSA all suffer from a relatively high error floor. Therefore, we introduce a novel modification of the MSA for quantized decoding of LDPC codes, called the threshold attenuated min-sum algorithm (TAMSA) (or the threshold offset min-sum algorithm (TOMSA)) with the aim of outperforming the MSA, AMSA, and OMSA at both low and high SNRs. The new decoding algorithm is designed based on the common assumption that trapping sets are the major cause of the error floor for quantized LDPC decoders, and it is shown to reduce the error probability associated with these problematic graphic objects. The lower bound analysis tool noted above is then used to verify the effectiveness of the new TAMSA (TOMSA) and also to assist in finding its optimum design parameters. We also show that the implementation complexity of the TAMSA (TOMSA) is only slightly higher than that of the AMSA or OMSA. Finally, we extend the lower bound to sliding window (SW) decoding of spatially coupled LDPC (SC-LDPC) codes. Additionally, we show that the performance of the TAMSA (TOMSA) is better than that of the MSA, AMSA, and OMSA for SW.

•Nov 16, 2022•0 citations

Absorbing Sets of Generalized LDPC Codes

Marco Ferrari, Alessandro Tomasoni, Luca Barletta +1 more

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.

•Feb 1, 2018•1 citation
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.
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.
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.
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.
Conditional upper bounds are given for min-sum decoding of low-density parity-check codes in the error floor region. It is generally thought that absorbing sets, i.e., small collections of variable nodes connected to a relatively small number of unsatisfied check nodes, are the primary source of errors in the error floor region. The conditional upper bounds presented here are based on the assumption that all error floor errors are caused by absorbing sets. In order to bound the probability of error associated with each absorbing set, a directed-edge Tanner graph is used to link absorbing sets to low-weight deviations. These low-weight deviations result when a proportionally large number of nodes within a stopping set belong to an absorbing set contained inside the stopping set. A complete collection of the most problematic absorbing sets, and the minimum deviation weights that result from them, are used to derive a conditional upper bound on the probability of error for min-sum decoding of low-density parity-check codes. Simulation results are given to demonstrate the accuracy of the bound.
The performance of low-density parity-check (LDPC) codes at high signal-to- noise ratios (SNRs) is known to be limited by the presence of certain sub-graphs that exist in the Tanner graph representation of the code, for example trapping sets and absorbing sets. This dissertation derives a lower bound on the frame error rate (FER) of any LDPC code containing a given problematic sub-graph, assuming a particular iterative message passing (MP) decoder and decoder quantization. A crucial aspect of the lower bound is that it is code-independent, in the sense that it can be derived based only on a problematic sub-graph and then applied to any code containing it. Due to the complexity of evaluating the exact bound, assumptions are proposed to approximate it, from which we can estimate decoder performance. For LDPC codes, the attenuated min-sum algorithm (AMSA) and the offset min- sum algorithm (OMSA) are known to outperform the conventional min-sum algorithm (MSA) at low SNRs, i.e., in the waterfall region of the FER curve. This dis- sertation demonstrates that, for quantized LDPC decoders, the AMSA and OMSA underperform the MSA at high SNRs, i.e., in the error floor region of the FER curve, and that the MSA, AMSA, and OMSA all suffer from a relatively high error floor. Therefore, we introduce a novel modification of the MSA for quantized decoding of LDPC codes, called the threshold attenuated min-sum algorithm (TAMSA) (or the threshold offset min-sum algorithm (TOMSA)) with the aim of outperforming the MSA, AMSA, and OMSA at both low and high SNRs. The new decoding algorithm is designed based on the common assumption that trapping sets are the major cause of the error floor for quantized LDPC decoders, and it is shown to reduce the error probability associated with these problematic graphic objects. The lower bound analysis tool noted above is then used to verify the effectiveness of the new TAMSA (TOMSA) and also to assist in finding its optimum design parameters. We also show that the implementation complexity of the TAMSA (TOMSA) is only slightly higher than that of the AMSA or OMSA. Finally, we extend the lower bound to sliding window (SW) decoding of spatially coupled LDPC (SC-LDPC) codes. Additionally, we show that the performance of the TAMSA (TOMSA) is better than that of the MSA, AMSA, and OMSA for SW.