The performance of a belief propagation decoder for low-density parity-check codes is limited by the presence of trapping sets in the code’s graph. This leads to an error floor at higher signal-to-noise ratios. We propose the use of an augmented decoder which operates by iteratively decoding on a set of graphs which have a subset of repeated check nodes. We compare the augmented decoder to other modified belief propagation decoders that have been presented in the literature. We show that for all the codes considered, the augmented decoder yields the best frame error rate in the error floor region.
The performance of a belief propagation decoder for low-density parity-check codes is limited by the presence of trapping sets in the code’s graph. This leads to an error floor at higher signal-to-noise ratios. We propose the use of an augmented decoder which operates by iteratively decoding on a set of graphs which have a subset of repeated check nodes. We compare the augmented decoder to other modified belief propagation decoders that have been presented in the literature. We show that for all the codes considered, the augmented decoder yields the best frame error rate in the error floor region.
Quantum low-density parity-check codes can be decoded using a syndrome based GF(4) belief propagation decoder (where GF denotes Galois field). However, the performance of this decoder is limited both by unavoidable 4-cycles in the code's factor graph and the degenerate nature of quantum errors. For the subclass of CSS codes, the number of 4-cycles can be reduced by breaking an error into an X and Z component and decoding each with an individual GF(2) based decoder. However, this comes at the expense of ignoring potential correlations between these two error components. We present a number of modified belief propagation decoders that address these issues. We propose a GF(2) based decoder for CSS codes that reintroduces error correlations by reattempting decoding with adjusted error probabilities. We also propose the use of an augmented decoder, which has previously been suggested for classical binary low-density parity-check codes. This decoder iteratively reattempts decoding on factor graphs that have a subset of their check nodes duplicated. The augmented decoder can be based on a GF(4) decoder for any code, a GF(2) decoder for CSS code, or even a supernode decoder for a dual-containing CSS code. For CSS codes, we further propose a GF(2) based decoder that combines the augmented decoder with error probability adjustment. We demonstrate the performance of these new decoders on a range of different codes, showing that they perform favorably compared to other decoders presented in literature.
Abstract Quantum error-correction codes are immeasurable resources for quantum computing and quantum communication. However, the existing decoders are generally incapable of checking node duplication of belief propagation (BP) on quantum low-density parity check (QLDPC) codes. Based on the probability theory in the machine learning, mathematical statistics and topological structure, a GF(4) (the Galois field is abbreviated as GF) augmented model BP decoder with Tanner graph is designed. The problem of repeated check nodes can be solved by this decoder. In simulation, when the random perturbation strength p=0.0115–0.0116 and number of attempts N = 60–70, the highest decoding efficiency of the augmented model BP decoder is obtained, and the low-loss frame error rate (FER) decreases to 7.1975 ×10−5. Hence, we design a novel augmented model decoder to compare the relationship between GF(2) and GF(4) for quantum code [[450,200]] on the depolarization channel. It can be verified that the proposed decoder provides the widely application range, and the decoding performance is better in QLDPC codes.
Many classes of high-performance Low-density parity check codes are based on parity check matrices composed of permutation sub matrices. The emulation-simulation framework further allows the algorithm and implementation to be iteratively redefined to improve the error floor performance of message passing decoder. Log-Like hood-Ratio (LLR) based Belief-Propagation (BP) algorithm is presented for Low Density Parity Check codes. Numerically accurate representation of check node update computation used in LLR-BP decoding is described. The implementation of Sum-Product algorithm (SPA) within Low Density Parity Check Code (LDPC) decoder is described in this paper and the correction term is used to improve the decoding performance of min-sum algorithm (MSA). Quantization and log-tanh function approximation in sum-product decoder strongly affect which absorbing set dominates in error floor region. For LDPC decoder, bit error rate (BER) decreases with increase in the signal to noise ratio.
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.
Abstract—In this paper, we focus on the Generalized Belief Propagation (GBP) algorithm to solve trapping sets in Low-Density Parity-Check (LDPC) codes. Trapping sets are topo-logical structures in Tanner graphs of LDPC codes that are not correctly decoded by Belief Propagation (BP), leading to exhibit an error-floor in the Bit-Error Rate (BER). Stemming from statistical physics of spin glasses, GBP consists in passing messages between clusters of Tanner graph nodes in another graph called the region-graph. Here, we introduce a specific clustering of nodes, based on a novel local loopfree principle, that breaks trapping sets such that the resulting region-graph is locally loopfree. We then construct a hybrid decoder made of BP and GBP that proves to be a powerful decoder as it clearly improves the BER and defeats the error-floor. Index Terms—LDPC codes, Generalized Belief Propagation, trapping sets, error-floor, local clustering
In this paper, we focus on the Generalized Belief Propagation (GBP) algorithm to solve trapping sets in Low-Density Parity-Check (LDPC) codes. Trapping sets are topological structures in Tanner graphs of LDPC codes that are not correctly decoded by Belief Propagation (BP), leading to exhibit an error-floor in the Bit-Error Rate (BER). Stemming from statistical physics of spin glasses, GBP consists in passing messages between clusters of Tanner graph nodes in another graph called the region-graph. Here, we introduce a specific clustering of nodes, based on a novel local loopfree principle, that breaks trapping sets such that the resulting region-graph is locally loopfree. We then construct a hybrid decoder made of BP and GBP that proves to be a powerful decoder as it clearly improves the BER and defeats the error-floor.