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 Information Theory

Performance of LDPC Codes Under Faulty Iterative Decoding

Lav R. Varshney

Published Jun 21, 2011• 115 citations
Publisher

Abstract

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.

DOI
10.1109/tit.2011.2145870

Related papers

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 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.

arXiv:0806.1215•Jun 6, 2008•0 citations

Performance of LDPC Codes Under Noisy Message-Passing Decoding

Lav R. Varshney

In traditional communication theory, it is assumed that error correcting codes may be decoded with algorithms that perform perfectly. Noise, however, provides a fundamental limit to computation systems just as it does to communication systems. In this work, we investigate the effect of noise in message-passing decoders for low-density parity-check codes. We observe that the concentration of the performance of the decoder around its average performance continues to hold when noise is introduced into message-passing. Given the concentration result, density evolution equations for a simple noisy message-passing decoder are derived. Analytic computation of thresholds shows that performance degrades smoothly as decoder noise increases. Decoding is robust to noise in the decoder.

IEEE Information Theory Workshop (ITW)•Sep 1, 2007•12 citations

Noisy belief propagation decoder

Chu-Hsiang Huang, Yao Li, Lara Dolecek

This paper analyzes the fundamental performance limits of an LDPC Belief Propagation (BP) decoder implemented on noisy hardware and proposes a robust decoder implementation to improve the resilience to hardware errors. Assuming that the effects of hardware noise in various computational units, i.e., variable nodes and check nodes, can be approximated by Gaussian noise, we develop a Gaussian approximate density evolution for noisy BP decoders. By the Gaussian approximate density evolution, we find that zero residual error rate is achievable for noisy BP decoders as long as the message representations are of arbitrarily high precision. Noisy BP decoding thresholds are then derived for various regular LDPC codes. These decoding thresholds determine maximum allowable communication and computation noise for reliable communication. Next, we propose an averaging BP decoder implementation by averaging over the messages in all up-to-date iterations to cancel out the computation noise. Simulation results demonstrate that on noisy hardware, the averaging BP decoder significantly reduces the residual error rates when compared to the nominal BP decoder.

Asilomar Conference on Signals, Systems and Computers (ACSSC)•Nov 1, 2014•3 citations

Design of LDPC Codes Robust to Noisy Message-Passing Decoding

Alla Tarighati, Hamed Farhadi, Farshad Lahouti

We address noisy message-passing decoding of lowdensity parity-check (LDPC) codes over additive white Gaussian noise channels. Message-passing decoders in which certain processing units iteratively exchange messages are common for decoding LDPC codes. The exchanged messages are in general subject to internal noise in hardware implementation of these decoders. We model the internal decoder noise as additive white Gaussian noise (AWGN) degrading exchanged messages. Using Gaussian approximation of the exchanged messages, we perform a two-dimensional density evolution analysis for the noisy LDPC decoder. This makes it possible to track both the mean, and the variance of the exchanged message densities, and hence, to quantify the threshold of the LDPC code in the presence of internal decoder noise. The numerical and simulation results are presented that quantify the performance loss due to the internal decoder noise. To partially compensate this performance loss, we propose a simple method, based on EXIT chart analysis, to design robust irregular LDPC codes. The simulation results indicate that the designed codes can indeed compensate part of the performance loss due to the internal decoder noise.

arXiv:1501.02483•Jan 11, 2015•1 citation

Performance analysis of noisy message-passing decoding of low-density parity-check codes

Alla Tarighati, Hamed Farhadi, Farshad Lahouti

A noisy message-passing decoding scheme isconsidered for low-density parity-check (LDPC) codes overadditive white Gaussian noise (AWGN) channels. The internaldecoder noise is motivated by the quantization noise in digitalimplementations or the intrinsic noise of analog LDPC decoders.We modelled the decoder noise as AWGN on the exchangedmessages in the iterative LDPC decoder. This is shown to renderthe message densities in the noisy LDPC decoder inconsistent.We then invoke Gaussian approximation and formulate a twodimensionaldensity evolution analysis for the noisy LDPCdecoder. This allows for not only tracking the mean, but also thevariance of the message densities, and hence, quantifying thethreshold of the LDPC code. According to the results, a decodernoise of unit variance, increases the threshold for a regular (3,6) code by 1.672dB.

•Jan 1, 2010•6 citations

The capacity of low-density parity-check codes under message-passing decoding

Tom Richardson, Rudiger L. Urbanke

We present a general method for determining the capacity of low-density parity-check (LDPC) codes under message-passing decoding when used over any binary-input memoryless channel with discrete or continuous output alphabets. Transmitting at rates below this capacity, a randomly chosen element of the given ensemble will achieve an arbitrarily small target probability of error with a probability that approaches one exponentially fast in the length of the code. (By concatenating with an appropriate outer code one can achieve a probability of error that approaches zero exponentially fast in the length of the code with arbitrarily small loss in rate.) Conversely, transmitting at rates above this capacity the probability of error is bounded away from zero by a strictly positive constant which is independent of the length of the code and of the number of iterations performed. Our results are based on the observation that the concentration of the performance of the decoder around its average performance, as observed by Luby et al. in the case of a binary-symmetric channel and a binary message-passing algorithm, is a general phenomenon. For the particularly important case of belief-propagation decoders, we provide an effective algorithm to determine the corresponding capacity to any desired degree of accuracy. The ideas presented in this paper are broadly applicable and extensions of the general method to low-density parity-check codes over larger alphabets, turbo codes, and other concatenated coding schemes are outlined.

IEEE Transactions on Information Theory•Jan 1, 2001•3,067 citations
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.
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 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.
In traditional communication theory, it is assumed that error correcting codes may be decoded with algorithms that perform perfectly. Noise, however, provides a fundamental limit to computation systems just as it does to communication systems. In this work, we investigate the effect of noise in message-passing decoders for low-density parity-check codes. We observe that the concentration of the performance of the decoder around its average performance continues to hold when noise is introduced into message-passing. Given the concentration result, density evolution equations for a simple noisy message-passing decoder are derived. Analytic computation of thresholds shows that performance degrades smoothly as decoder noise increases. Decoding is robust to noise in the decoder.
This paper analyzes the fundamental performance limits of an LDPC Belief Propagation (BP) decoder implemented on noisy hardware and proposes a robust decoder implementation to improve the resilience to hardware errors. Assuming that the effects of hardware noise in various computational units, i.e., variable nodes and check nodes, can be approximated by Gaussian noise, we develop a Gaussian approximate density evolution for noisy BP decoders. By the Gaussian approximate density evolution, we find that zero residual error rate is achievable for noisy BP decoders as long as the message representations are of arbitrarily high precision. Noisy BP decoding thresholds are then derived for various regular LDPC codes. These decoding thresholds determine maximum allowable communication and computation noise for reliable communication. Next, we propose an averaging BP decoder implementation by averaging over the messages in all up-to-date iterations to cancel out the computation noise. Simulation results demonstrate that on noisy hardware, the averaging BP decoder significantly reduces the residual error rates when compared to the nominal BP decoder.
We address noisy message-passing decoding of lowdensity parity-check (LDPC) codes over additive white Gaussian noise channels. Message-passing decoders in which certain processing units iteratively exchange messages are common for decoding LDPC codes. The exchanged messages are in general subject to internal noise in hardware implementation of these decoders. We model the internal decoder noise as additive white Gaussian noise (AWGN) degrading exchanged messages. Using Gaussian approximation of the exchanged messages, we perform a two-dimensional density evolution analysis for the noisy LDPC decoder. This makes it possible to track both the mean, and the variance of the exchanged message densities, and hence, to quantify the threshold of the LDPC code in the presence of internal decoder noise. The numerical and simulation results are presented that quantify the performance loss due to the internal decoder noise. To partially compensate this performance loss, we propose a simple method, based on EXIT chart analysis, to design robust irregular LDPC codes. The simulation results indicate that the designed codes can indeed compensate part of the performance loss due to the internal decoder noise.
A noisy message-passing decoding scheme isconsidered for low-density parity-check (LDPC) codes overadditive white Gaussian noise (AWGN) channels. The internaldecoder noise is motivated by the quantization noise in digitalimplementations or the intrinsic noise of analog LDPC decoders.We modelled the decoder noise as AWGN on the exchangedmessages in the iterative LDPC decoder. This is shown to renderthe message densities in the noisy LDPC decoder inconsistent.We then invoke Gaussian approximation and formulate a twodimensionaldensity evolution analysis for the noisy LDPCdecoder. This allows for not only tracking the mean, but also thevariance of the message densities, and hence, quantifying thethreshold of the LDPC code. According to the results, a decodernoise of unit variance, increases the threshold for a regular (3,6) code by 1.672dB.
We present a general method for determining the capacity of low-density parity-check (LDPC) codes under message-passing decoding when used over any binary-input memoryless channel with discrete or continuous output alphabets. Transmitting at rates below this capacity, a randomly chosen element of the given ensemble will achieve an arbitrarily small target probability of error with a probability that approaches one exponentially fast in the length of the code. (By concatenating with an appropriate outer code one can achieve a probability of error that approaches zero exponentially fast in the length of the code with arbitrarily small loss in rate.) Conversely, transmitting at rates above this capacity the probability of error is bounded away from zero by a strictly positive constant which is independent of the length of the code and of the number of iterations performed. Our results are based on the observation that the concentration of the performance of the decoder around its average performance, as observed by Luby et al. in the case of a binary-symmetric channel and a binary message-passing algorithm, is a general phenomenon. For the particularly important case of belief-propagation decoders, we provide an effective algorithm to determine the corresponding capacity to any desired degree of accuracy. The ideas presented in this paper are broadly applicable and extensions of the general method to low-density parity-check codes over larger alphabets, turbo codes, and other concatenated coding schemes are outlined.