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

Involve, A Journal of Mathematics

Renaya Dhingra, Gretchen L. Matthews, Collin McDevitt, Emily McMillon

Published Jan 1, 2026• 0 citations
OpenAlex

Abstract

Absorbing sets are graphical structures that cause iterative decoders to fail. The sets depend on the particular iterative decoding algorithm. In this paper, we consider a variant of the wellstudied Gallager B decoding algorithm for binary low-density parity-check codes. Here, a bit node updates its value according to either the number of or fraction of unsatisfied neighboring check nodes. The traditional Gallager B algorithm is the special case in which half (meaning a fraction of ½) of the check nodes being unsatisfied is required for a bit to change its value. We study absorbing sets in these settings along with the received words which give decoder failure. We determine the how changing the update rules pick up new absorbing sets. This allows for fine-tuning the standard algorithm according to the particular channel or error probability. We also connect these notions to Boolean functions.

Related papers

Failure analysis of two-bit flipping decoding algorithms

Bane V. Vasic, Dung Viet Nguyen

We consider a class of bit flipping algorithms for low-density parity-check codes over the binary symmetric channel in which one additional bit at a variable and check nodes is employed. For these two-bit flipping algorithms, we give and illustrate through examples a recursive procedure for finding all uncorrectable error patters and corresponding induced subgraphs, referred as a trapping set profile. This procedure is used to select a small collection of good algorithms that in a decoding diversity approach, run in parallel or serial, outperform Gallager A/B, min-sum and sum product algorithm in the error floor region.

International Conference on Signal Processing and Communications (SPCOM)•Jul 1, 2014•1 citation

Extremal absorbing sets in low-density parity-check codes

Emily McMillon, Allison Beemer, Christine A. Kelley

Absorbing sets are combinatorial structures in the Tanner graphs of low-density parity-check (LDPC) codes that have been shown to inhibit the high signal-to-noise ratio performance of iterative decoders over many communication channels. Absorbing sets of minimum size are the most likely to cause errors, and thus have been the focus of much research. In this paper, we determine the sizes of absorbing sets that can occur in general and left-regular LDPC code graphs, with emphasis on the range of $ b $ for a given $ a $ for which an $ (a,b) $-absorbing set may exist. We identify certain cases of extremal absorbing sets that are elementary, a particularly harmful class of absorbing sets, and also introduce the notion of minimal absorbing sets which will help in designing absorbing set removal algorithms.

Advances in Mathematics of Communications•Apr 7, 2021•3 citations

Performance evaluation of faulty iterative decoders using absorbing Markov chains

Predrag Ivaniš, Bane V. Vasic, David Declercq

We propose an iterative decoder made of a combination of faulty and perfect logic gates that is capable of correcting more channel errors than its counterpart made completely of perfect logic gates. We present an error probability analysis based on absorbing Markov chains, and explain how the randomness in the check node update function helps a decoder to escape to local minima associated with trapping sets. For the (155, 64) Tanner low-density parity check code, we provide a range of gate failure probabilities for which imperfect decoders perform better.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•4 citations

Improved Bit-Flipping Decoding of Low-Density Parity-Check Codes

N. Miladinovic, M.P.C. Fossorier

In this correspondence, a new method for improving hard-decision bit-flipping decoding of low-density parity-check (LDPC) codes is presented. Bits with a number of unsatisfied check sums larger than a predetermined threshold are flipped with a probability p /spl les/ 1 which is independent of the code considered. The probability p is incremented during decoding according to some rule. With a proper choice of the initial p, the proposed improved bit-flipping (BF) algorithm achieves gain not only in performance, but also in average decoding time for signal-to-noise ratio (SNR) values of interest with respect to p = 1.

IEEE Transactions on Information Theory•Apr 1, 2005•85 citations

An improved decoding algorithm for low-density parity-check codes over the binary erasure channel

Badri N. Vellambi, Faramarz Fekri

This paper presents a new improved decoding algorithm for low-density parity-check (LDPC) codes over the binary erasure channel (BEC). The proposed algorithm combines the fact that a considerable fraction of unsatisfied check nodes are of degree two with the concept of guessing bits to perform simple graph-theoretic manipulations on the Tanner graph. The proposed decoding algorithm has a complexity similar to present improved decoding algorithms [H. Pishro-Nik et al., 2004]. Simulations of codes of very short lengths over BEC reveal the superiority of our algorithm over present improved decoding algorithms for a wide range of bit error rates.

Globecom•Jan 1, 2005•0 citations

Results on the Improved Decoding Algorithm for Low-Density Parity-Check Codes Over the Binary Erasure Channel

Badri N. Vellambi, Faramarz Fekri

In this correspondence, we first investigate some analytical aspects of the recently proposed improved decoding algorithm for low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We derive a necessary and sufficient condition for the improved decoding algorithm to successfully complete decoding when the decoder is initialized to guess a predetermined number of guesses after the standard message-passing terminates at a stopping set. Furthermore, we present improved bounds on the number of bits to be guessed for successful completion of the decoding process when a stopping set is encountered. Under suitable conditions, we derive a lower bound on the number of iterations to be performed for complete decoding of the stopping set. We then present a superior, novel improved decoding algorithm for LDPC codes over the binary erasure channel (BEC). The proposed algorithm combines the observation that a considerable fraction of unsatisfied check nodes in the neighborhood of a stopping set are of degree two, and the concept of guessing bits to perform simple and intuitive graph-theoretic manipulations on the Tanner graph. The proposed decoding algorithm has a complexity similar to previous improved decoding algorithms. Finally, we present simulation results of short-length codes over BEC that demonstrate the superiority of our algorithm over previous improved decoding algorithms for a wide range of bit error rates

IEEE Transactions on Information Theory•Apr 1, 2007•24 citations
Absorbing sets are graphical structures that cause iterative decoders to fail. The sets depend on the particular iterative decoding algorithm. In this paper, we consider a variant of the wellstudied Gallager B decoding algorithm for binary low-density parity-check codes. Here, a bit node updates its value according to either the number of or fraction of unsatisfied neighboring check nodes. The traditional Gallager B algorithm is the special case in which half (meaning a fraction of ½) of the check nodes being unsatisfied is required for a bit to change its value. We study absorbing sets in these settings along with the received words which give decoder failure. We determine the how changing the update rules pick up new absorbing sets. This allows for fine-tuning the standard algorithm according to the particular channel or error probability. We also connect these notions to Boolean functions.
We consider a class of bit flipping algorithms for low-density parity-check codes over the binary symmetric channel in which one additional bit at a variable and check nodes is employed. For these two-bit flipping algorithms, we give and illustrate through examples a recursive procedure for finding all uncorrectable error patters and corresponding induced subgraphs, referred as a trapping set profile. This procedure is used to select a small collection of good algorithms that in a decoding diversity approach, run in parallel or serial, outperform Gallager A/B, min-sum and sum product algorithm in the error floor region.
Absorbing sets are combinatorial structures in the Tanner graphs of low-density parity-check (LDPC) codes that have been shown to inhibit the high signal-to-noise ratio performance of iterative decoders over many communication channels. Absorbing sets of minimum size are the most likely to cause errors, and thus have been the focus of much research. In this paper, we determine the sizes of absorbing sets that can occur in general and left-regular LDPC code graphs, with emphasis on the range of $ b $ for a given $ a $ for which an $ (a,b) $-absorbing set may exist. We identify certain cases of extremal absorbing sets that are elementary, a particularly harmful class of absorbing sets, and also introduce the notion of minimal absorbing sets which will help in designing absorbing set removal algorithms.
We propose an iterative decoder made of a combination of faulty and perfect logic gates that is capable of correcting more channel errors than its counterpart made completely of perfect logic gates. We present an error probability analysis based on absorbing Markov chains, and explain how the randomness in the check node update function helps a decoder to escape to local minima associated with trapping sets. For the (155, 64) Tanner low-density parity check code, we provide a range of gate failure probabilities for which imperfect decoders perform better.
In this correspondence, a new method for improving hard-decision bit-flipping decoding of low-density parity-check (LDPC) codes is presented. Bits with a number of unsatisfied check sums larger than a predetermined threshold are flipped with a probability p /spl les/ 1 which is independent of the code considered. The probability p is incremented during decoding according to some rule. With a proper choice of the initial p, the proposed improved bit-flipping (BF) algorithm achieves gain not only in performance, but also in average decoding time for signal-to-noise ratio (SNR) values of interest with respect to p = 1.
This paper presents a new improved decoding algorithm for low-density parity-check (LDPC) codes over the binary erasure channel (BEC). The proposed algorithm combines the fact that a considerable fraction of unsatisfied check nodes are of degree two with the concept of guessing bits to perform simple graph-theoretic manipulations on the Tanner graph. The proposed decoding algorithm has a complexity similar to present improved decoding algorithms [H. Pishro-Nik et al., 2004]. Simulations of codes of very short lengths over BEC reveal the superiority of our algorithm over present improved decoding algorithms for a wide range of bit error rates.
In this correspondence, we first investigate some analytical aspects of the recently proposed improved decoding algorithm for low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We derive a necessary and sufficient condition for the improved decoding algorithm to successfully complete decoding when the decoder is initialized to guess a predetermined number of guesses after the standard message-passing terminates at a stopping set. Furthermore, we present improved bounds on the number of bits to be guessed for successful completion of the decoding process when a stopping set is encountered. Under suitable conditions, we derive a lower bound on the number of iterations to be performed for complete decoding of the stopping set. We then present a superior, novel improved decoding algorithm for LDPC codes over the binary erasure channel (BEC). The proposed algorithm combines the observation that a considerable fraction of unsatisfied check nodes in the neighborhood of a stopping set are of degree two, and the concept of guessing bits to perform simple and intuitive graph-theoretic manipulations on the Tanner graph. The proposed decoding algorithm has a complexity similar to previous improved decoding algorithms. Finally, we present simulation results of short-length codes over BEC that demonstrate the superiority of our algorithm over previous improved decoding algorithms for a wide range of bit error rates