Skip to main content
eScholarship
Open Access Publications from the University of California

Absorbing Set Distributions, Quantization and Practical Message Passing Decoders

  • Author(s): Amiri, Behzad
  • Advisor(s): Dolecek, Lara
  • et al.
Abstract

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.

Main Content
Current View