It is well-known that the performance of low-density parity-check codes is compromised by the emergence of an error floor, which is caused by so-called trapping sets. By identifying the dominant trapping sets, this error floor can be estimated analytically using a linear model. In this paper, this linear approach is improved to make the analysis more accurate. Then, guided by the error probability formula, a simple but effective method to improve the code performance in the error floor region is proposed, by introducing a boosting factor to the log-likelihood ratios returned from unsatisfied check nodes during the early decoding stages. It is shown that the effect of the dominant trapping sets can thus be reduced. The dominance of trapping sets can be further reduced by extending the computational range of the LLRs at the decoder. To illustrate these ideas, a short regular LDPC code constructed by Tanner, as well as the IEEE 802.3 LDPC code, are studied.
It is well-known that the performance of low-density parity-check codes is compromised by the emergence of an error floor, which is caused by so-called trapping sets. By identifying the dominant trapping sets, this error floor can be estimated analytically using a linear model. In this paper, this linear approach is improved to make the analysis more accurate. Then, guided by the error probability formula, a simple but effective method to improve the code performance in the error floor region is proposed, by introducing a boosting factor to the log-likelihood ratios returned from unsatisfied check nodes during the early decoding stages. It is shown that the effect of the dominant trapping sets can thus be reduced. The dominance of trapping sets can be further reduced by extending the computational range of the LLRs at the decoder. To illustrate these ideas, a short regular LDPC code constructed by Tanner, as well as the IEEE 802.3 LDPC code, are studied.
The goal of error control coding is to encode information in such a way, that in the event that errors occur during transmission over a noisy communication channel or during storage in an unreliable memory, the receiver can correct the errors and recover the original transmitted information. Low-density parity-check (LDPC) codes are a kind of high performance linear block code, which are already used in many recent communication systems. Information rates guaranteed by these codes approach the theoretical Shannon capacity limit. In addition, LDPC codes are now widely used in practice and included in many communication standards. Therefore study of these codes is very important and practical approaches to their design and decoding techniques are of great interest. There exist very good decoding algorithms for LDPC codes with respect to different channel models. However, LDPC codes suffer from the infamous error floor problem at high signal-to-noise ratios. This problem is attributed to the trapping sets by Richardson. It is shown that the dominant trapping sets of regular LDPC codes, so called absorption sets, undergo a two-phase dynamic behavior in the iterative message-passing decoding algorithm. We present a linear dynamic model for the iteration behavior of these sets. It can be seen that they undergo an initial geometric growth phase which stabilizes in a final bit-flipping behavior where the algorithm reaches a fixed point. Our analysis is shown to lead to very accurate numerical calculations of the error floor bit error rates down to error rates that are inaccessible by simulation. The topologies of the dominant absorption sets of two example codes, the IEEE 802.3an [2048,1723] regular (6,32) LDPC code and the Tanner [155,64,20] regular (3,5) LDPC code, are identified and tabulated by using topological features in combination with search algorithms, respectively. To make our analysis more complete, we provide more solid evidence showing that trapping sets are equivalent to absorption sets. In other words, we argue that absorption sets characterize all failure mechanisms. Some insights from our linear analysis can be borrowed to approach this problem. Another insight that this formula provides to us is the means to reduce the error floor, which is another important part of what we hoped to achieve by developing the formula in the first place. By allowing the log-likelihood ratios (LLRs) utilized by the message-passing decoding to grow bigger in precision length, the absorption sets as a trouble-causing structure will be successfully corrected. Therefore, the absorption sets, generically born with the code design, will no longer threaten the error correcting performance as long as the messages have enough room and time to grow. This translates to greater LLR clipping thresholds and more iterations, both of which are preset at the decoder. However, the actual settings are dependent on how much the subgraph of the dominant absorption set resembles that of a non-zero minimum-weight codeword, therefore the settings are empirical. In general more likeness in their topologies, the more effort it costs to correct the absorption set.
This paper addresses the prediction of error floors of low-density parity-check (LDPC) codes with variable nodes of constant degree in the additive white Gaussian noise (AWGN) channel. Specifically, we focus on the performance of the sum-product algorithm (SPA) decoder formulated in the log-likelihood ratio (LLR) domain. We hypothesize that several published error floor levels are due to the manner in which decoder implementations handled the LLRs at high SNRs. We employ an LLR-domain SPA decoder that does not saturate near-certain messages and find the error rates of our decoder to be lower by at least several orders of magnitude. We study the behavior of trapping sets (or near-codewords) that are the dominant cause of the reported error floors. We develop a refined linear model, based on the work of Sun and others, that accurately predicts error floors caused by elementary tapping sets for saturating decoders. Performance results of several codes at several levels of decoder saturation are presented.
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.
We discuss error floor asympotics and present a method for improving the performance of low-density parity check (LDPC) codes in the high SNR (error floor) region. The method is based on Tanner graph covers that do not have trapping sets from the original code. The advantages of the method are that it is universal, as it can be applied to any LDPC code/channel/decoding algorithm and it improves performance at the expense of increasing the code length, without losing the code regularity, without changing the decoding algorithm, and, under certain conditions, without lowering the code rate. The proposed method can be modified to construct convolutional LDPC codes also. The method is illustrated by modifying Tanner, MacKay and Margulis codes to improve performance on the binary symmetric channel (BSC) under the Gallager B decoding algorithm. Decoding results on AWGN channel are also presented to illustrate that optimizing codes for one channel/decoding algorithm can lead to performance improvement on other channels.
We discuss error floor asympotics and present a method for improving the performance of low-density parity-check (LDPC) codes in the high SNR (error floor) region. The method is based on Tanner graph covers that do not have trapping sets from the original code. The advantages of the method are that it is universal, as it can be applied to any LDPC code/channel/decoding algorithm and it improves performance at the expense of increasing the code length, without losing the code regularity, without changing the decoding algorithm, and, under certain conditions, without lowering the code rate. The proposed method can be modified to construct convolutional LDPC codes also. The method is illustrated by modifying Tanner, MacKay and Margulis codes to improve performance on the binary symmetric channel (BSC) under the Gallager B decoding algorithm. Decoding results on AWGN channel are also presented to illustrate that optimizing codes for one channel/decoding algorithm can lead to performance improvement on other channels.
Finite-length low-density parity-check (LDPC) codes usually suffer from error floors in high signal-to-noise ratio (SNR) region. The error floor in the additive white Gaussian noise (AWGN) channel is known to be caused by trapping sets or absorbing sets. In this paper, we investigate combinatorial properties of trapping sets by using graph-theoretic approach. All non-isomorphic trapping sets are identified by a graph-theoretic tool and a method to distinguish the trapping sets which cannot appear in any protograph-based LDPC codes are proposed. Finally, a measure for estimating the harmfulness of trapping sets is proposed by using the linear system model of trapping sets.