Analysis of Trapping Sets for LDPC Codes Using A Linear System Model

Qingqing Peng, Ke Liu, Guiying Yan +1 more

Adnan Landolsi Mohamed, Esa Alghonaim, El-Maleh Aiman

Shuai Zhang, Christian B. Schlegel

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.

Shuai Zhang

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.

B. N. Sindhu Tejaswini, Rajendra Prasad Lal, Vadlamudi Ch. Venkaiah