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

Thresholds of Absorbing Sets Under Scaled Min-Sum LDPC Decoding

Marco Ferrari, Alessandro Tomasoni, Ramon Marenzi, S. Bellini

Published Jul 12, 2019• 8 citations
Publisher

Abstract

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.

DOI
10.1109/tcomm.2019.2926032

Related papers

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

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

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

Performance bounds for quantized LDPC decoders based on absorbing sets

Homayoon Hatami, David G. M. Mitchell, Daniel J. Costello +1 more

A code-independent performance bound for a given absorbing set is derived for quantized low-density parity-check (LDPC) decoders. The analysis demonstrates that each absorbing set in the Tanner graph imposes a specific lower bound on the frame error rate (FER) of any code containing that absorbing set under a given quantization scheme. This approach is applicable to any message-passing (MP) decoding algorithm and any uniform or non-uniform quantization scheme for LDPC codes. Simulation results using the sum-product algorithm (SPA) provide FERs that are consistent with the obtained bounds. In addition, the bounds demonstrate that the conventional quantized SPA is not capable of achieving very low FERs if the LDPC codes contain certain absorbing sets.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•5 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

Adaptive deactivation and zero-forcing scheme for low-complexity LDPC decoders

Taehyun Kim, Jonghyun Baik, Myeongwoo Lee +1 more

A modified message propagation algorithm is proposed for a low-complexity decoder of low-density parity-check (LDPC) codes, which controls the information propagated from variable and check nodes.The proposed threshold-based node deactivation for variable nodes and zero-forcing scheme for check nodes remarkably reduce decoding complexity required for similar error performance. In the proposed scheme, different thresholds, which are determined from the base matrix of the LDPC codes, are applied for each type of variable node. In addition, thresholds for deactivating variable nodes are increased while the decoding process is operated for a reduction in decoding complexity without early error floor, which is a drawback of the conventional threshold-based deactivation scheme. Simulation results show that the proposed scheme enables normalized min-sum decoders to decode successfully with less complexity than the conventional threshold-based deactivating scheme.

EURASIP Journal on Wireless Communications and Networking•Sep 11, 2017•1 citation
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. 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.
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.
A code-independent performance bound for a given absorbing set is derived for quantized low-density parity-check (LDPC) decoders. The analysis demonstrates that each absorbing set in the Tanner graph imposes a specific lower bound on the frame error rate (FER) of any code containing that absorbing set under a given quantization scheme. This approach is applicable to any message-passing (MP) decoding algorithm and any uniform or non-uniform quantization scheme for LDPC codes. Simulation results using the sum-product algorithm (SPA) provide FERs that are consistent with the obtained bounds. In addition, the bounds demonstrate that the conventional quantized SPA is not capable of achieving very low FERs if the LDPC codes contain certain absorbing sets.
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.
A modified message propagation algorithm is proposed for a low-complexity decoder of low-density parity-check (LDPC) codes, which controls the information propagated from variable and check nodes.The proposed threshold-based node deactivation for variable nodes and zero-forcing scheme for check nodes remarkably reduce decoding complexity required for similar error performance. In the proposed scheme, different thresholds, which are determined from the base matrix of the LDPC codes, are applied for each type of variable node. In addition, thresholds for deactivating variable nodes are increased while the decoding process is operated for a reduction in decoding complexity without early error floor, which is a drawback of the conventional threshold-based deactivation scheme. Simulation results show that the proposed scheme enables normalized min-sum decoders to decode successfully with less complexity than the conventional threshold-based deactivating scheme.