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

Information Theory and Applications Workshop (ITA)

Approaching maximum likelihood performance of LDPC codes by stochastic resonance in noisy iterative decoders

Bane V. Vasic, Predrag Ivaniš, David Declercq, Khoa Le

Published Jan 1, 2016• 19 citations
Publisher

Abstract

In the 1960s-70s, Taylor and Kuznetsov obtained a remarkable result that information can be reliably retrieved from a noisy channel even if a decoder is made of noisy components. The results of Vasic and Chilappagari presented at the ITA Workshop ten years ago have revived the interest in decoders made of noisy hardware and since then a number of improvements of the iterative decoders have been made to bring their performance closer to that of their perfect counterparts. However, a common mantra has been that noisy decoders cannot be better than their perfect counterparts. In this talk we report an unexpected phenomenon we have recently discovered - noise can actually improve the error correction process by reducing the probability of decoding error, in some cases by more that two orders of magnitude. This new form of stochastic resonance enables us to use logic gate errors to correct channel errors. This novelty recognizes that the decoder - essentially an iterative minimization of the Bethe free energy on the code graph - can get trapped in local minima, and random perturbations help the decoder to escape from these minima and converge to a correct code-word. In the spirit of Marcus Tullius Cicero's “Clavus clavo eicitur,” (“one nail drives out another”) they operate on the principle: Error errore eicitur” - “one error drives out another.” Crucially, such useful random perturbations require neither additional hardware nor energy, as they are built into the low-powered, noisy hardware itself.

DOI
10.1109/ita.2016.7888185

Related papers

Stochastic resonance in iterative decoding: Message passing and gradient descent bit flipping

Predrag Ivaniš, Srdan S. Brkic, Bane V. Vasic

This paper contains a survey on iterative decoders of low-density parity-check (LDPC) codes made of unreliable logic gates that are capable to provide lower probability of error, when compared to their perfectly reliable counterparts. We have recently shown that the error-floor performance of message-passing decoders can be improved, if randomness that exists in unreliable logic gates is incorporated into decoding deliberately, without any complexity cost. Furthermore, we have shown that controlling the level of unreliability enable us to exploit the stochastic resonance phenomenon, previously observed in theoretical physics, electronic and magnetic systems. In contrary to common belief, we have shown that for a narrow range of gate failure probability the overall decoding performance is dramatically increased. In this paper, we show that the effect of stochastic resonance is even more noticeable for the case of the gradient descent bit-flipping (GDBF) algorithm. This decoder combines the simplest iterative decoding algorithm with gradient descent optimization, making it an attractive solution for a variety of low complexity storage systems, or code-based cryptosystems. In addition, we show that getting the most of the stochastic resonance is essentially a deep learning problem, since setting the levels of unreliability for individual parts of the decoder by a training process is a step toward incorporating the machine learning techniques into design and analysis of iterative decoders of LDPC codes.

International Conference on Advanced Technologies, Systems and Services in Telecommunications (TELSIKS)•Oct 1, 2017•1 citation

Noise-aided gradient descent bit-flipping decoders approaching maximum likelihood decoding

David Declercq, Chris Winstead, Bane V. Vasic +3 more

In the recent literature, the study of iterative LDPC decoders implemented on faulty-hardware has led to the counter-intuitive conclusion that noisy decoders could perform better than their noiseless version. This peculiar behavior has been observed in the finite codeword length regime, where the noise perturbating the decoder dynamics help to escape the attraction of fixed points such as trapping sets. In this paper, we will study two recently introduced LDPC decoders derived from noisy versions of the gradient descent bit-flipping decoder (GDBF). Although the GDBF is known to be a simple decoder with limited error correction capability compared to more powerful softdecision decoders, it has been shown that the introduction of a random perturbation in the decoder could greatly improve the performance results, approaching and even surpassing belief propagation or min-sum based decoders. For both decoders, we evaluate the probability of escaping from a Trapping set, and relate this probability to the parameters of the injected noise distribution, using a Markovian model of the decoder transitions in the state space of errors localized on isolated trapping sets. In a second part of the paper, we present a modified scheduling of our algorithms for the binary symmetric channel, which allows to approach maximum likelihood decoding (MLD) at the cost of a very large number of iterations.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2016•10 citations

Stochastic resonance decoding for quantum LDPC codes

Nithin Raveendran, Priya J. Nadkarni, Shayan Srinivasa Garani +1 more

We introduce a stochastic resonance based decoding paradigm for quantum codes using an error correction circuit made of a combination of noisy and noiseless logic gates. The quantum error correction circuit is based on iterative syndrome decoding of quantum low-density parity check codes, and uses the positive effect of errors in gates to correct errors due to decoherence. We analyze how the proposed stochastic algorithm can escape from short cycle trapping sets present in the dual containing Calderbank, Shor and Steane (CSS) codes. Simulation results show improved performance of the stochastic algorithm over the deterministic decoder.

International Conference on Communications•May 1, 2017•9 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

Improving the Error Floor Performance of LDCP Codes with Better Codes and Better Decoders

Dung Viet Nguyen

Error correcting codes are used in virtually all communication systems to ensure reliable transmission of information. In 1948, Shannon established an upper-bound on the maximum rate at which information can be transmitted reliably over a noisy channel. Reliably transmitting information with a rate close to this theoretical limit, known as the channel capacity, has been the goal of channel coding scientists for the last five decades. The rediscovery of low-density parity-check (LDPC) codes in the 1990s added much-renewed excitement in the coding community. LDPC codes are interesting because they can approach channel capacity under sub-optimum decoding algorithms whose complexity is linear in the code length. Unsurprisingly, LDPC codes quickly attained their popularity in practical applications such as magnetic storage, wireless and optical communications. One, if not the most, important and challenging problem in LDPC code research is the study and analysis of the error floor phenomenon. This phenomenon is described as an abrupt degradation in the frame error rate performance of LDPC codes in the high signal-to-noise ratio region. Error floor is harmful because its presence prevents the LDPC decoder from reaching very low probability of decoding failure, an important requirement for many applications. Not long after the rediscovery of LDPC codes, scientists established that error floor is caused by certain harmful structures, most commonly known as trapping sets, in the Tanner representation of a code. Since then, the study of error floor mostly consists of three major problems: 1) estimating error floor; 2) constructing LDPC codes with low error floor and 3) designing decoders that are less susceptible to error floor. Although some parts of this dissertation can be used as important elements in error floor estimation, our main contributions are a novel method for constructing LDPC codes with low error floor and a novel class of low complexity decoding algorithms that can collectively alleviate error floor. These contributions are summarized as follows. A method to construct LDPC codes with low error floors on the binary symmetric channel is presented. Codes are constructed so that their Tanner graphs are free of certain small trapping sets. These trapping sets are selected from the Trapping Set Ontology for the Gallager A/B decoder. They are selected based on their relative harmfulness for a given decoding algorithm. We evaluate the relative harmfulness of different trapping sets for the sum-product algorithm by using the topological relations among them and by analyzing the decoding failures on one trapping set in the presence or absence of other trapping sets. We apply this method to construct structured LDPC codes. To facilitate the discussion, we give a new description of structured LDPC codes whose parity-check matrices are arrays of permutation matrices. This description uses Latin squares to define a set of permutation matrices that have disjoint support and to derive a simple necessary and sufficient condition for the Tanner graph of a code to be free of four-cycles. A new class of bit flipping algorithms for LDPC codes over the binary symmetric channel is proposed. Compared to the regular (parallel or serial) bit flipping algorithms, the proposed algorithms employ one additional bit at a variable node to represent its "strength." The introduction of this additional bit allows an increase in the guaranteed error correction capability. An additional bit is also employed at a check node to capture information which is beneficial to decoding. A framework for failure analysis and selection of two-bit bit flipping algorithms is provided. The main component of this framework is the (re)definition of trapping sets, which are the most "compact" Tanner graphs that cause decoding failures of an algorithm. A recursive procedure to enumerate trapping sets is described. This procedure is the basis for selecting a collection of algorithms that work well together. It is demonstrated that decoders which employ a properly selected group of the proposed algorithms operating in parallel can offer high speed and low error floor decoding.

•Jan 1, 2012•1 citation

Performance of LDPC Codes Under Faulty Iterative Decoding

Lav R. Varshney

Departing from traditional communication theory where decoding algorithms are assumed to perform without error, a system where noise perturbs both computational devices and communication channels is considered here. This paper studies limits in processing noisy signals with noisy circuits by investigating the effect of noise on standard iterative decoders for low-density parity-check (LDPC) codes. Concentration of decoding performance around its average is shown to hold when noise is introduced into message-passing and local computation. Density evolution equations for simple faulty iterative decoders are derived. In one model, computing nonlinear estimation thresholds shows that performance degrades smoothly as decoder noise increases, but arbitrarily small probability of error is not achievable. Probability of error may be driven to zero in another system model; the decoding threshold again decreases smoothly with decoder noise. As an application of the methods developed, an achievability result for reliable memory systems constructed from unreliable components is provided.

IEEE Transactions on Information Theory•Jun 21, 2011•115 citations
In the 1960s-70s, Taylor and Kuznetsov obtained a remarkable result that information can be reliably retrieved from a noisy channel even if a decoder is made of noisy components. The results of Vasic and Chilappagari presented at the ITA Workshop ten years ago have revived the interest in decoders made of noisy hardware and since then a number of improvements of the iterative decoders have been made to bring their performance closer to that of their perfect counterparts. However, a common mantra has been that noisy decoders cannot be better than their perfect counterparts. In this talk we report an unexpected phenomenon we have recently discovered - noise can actually improve the error correction process by reducing the probability of decoding error, in some cases by more that two orders of magnitude. This new form of stochastic resonance enables us to use logic gate errors to correct channel errors. This novelty recognizes that the decoder - essentially an iterative minimization of the Bethe free energy on the code graph - can get trapped in local minima, and random perturbations help the decoder to escape from these minima and converge to a correct code-word. In the spirit of Marcus Tullius Cicero's “Clavus clavo eicitur,” (“one nail drives out another”) they operate on the principle: Error errore eicitur” - “one error drives out another.” Crucially, such useful random perturbations require neither additional hardware nor energy, as they are built into the low-powered, noisy hardware itself.
This paper contains a survey on iterative decoders of low-density parity-check (LDPC) codes made of unreliable logic gates that are capable to provide lower probability of error, when compared to their perfectly reliable counterparts. We have recently shown that the error-floor performance of message-passing decoders can be improved, if randomness that exists in unreliable logic gates is incorporated into decoding deliberately, without any complexity cost. Furthermore, we have shown that controlling the level of unreliability enable us to exploit the stochastic resonance phenomenon, previously observed in theoretical physics, electronic and magnetic systems. In contrary to common belief, we have shown that for a narrow range of gate failure probability the overall decoding performance is dramatically increased. In this paper, we show that the effect of stochastic resonance is even more noticeable for the case of the gradient descent bit-flipping (GDBF) algorithm. This decoder combines the simplest iterative decoding algorithm with gradient descent optimization, making it an attractive solution for a variety of low complexity storage systems, or code-based cryptosystems. In addition, we show that getting the most of the stochastic resonance is essentially a deep learning problem, since setting the levels of unreliability for individual parts of the decoder by a training process is a step toward incorporating the machine learning techniques into design and analysis of iterative decoders of LDPC codes.
In the recent literature, the study of iterative LDPC decoders implemented on faulty-hardware has led to the counter-intuitive conclusion that noisy decoders could perform better than their noiseless version. This peculiar behavior has been observed in the finite codeword length regime, where the noise perturbating the decoder dynamics help to escape the attraction of fixed points such as trapping sets. In this paper, we will study two recently introduced LDPC decoders derived from noisy versions of the gradient descent bit-flipping decoder (GDBF). Although the GDBF is known to be a simple decoder with limited error correction capability compared to more powerful softdecision decoders, it has been shown that the introduction of a random perturbation in the decoder could greatly improve the performance results, approaching and even surpassing belief propagation or min-sum based decoders. For both decoders, we evaluate the probability of escaping from a Trapping set, and relate this probability to the parameters of the injected noise distribution, using a Markovian model of the decoder transitions in the state space of errors localized on isolated trapping sets. In a second part of the paper, we present a modified scheduling of our algorithms for the binary symmetric channel, which allows to approach maximum likelihood decoding (MLD) at the cost of a very large number of iterations.
We introduce a stochastic resonance based decoding paradigm for quantum codes using an error correction circuit made of a combination of noisy and noiseless logic gates. The quantum error correction circuit is based on iterative syndrome decoding of quantum low-density parity check codes, and uses the positive effect of errors in gates to correct errors due to decoherence. We analyze how the proposed stochastic algorithm can escape from short cycle trapping sets present in the dual containing Calderbank, Shor and Steane (CSS) codes. Simulation results show improved performance of the stochastic algorithm over the deterministic decoder.
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.
Error correcting codes are used in virtually all communication systems to ensure reliable transmission of information. In 1948, Shannon established an upper-bound on the maximum rate at which information can be transmitted reliably over a noisy channel. Reliably transmitting information with a rate close to this theoretical limit, known as the channel capacity, has been the goal of channel coding scientists for the last five decades. The rediscovery of low-density parity-check (LDPC) codes in the 1990s added much-renewed excitement in the coding community. LDPC codes are interesting because they can approach channel capacity under sub-optimum decoding algorithms whose complexity is linear in the code length. Unsurprisingly, LDPC codes quickly attained their popularity in practical applications such as magnetic storage, wireless and optical communications. One, if not the most, important and challenging problem in LDPC code research is the study and analysis of the error floor phenomenon. This phenomenon is described as an abrupt degradation in the frame error rate performance of LDPC codes in the high signal-to-noise ratio region. Error floor is harmful because its presence prevents the LDPC decoder from reaching very low probability of decoding failure, an important requirement for many applications. Not long after the rediscovery of LDPC codes, scientists established that error floor is caused by certain harmful structures, most commonly known as trapping sets, in the Tanner representation of a code. Since then, the study of error floor mostly consists of three major problems: 1) estimating error floor; 2) constructing LDPC codes with low error floor and 3) designing decoders that are less susceptible to error floor. Although some parts of this dissertation can be used as important elements in error floor estimation, our main contributions are a novel method for constructing LDPC codes with low error floor and a novel class of low complexity decoding algorithms that can collectively alleviate error floor. These contributions are summarized as follows. A method to construct LDPC codes with low error floors on the binary symmetric channel is presented. Codes are constructed so that their Tanner graphs are free of certain small trapping sets. These trapping sets are selected from the Trapping Set Ontology for the Gallager A/B decoder. They are selected based on their relative harmfulness for a given decoding algorithm. We evaluate the relative harmfulness of different trapping sets for the sum-product algorithm by using the topological relations among them and by analyzing the decoding failures on one trapping set in the presence or absence of other trapping sets. We apply this method to construct structured LDPC codes. To facilitate the discussion, we give a new description of structured LDPC codes whose parity-check matrices are arrays of permutation matrices. This description uses Latin squares to define a set of permutation matrices that have disjoint support and to derive a simple necessary and sufficient condition for the Tanner graph of a code to be free of four-cycles. A new class of bit flipping algorithms for LDPC codes over the binary symmetric channel is proposed. Compared to the regular (parallel or serial) bit flipping algorithms, the proposed algorithms employ one additional bit at a variable node to represent its "strength." The introduction of this additional bit allows an increase in the guaranteed error correction capability. An additional bit is also employed at a check node to capture information which is beneficial to decoding. A framework for failure analysis and selection of two-bit bit flipping algorithms is provided. The main component of this framework is the (re)definition of trapping sets, which are the most "compact" Tanner graphs that cause decoding failures of an algorithm. A recursive procedure to enumerate trapping sets is described. This procedure is the basis for selecting a collection of algorithms that work well together. It is demonstrated that decoders which employ a properly selected group of the proposed algorithms operating in parallel can offer high speed and low error floor decoding.
Departing from traditional communication theory where decoding algorithms are assumed to perform without error, a system where noise perturbs both computational devices and communication channels is considered here. This paper studies limits in processing noisy signals with noisy circuits by investigating the effect of noise on standard iterative decoders for low-density parity-check (LDPC) codes. Concentration of decoding performance around its average is shown to hold when noise is introduced into message-passing and local computation. Density evolution equations for simple faulty iterative decoders are derived. In one model, computing nonlinear estimation thresholds shows that performance degrades smoothly as decoder noise increases, but arbitrarily small probability of error is not achievable. Probability of error may be driven to zero in another system model; the decoding threshold again decreases smoothly with decoder noise. As an application of the methods developed, an achievability result for reliable memory systems constructed from unreliable components is provided.