In this paper, we analyze Finite Alphabet Iterative Decoders (FAIDs) running on faulty hardware. Under symmetric error models at the message level, we derive the noisy Density Evolution equations, and introduce a new noisy threshold phenomenon (called functional threshold), which accurately characterizes the convergence behavior of LDPC code ensembles under noisy-FAID decoding. The proposed functional threshold is then used to identify FAIDs which are particularly robust to the transient hardware noise. Finite-length simulations are drawn to verify the validity of the asymptotical study.
In this paper, we analyze Finite Alphabet Iterative Decoders (FAIDs) running on faulty hardware. Under symmetric error models at the message level, we derive the noisy Density Evolution equations, and introduce a new noisy threshold phenomenon (called functional threshold), which accurately characterizes the convergence behavior of LDPC code ensembles under noisy-FAID decoding. The proposed functional threshold is then used to identify FAIDs which are particularly robust to the transient hardware noise. Finite-length simulations are drawn to verify the validity of the asymptotical study.
This paper addresses the problem of designing low-density parity check decoders robust to transient errors introduced by faulty hardware. We assume that the faulty hardware introduces errors during the message-passing updates, and we propose a general framework for the definition of the message update faulty functions. Within this framework, we define symmetry conditions for the faulty functions and derive two simple error models used in the analysis. With this analysis, we propose a new interpretation of the functional density evolution threshold introduced by Kameni et al. in the recent literature and show its limitations in the case of highly unreliable hardware. However, we show that under restricted decoder noise conditions, the functional threshold can be used to predict the convergence behavior of finite alphabet iterative decoders (FAIDs) under faulty hardware. In particular, we reveal the existence of robust and nonrobust FAIDs and propose a framework for the design of robust decoders. We finally illustrate robust- and nonrobust-decoder behaviors of finite-length codes using Monte Carlo simulations.
Recently new message passing decoders for LDPC codes, called finite alphabet iterative decoders (FAIDs) were proposed. The messages belong to a finite alphabet and the update functions are simple boolean maps different from the functions used for the belied propagation (BP) decoder. The maps can be chosen using the knowledge of potential trapping sets such that the decoders surpass the BP decoder in the error floor. In this paper, we address the issue of selecting good FAIDs which perform well in the error floor for column weight three codes. We introduce the notion of noisy trapping set which is a generalization based on analyzing the local dynamic behaviour of a given FAID on a trapping set. Using this notion as the core, we provide an iterative greedy algorithm that outputs a set of candidate FAIDs containing potentially good decoders for any given code. To illustrate the appliance of the methodology on several codes, we show that the set of candidate FAIDs contains particularly good FAIDs for different codes with different rates and lengths.
This paper investigates the behavior of the Min-Sum decoder running on noisy devices. Our aim is to evaluate the robustness of the decoder to computation noise caused by the faulty logic in the processing units. This type of noise represents a new source of errors that may occur during the decoding process. To this end, we first introduce probabilistic models for the arithmetic and logic units of the finite-precision min-sum decoder and then carry out the density evolution analysis of the noisy min-sum decoder. We show that, in some particular cases, the noise introduced by the device can help the min-sum decoder to escape from fixed points attractors and may actually result in an increased correction capacity with respect to the noiseless decoder. We also point out a specific threshold phenomenon, referred to as functional threshold, which accurately describes the convergence behavior of noisy decoders. The behavior of the noisy MS is demonstrated in the asymptotic limit of the code length through a noisy version of density evolution and is also verified in the finite-length case by Monte Carlo simulations.
This paper investigates the behavior of the Min-Sum decoder running on noisy devices. The aim is to evaluate the robustness of the decoder in the presence of computation noise, e.g. due to faulty logic in the processing units, which represents a new source of errors that may occur during the decoding process. To this end, we first introduce probabilistic models for the arithmetic and logic units of the the finite-precision Min-Sum decoder, and then carry out the density evolution analysis of the noisy Min-Sum decoder. We show that in some particular cases, the noise introduced by the device can help the Min-Sum decoder to escape from fixed points attractors, and may actually result in an increased correction capacity with respect to the noiseless decoder. We also reveal the existence of a specific threshold phenomenon, referred to as functional threshold. The behavior of the noisy decoder is demonstrated in the asymptotic limit of the code-length -- by using "noisy" density evolution equations -- and it is also verified in the finite-length case by Monte-Carlo simulation.
We introduce a new paradigm for finite precision iterative decoding on low-density parity-check codes over the binary symmetric channel. The messages take values from a finite alphabet, and unlike traditional quantized decoders which are quantized versions of the belief propagation (BP) decoder, the proposed finite alphabet iterative decoders (FAIDs) do not propagate quantized probabilities or log-likelihoods and the variable node update functions do not mimic the BP decoder. Rather, the update functions are maps designed using the knowledge of potentially harmful subgraphs that could be present in a given code, thereby rendering these decoders capable of outperforming the BP in the error floor region. On certain column-weight-three codes of practical interest, we show that there exist {FAIDs that surpass the floating-point BP decoder in the error floor region while requiring only three bits of precision for the representation of the messages}. Hence, FAIDs are able to achieve a superior performance at much lower complexity. We also provide a methodology for the selection of FAIDs that is not code-specific, but gives a set of candidate FAIDs containing potentially good decoders in the error floor region for any column-weight-three code. We validate the code generality of our methodology by providing particularly good three-bit precision FAIDs for a variety of codes with different rates and lengths.
The recent renaissance of one particular class of error-correcting codes called low-density parity-check (LDPC) codes has revolutionized the area of communications leading to the so-called field of modern coding theory. At the heart of this theory lies the fact that LDPC codes can be efficiently decoded by an iterative inference algorithm known as belief propagation (BP) which operates on a graphical model of a code. With BP decoding, LDPC codes are able to achieve an exceptionally good error-rate performance as they can asymptotically approach Shannon's capacity. However, LDPC codes under BP decoding suffer from the error floor phenomenon, an abrupt degradation in the error-rate performance of the code in the high signal-to-noise ratio region, which prevents the decoder from achieving very low error-rates. It arises mainly due to the sub-optimality of BP decoding on finite-length loopy graphs. Moreover, the effects of finite precision that stem from hardware realizations of BP decoding can further worsen the error floor phenomenon. Over the past few years, the error floor problem has emerged as one of the most important problems in coding theory with applications now requiring very low error rates and faster processing speeds. Further, addressing the error floor problem while taking finite precision into account in the decoder design has remained a challenge. In this dissertation, we introduce a new paradigm for finite precision iterative decoding of LDPC codes over the binary symmetric channel (BSC). These novel decoders, referred to as finite alphabet iterative decoders (FAIDs), are capable of surpassing the BP in the error floor region at a much lower complexity and memory usage than BP without any compromise in decoding latency. The messages propagated by FAIDs are not quantized probabilities or log-likelihoods, and the variable node update functions do not mimic the BP decoder. Rather, the update functions are simple maps designed to ensure a higher guaranteed error correction capability which improves the error floor performance. We provide a methodology for the design of FAIDs on column-weight-three codes. Using this methodology, we design 3-bit precision FAIDs that can surpass the BP (floating-point) in the error floor region on several column-weight-three codes of practical interest. While the proposed FAIDs are able to outperform the BP decoder with low precision, the analysis of FAIDs still proves to be a difficult issue. Furthermore, their achievable guaranteed error correction capability is still far from what is achievable by the optimal maximum-likelihood (ML) decoding. In order to address these two issues, we propose another novel class of decoders called decimation-enhanced FAIDs for LDPC codes. For this class of decoders, the technique of decimation is incorporated into the variable node update function of FAIDs. Decimation, which involves fixing certain bits of the code to a particular value during decoding, can significantly reduce the number of iterations required to correct a fixed number of errors while maintaining the good performance of a FAID, thereby making such decoders more amenable to analysis. We illustrate this for 3-bit precision FAIDs on column-weight-three codes and provide insights into the analysis of such decoders. We also show how decimation can be used adaptively to further enhance the guaranteed error correction capability of FAIDs that are already good on a given code. The new adaptive decimation scheme proposed has marginally added complexity but can significantly increase the slope of the error floor in the error-rate performance of a particular FAID. On certain high-rate column-weight-three codes of practical interest, we show that adaptive decimation-enhanced FAIDs can achieve a guaranteed error-correction capability that is close to the theoretical limit achieved by ML decoding.