The error mechanisms of iterative message-passing decoders with low-density parity-check codes are studied. The connections between trapping sets and deviations on computation trees are explored in depth in an attempt to bridge experimental and analytic approaches to these error mechanisms. An iterative algorithm for finding low-weight trapping sets is presented along with a method for characterizing the weight of deviations that result from trapping sets.
The error mechanisms of iterative message-passing decoders with low-density parity-check codes are studied. The connections between trapping sets and deviations on computation trees are explored in depth in an attempt to bridge experimental and analytic approaches to these error mechanisms. An iterative algorithm for finding low-weight trapping sets is presented along with a method for characterizing the weight of deviations that result from trapping sets.
The error mechanisms of iterative message‐passing decoders for low‐density parity‐check codes are studied. A tutorial review is given of the various graphical structures, including trapping sets, stopping sets, and absorbing sets that are frequently used to characterize the errors observed in simulations of iterative decoding of low‐density parity‐check codes. The connections between trapping sets and deviations on computation trees are explored in depth using the notion ofproblematictrapping sets in order to bridge the experimental and analytic approaches to these error mechanisms. A new iterative algorithm for finding low‐weight problematic trapping sets is presented and shown to be capable of identifying many trapping sets that are frequently observed during iterative decoding of low‐density parity‐check codes on the additive white Gaussian noise channel. Finally, a new method is given for characterizing the weight of deviations that result from problematic trapping sets.
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.
Error-floors are the main reason for excluding LDPC codes from applications requiring very low bit-error rate. They are attributed to a particular structure in the codes' Tanner graphs, known as trapping sets, which traps the message-passing algorithms commonly used to decode LDPC codes, and prevents decoding from converging to the correct codeword. A technique is proposed to break trapping sets while decoding. Based on decoding results leading to a decoding failure, some bits are identified in a previous iteration and flipped and decoding is restarted. This backtracking may enable the decoder to get out of the trapped state. A semi-analytical method is also proposed to predict the error-floor after backtracking. Simulation results indicate the effectiveness of the proposed technique in lowering the error-floor. The technique, which has moderate complexity overhead, is applicable to any code without requiring a prior knowledge of the structure of its trapping sets.
Conditional upper bounds are given for min-sum decoding of low-density parity-check codes in the error floor region. It is generally thought that absorbing sets, i.e., small collections of variable nodes connected to a relatively small number of unsatisfied check nodes, are the primary source of errors in the error floor region. The conditional upper bounds presented here are based on the assumption that all error floor errors are caused by absorbing sets. In order to bound the probability of error associated with each absorbing set, a directed-edge Tanner graph is used to link absorbing sets to low-weight deviations. These low-weight deviations result when a proportionally large number of nodes within a stopping set belong to an absorbing set contained inside the stopping set. A complete collection of the most problematic absorbing sets, and the minimum deviation weights that result from them, are used to derive a conditional upper bound on the probability of error for min-sum decoding of low-density parity-check codes. Simulation results are given to demonstrate the accuracy of the bound.
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.
It is shown that dominant trapping sets of regular low-density parity-check (LDPC) codes, so-called absorption sets, undergo a two-phased dynamic behavior in the iterative message-passing decoding algorithm. Using a linear dynamic model for the iteration behavior of these sets, it is shown that they undergo an initial geometric growth phase which stabilizes in a final bit-flipping behavior where the algorithm reaches a fixed point. This 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 topology of the dominant absorption sets of an example code, the IEEE 802.3an (2048,1723) regular LDPC code, are identified and tabulated using topological relationships in combination with search algorithms.