In the low-error rate regime, message-passing (MP) decoding for low-density parity-check (LDPC) codes is known to have performance degradation due to trapping sets (TSs), which often limits the use of LDPC codes for applications with low target error rates like storage devices. This work proposes a novel deep-learning based decoding algorithm which is tailored for breaking TSs. In particular, when MP decoding fails due to TSs, there exist pairs of unsatisfied check nodes (CNs) which are connected through paths only with error variable nodes (VNs), i.e., VNs with erroneous hard-decision results. The proposed algorithm efficiently identifies the paths with error VNs between unsatisfied CNs with the aid of deep-learning techniques. Then, the decoding failures are resolved by repeating the MP decoding after re-initializing the channel outputs for the error VNs in the identified paths. In addition, by analyzing the behaviors of the deep-learning based algorithm, we propose a low-complexity algorithm, called adaptive-error-path (AEP) detector. Simulation results show that the proposed algorithms efficiently break the TSs and significantly improve the error-floor performance in the low error-rate regime.
In the low-error rate regime, message-passing (MP) decoding for low-density parity-check (LDPC) codes is known to have performance degradation due to trapping sets (TSs), which often limits the use of LDPC codes for applications with low target error rates like storage devices. This work proposes a novel deep-learning based decoding algorithm which is tailored for breaking TSs. In particular, when MP decoding fails due to TSs, there exist pairs of unsatisfied check nodes (CNs) which are connected through paths only with error variable nodes (VNs), i.e., VNs with erroneous hard-decision results. The proposed algorithm efficiently identifies the paths with error VNs between unsatisfied CNs with the aid of deep-learning techniques. Then, the decoding failures are resolved by repeating the MP decoding after re-initializing the channel outputs for the error VNs in the identified paths. In addition, by analyzing the behaviors of the deep-learning based algorithm, we propose a low-complexity algorithm, called adaptive-error-path (AEP) detector. Simulation results show that the proposed algorithms efficiently break the TSs and significantly improve the error-floor performance in the low error-rate regime.
Trapping sets strongly degrade performance of low-density parity check (LDPC) codes in the low-error-rate region. This creates significant difficulties for the deployment of LDPC codes to low-error-rate applications such as storage and wireless systems with no or limited retransmission options. We propose a novel technique for breaking trapping sets based on collaborative decoding that utilizes two different decoding modes. While the main decoding mode executes message passing based on the original parity check matrix of the corresponding LDPC code, the sub-decoding mode operates on a modified parity check matrix formed by removing a portion of check nodes in the factor graph representation of the given code. The modified parity check matrix is designed to promote a passing of correct information into erroneous variable nodes in the trapping set. Theoretical properties of the proposed trapping-set-breaking technique have been established based on the notion of the improved separation for the trapped variable nodes. Simulation results show that the proposed collaborative LDPC decoding scheme switching between the two decoding modes back and forth effectively breaks dominant trapping sets of various known types of regular and irregular LDPC codes.
Protecting logical information in the form of a classical bit or a quantum bit (qubit) is an essential step in ensuring fault-tolerant classical or quantum computation. Error correction codes and their decoders perform this step by adding redundant information that aids the decoder to recover or protect the logical information even in the presence of noise. Low-density parity-check (LDPC) codes have been one of the most popular error correction candidates in modern communication and data storage systems. Similarly, their quantum analogues, quantum LDPC codes are being actively pursued as excellent prospects for error correction in future fault-tolerant quantum systems due to their asymptotically non-zero rates, sparse parity check matrices, and efficient iterative decoding algorithms. This dissertation deals with failure configurations, known as \emph{trapping sets} of classical and quantum LDPC codes when decoded with iterative message passing decoding algorithms, and the \emph{error floor phenomenon} - the degradation of logical error rate performance at low physical noise regime. The study of quantum trapping sets will enable the construction of better quantum LDPC codes and also help in modifying iterative quantum decoders to achieve higher fault-tolerant thresholds and lower error floors. Towards this goal, the dissertation also presents iterative decoders for classical and quantum LDPC codes using the \emph{deep neural network framework}, novel iterative decoding algorithms, and a decoder-aware \emph{expansion-contraction method} for error floor estimation. In this dissertation, we first establish a systematic methodology by which one can identify and classify \emph{quantum trapping sets} (QTSs) according to their topological structure and decoder used. For this purpose, we leverage the known harmful configurations in the Tanner graph, called \emph{trapping sets} (TSs), from the classical error correction world. The conventional definition of a trapping set of classical LDPC codes is generalized to address the syndrome decoding scenario for quantum LDPC codes. Furthermore, we show that the knowledge of QTSs can be used to design better quantum LDPC codes and decoders. In the context of the development of novel decoders, we extend the stochastic resonance based decoders to quantum LDPC codes, propose iteration-varying message passing decoders with their message update rules learned by neural networks tuned for low logical error rate, and present a syndrome based generalized belief propagation algorithm for tackling convergence failure of iterative decoders due to the presence of short cycles. Our analysis of TSs of a layered decoding architecture clearly reveals the dependence of the harmfulness of TSs (classical or quantum) on the iterative decoder, and thus on the error floor estimates. We present a computationally efficient method for estimating error floors of LDPC codes over the binary symmetric channel without any prior knowledge of its trapping sets. The sub-graph expansion-contraction method is a general procedure for TS characterization, which lists all harmful error patterns up to a given weight for the LDPC code and decoder. Based on this decoder-aware trapping set characterization for LDPC codes, we propose a model-driven deep neural network (DNN) framework that unfolds the decoding iterations, to design the \emph{decoder diversity of finite alphabet iterative decoders (FAIDs)}. Our decoder diversity DNN-FAID delivers excellent waterfall performance along with a low error floor.
Low-density parity-check (LDPC) codes are widely used in a variety of communication systems because of their low complexity iterative decoding and performance approaching Shannon capacity. However, the existence of error floor seriously hinders the application and development of LDPC codes in related fields. In this paper, a deep learning-aided post-processing scheme (DLAPPS) based on Layered Normalized Min-Sum algorithm (LNMSA) is proposed to effectively lower error floor of LDPC codes. LNMSA is used in the first stage, and in the second stage incorrect frames are re-decoded by processing two types of nodes classified by neural networks. Simulation results show that the proposed DLAPPS can significantly improve error correction performance and lower the error floor of LDPC codes while maintaining a relatively low decoding complexity.
Low-density parity-check (LDPC) codes have been the focus of much research over the past decade thanks to their near Shannon limit performance and to their efficient message- passing (MP) decoding algorithms. However, the error floor phenomenon observed in MP decoding, which manifests itself as an abrupt change in the slope of the error-rate curve, has hindered the adoption of LDPC codes and MP decoders in some applications requiring very low error rates. As an alternative to MP decoding, linear programming (LP) decoding is an approximation to maximum-likelihood decoding by relaxing the optimal decoding problem into a linear optimization problem. It has been noticed that, when the symbols error probability in channel output is low, LP decoding has superior error correction performance. However, due to the inefficiency of general- purpose LP solvers which are not optimized for solving LP problems, LP decoding is computationally more complex than MP decoding, especially for codes of large block size. In this dissertation, we first design an efficient exhaustive search algorithm to find all small error-prone substructures, some of which are commonly blamed for certain decoding failures of MP decoding. Then, we investigate the cause of error floors in LDPC codes from the perspective of the MP decoder implementation, with special attention to limitations that decrease the numerical accuracy of messages passed during decoding, and propose a quantization method for fixed-point implementation of MP decoding which significantly improves the error-floor performance by overcoming the limitations of standard quantization rules. For LP decoding, we improve the error-correcting capability of LP decoding by using an effective algorithm to generate additional redundant parity-check constraints which eliminate certain undesired solutions to LP decoding problem. We further propose an efficient message-passing algorithm to solve the LP decoding problem. This algorithm is based on the alternating direction method of multipliers (ADMM), a classic technique in convex optimization theory, and our key contribution is a novel, efficient projection algorithm that can improve the decoding speed of the ADMM- based LP decoder. The last part of this dissertation is a separate piece of work on optimizing video transmission over distributed cognitive radio network
In this paper, we present a computationally efficient method for estimating error floors of low-density parity-check (LDPC) codes over the binary symmetric channel (BSC) without any prior knowledge of its trapping sets (TSs). Given the Tanner graph G of a code, and the decoding algorithm V, the method starts from a list of short cycles in G, and expands each cycle by including its sufficiently large neighborhood in G. Variable nodes of the expanded sub-graphs EXP are then corrupted exhaustively by all possible error patterns, and decoded by V operating on EXP. Union of support of the error patterns for which V fails on each EXP defines a subset of variable nodes that is a TS. The knowledge of the minimal error patterns and their strengths in each TSs is used to compute an estimation of the frame error rate. This estimation represents the contribution of error events localized on TSs, and therefore serves as an accurate estimation of the error floor performance of V at low BSC cross-over probabilities. We also discuss trade-offs between accuracy and computational complexity. Our analysis shows that in some cases the proposed method provides a million-fold improvement in computational complexity over standard Monte-Carlo simulation.
In this paper, a modified sum-product algorithm to correct bit errors captured within the trapping sets, which are produced in decoding of low-density parity-check (LDPC) codes, is proposed. Unlike the original sum-product algorithm, the proposed decoding method consists of two stages. Whether the main cause of decoding failure is the trapping sets or not is determined at the first stage. And the bit errors within the trapping sets are corrected at the second stage. In the modified algorithm, the set of failed check nodes and the transition patterns of hard-decision bits are exploited to search variable nodes in the trapping sets. After inverting information of the variable nodes, the sum-product algorithm is carried out to correct the bit errors. As a result of simulation, the proposed algorithm shows continuously improved error performance with increase in the signal-to-noise ratio. It is, therefore, considered that the modified sum-product algorithm significantly reduces or possibly eliminates the error floor in LDPC codes.