It is well recognized that low-density parity-check (LDPC) codes can suffer from an error floor when decoded iteratively. This performance degradation is often attributed to the class of objects known as trapping sets. As a subset of the trapping set collection, there exists a class of graphical structures called the absorbing sets. An absorbing set is a combinatorially-defined object; in particular a fully absorbing set is stable under bit-flipping decoding. By construction, there can exist trapping sets that are not stable under such a decoder. As a result, for finite-precision, iterative decoding algorithms used over additive channels, absorbing sets can describe decoding errors more accurately than the broader class of trapping sets. In the first part of this thesis, we compute the normalized logarithmic asymptotic distributions of absorbing sets and fully absorbing sets, including elementary (fully) absorbing sets. We compare distributions of absorbing and trapping sets for representative code parameters of interest, and quantify the (lack of) discrepancies between the two. Good absorbing set properties are implied for known structured LDPC codes, including repeat accumulate codes and protograph-based constructions. Establishing the distribution of fully absorbing sets (especially when the discrepancy with the trapping set distribution is significant) allows one to further refine the estimates of the error rates under bit-flipping and related decoders.To reduce implementation complexity, the messages in a practical message passing decoder are necessarily quantized. Absorbing regions act as "decoding regions" around absorbing sets. In the second part of this thesis, we take a closer look at the interplay between quantization and absorbing regions. We provide a study of a range of quantization choices, the impact of quantization on the candidate absorbing regions, and derive guidelines for practical decoders. We show that, due to the non-linear dynamics of message passing decoders, coarser quantization may in fact perform better than finer quantization. Results of this type of work can be particularly useful in designing high performance decoders for very high-reliability storage systems, such as emerging data storage hard disk and solid state drives.
It is well recognized that low-density parity-check (LDPC) codes can suffer from an error floor when decoded iteratively. This performance degradation is often attributed to the class of objects known as trapping sets. As a subset of the trapping set collection, there exists a class of graphical structures called the absorbing sets. An absorbing set is a combinatorially-defined object; in particular a fully absorbing set is stable under bit-flipping decoding. By construction, there can exist trapping sets that are not stable under such a decoder. As a result, for finite-precision, iterative decoding algorithms used over additive channels, absorbing sets can describe decoding errors more accurately than the broader class of trapping sets. In the first part of this thesis, we compute the normalized logarithmic asymptotic distributions of absorbing sets and fully absorbing sets, including elementary (fully) absorbing sets. We compare distributions of absorbing and trapping sets for representative code parameters of interest, and quantify the (lack of) discrepancies between the two. Good absorbing set properties are implied for known structured LDPC codes, including repeat accumulate codes and protograph-based constructions. Establishing the distribution of fully absorbing sets (especially when the discrepancy with the trapping set distribution is significant) allows one to further refine the estimates of the error rates under bit-flipping and related decoders.To reduce implementation complexity, the messages in a practical message passing decoder are necessarily quantized. Absorbing regions act as "decoding regions" around absorbing sets. In the second part of this thesis, we take a closer look at the interplay between quantization and absorbing regions. We provide a study of a range of quantization choices, the impact of quantization on the candidate absorbing regions, and derive guidelines for practical decoders. We show that, due to the non-linear dynamics of message passing decoders, coarser quantization may in fact perform better than finer quantization. Results of this type of work can be particularly useful in designing high performance decoders for very high-reliability storage systems, such as emerging data storage hard disk and solid state drives.
It is well recognized that low-density parity-check (LDPC) codes can suffer from an error floor when decoded iteratively. This performance degradation is often attributed to the class of objects known as trapping sets. Past work has focused on characterizing the distribution of trapping sets for a variety of code ensembles, including regular, irregular and structured LDPC codes. As a subset of the trapping set collection, there exists a class of graphical structures called the absorbing sets. An absorbing set is a combinatorially-defined object; in particular a fully absorbing set is stable under bit-flipping decoding. By construction, there can exist trapping sets that are not stable under such a decoder. As a result, for finite-precision, iterative decoding algorithms used over additive channels, absorbing sets can describe decoding errors more accurately than the broader class of trapping sets. In this paper, we compute the normalized logarithmic asymptotic distributions of absorbing sets and fully absorbing sets, including elementary (fully) absorbing sets. The calculations are based on the trapping set enumeration method proposed by Milenkovic, Soljanin, and Whiting in [1]. We compare distributions of absorbing and trapping sets for representative code parameters of interest, and quantify the (lack of) discrepancies between the two. Good absorbing set properties are implied for known structured LDPC codes, including repeat accumulate codes and protograph-based constructions. Establishing the distribution of fully absorbing sets (especially when the discrepancy with the trapping set distribution is significant) allows one to further refine the estimates of the error rates under bit-flipping and related decoders.
Low-density parity-check (LDPC) codes and accompanying message passing decoding algorithms are a popular choice for data encoding and decoding in modern communications and storage systems. To reduce implementation complexity, the messages in a practical message passing decoder are necessarily quantized. It is well known that the performance of practical, quantized message passing decoders in the high-reliability regime is governed by non-codeword decoding errors, typically described via trapping/absorbing sets. Absorbing regions act as “decoding regions” around absorbing sets. In this work, we take a closer look at the interplay between quantization and absorbing regions. We provide a study of a range of quantization choices, describe the impact of quantization on the candidate absorbing regions, and derive guidelines for practical finite-precision decoders. In particular, we show that, depending on the choice of the quantization allocation, different absorbing sets emerge as dominant: even though the overall performance of two quantization schemes can be similar, the distribution of decoding errors across possible absorbing sets can be substantially different. We take the advantage of disjointness of error profiles of two carefully chosen quantized decoders to design a decoder that is a series of these two decoders. The result is a performance improvement of at least an order magnitude relative to constituent decoders without increase in complexity.
The class of low-density parity-check (LDPC) codes is attractive, since such codes can be decoded using practical message-passing algorithms, and their performance is known to approach the Shannon limits for suitably large block lengths. For the intermediate block lengths relevant in applications, however, many LDPC codes exhibit a so-called “error floor,” corresponding to a significant flattening in the curve that relates signal-to-noise ratio (SNR) to the bit-error rate (BER) level. Previous work has linked this behavior to combinatorial substructures within the Tanner graph associated with an LDPC code, known as (fully) absorbing sets. These fully absorbing sets correspond to a particular type of near-codewords or trapping sets that are stable under bit-flipping operations, and exert the dominant effect on the low BER behavior of structured LDPC codes. This paper provides a detailed theoretical analysis of these (fully) absorbing sets for the class ofCp,γarray-based LDPC codes, including the characterization of all minimal (fully) absorbing sets for the array-based LDPC codes forγ=2,3,4, and moreover, it provides the development of techniques to enumerate them exactly. Theoretical results of this type provide a foundation for predicting and extrapolating the error floor behavior of LDPC codes.
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.
In contrast to the capacity approaching performance of iteratively decoded low-density parity check (LDPC) codes, many practical finite-length LDPC codes exhibit performance degradation, manifested in a so-called error floor. Previous work has linked this phenomenon to the presence of certain combinatorial structures within the Tanner graph representation of the code, termed absorbing sets. Absorbing sets are stable under the bit-flipping operations and have been shown to act as fixed points (¿absorbers¿) for a wider class of iterative decoding algorithms. Codes often possess absorbing sets whose size is smaller than the minimum distance: the smallest absorbing sets are deemed most detrimental culprits behind the error floor. This paper focuses on the elementary combinatorial bounds of the smallest (candidate) absorbing sets. For certain classes of practical codes we demonstrate the tightness of these bounds and show how can the structure of the code and the structure of the absorbing sets be utilized to increase the size of the smallest absorbing sets without compromising other code properties such as the node degrees and the girth. As such, this work provides a step towards a better code design by taking into account the combinatorial nature of fixed points of iterative decoding algorithms.
The error floor phenomenon observed with LDPC codes and their graph-based, iterative, message-passing (MP) decoders is commonly attributed to the existence of error-prone substructures - variously referred to as near-codewords, trapping sets, absorbing sets, or pseudocodewords - in a Tanner graph representation of the code. Many approaches have been proposed to lower the error floor by designing new LDPC codes with fewer such substructures or by modifying the decoding algorithm. Using a theoretical analysis of iterative MP decoding in an idealized trapping set scenario, we show that a contributor to the error floors observed in the literature may be the imprecise implementation of decoding algorithms and, in particular, the message quantization rules used. We then propose a new quantization method - (q+1)-bit quasi-uniform quantization - that efficiently increases the dynamic range of messages, thereby overcoming a limitation of conventional quantization schemes. Finally, we use the quasi-uniform quantizer to decode several LDPC codes that suffer from high error floors with traditional fixed-point decoder implementations. The performance simulation results provide evidence that the proposed quantization scheme can, for a wide variety of codes, significantly lower error floors with minimal increase in decoder complexity.