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 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. In this paper, we show that one source of the error floors observed in the literature may be the message quantization rule used in the iterative decoder implementation. We then propose a new quantization method to overcome the limitations of standard quantization rules. Performance simulation results for two LDPC codes commonly found to have high error floors when used with the fixed-point min-sum decoder and its variants demonstrate the validity of our findings and the effectiveness of the proposed quantization algorithm.
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 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. In this paper, we show that one source of the error floors observed in the literature may be the message quantization rule used in the iterative decoder implementation. We then propose a new quantization method to overcome the limitations of standard quantization rules. Performance simulation results for two LDPC codes commonly found to have high error floors when used with the fixed-point min-sum decoder and its variants demonstrate the validity of our findings and the effectiveness of the proposed quantization algorithm.
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.
The performance of low-density parity-check (LDPC) codes at high signal-to- noise ratios (SNRs) is known to be limited by the presence of certain sub-graphs that exist in the Tanner graph representation of the code, for example trapping sets and absorbing sets. This dissertation derives a lower bound on the frame error rate (FER) of any LDPC code containing a given problematic sub-graph, assuming a particular iterative message passing (MP) decoder and decoder quantization. A crucial aspect of the lower bound is that it is code-independent, in the sense that it can be derived based only on a problematic sub-graph and then applied to any code containing it. Due to the complexity of evaluating the exact bound, assumptions are proposed to approximate it, from which we can estimate decoder performance. For LDPC codes, the attenuated min-sum algorithm (AMSA) and the offset min- sum algorithm (OMSA) are known to outperform the conventional min-sum algorithm (MSA) at low SNRs, i.e., in the waterfall region of the FER curve. This dis- sertation demonstrates that, for quantized LDPC decoders, the AMSA and OMSA underperform the MSA at high SNRs, i.e., in the error floor region of the FER curve, and that the MSA, AMSA, and OMSA all suffer from a relatively high error floor. Therefore, we introduce a novel modification of the MSA for quantized decoding of LDPC codes, called the threshold attenuated min-sum algorithm (TAMSA) (or the threshold offset min-sum algorithm (TOMSA)) with the aim of outperforming the MSA, AMSA, and OMSA at both low and high SNRs. The new decoding algorithm is designed based on the common assumption that trapping sets are the major cause of the error floor for quantized LDPC decoders, and it is shown to reduce the error probability associated with these problematic graphic objects. The lower bound analysis tool noted above is then used to verify the effectiveness of the new TAMSA (TOMSA) and also to assist in finding its optimum design parameters. We also show that the implementation complexity of the TAMSA (TOMSA) is only slightly higher than that of the AMSA or OMSA. Finally, we extend the lower bound to sliding window (SW) decoding of spatially coupled LDPC (SC-LDPC) codes. Additionally, we show that the performance of the TAMSA (TOMSA) is better than that of the MSA, AMSA, and OMSA for SW.
The performance of low-density parity-check (LDPC) codes at high signal-to-noise ratios (SNRs) is known to be limited by the presence of certain sub-graphs that exist in the Tanner graph representation of the code, for example trapping sets and absorbing sets. This paper derives a lower bound on the frame error rate (FER) of any LDPC code containing a given problematic sub-graph, assuming a particular message passing decoder and decoder quantization. A crucial aspect of the lower bound is that it is code-independent, in the sense that it can be derived based only on a problematic sub-graph and then applied to any code containing it. Due to the complexity of evaluating the exact bound, assumptions are proposed to approximate it, from which we can estimate decoder performance. Simulated results obtained for both the quantized sum-product algorithm (SPA) and the quantized min-sum algorithm (MSA) are shown to be consistent with the approximate bound and the corresponding performance estimates. Different classes of LDPC codes, including both structured and randomly constructed codes, are used to demonstrate the robustness of the approach.
One of the most significant impediments to the use of LDPC codes in many communication and storage systems is the error-rate floor phenomenon associated with their iterative decoders. The error floor has been attributed to certain subgraphs of an LDPC code's Tanner graph induced by so-called trapping sets. We show in this paper that once we identify the trapping sets of an LDPC code of interest, a sum-product algorithm (SPA) decoder can be custom-designed to yield floors that are orders of magnitude lower than floors of the the conventional SPA decoder. We present three classes of such decoders: (1) a bi-mode decoder, (2) a bit-pinning decoder which utilizes one or more outer algebraic codes, and (3) three generalized-LDPC decoders. We demonstrate the effectiveness of these decoders for two codes, the rate-1/2 (2640,1320) Margulis code which is notorious for its floors and a rate-0.3 (640,192) quasi-cyclic code which has been devised for this study. Although the paper focuses on these two codes, the decoder design techniques presented are fully generalizable to any LDPC code.
Previously published lower bounds on the error-floor performance of low-density parity-check (LDPC) codes with quantized sum-product algorithm (SPA) decoders need modification to apply to min-sum algorithm (MSA) decoders. In this paper we show that, due to the sub-optimality of MSA decoders, certain assumptions that apply to SPA decoders are not valid for MSA decoders. Based on appropriately modified assumptions, an improved technique is then proposed to evaluate lower bounds on the error floor performance of LDPC codes for an additive white Gaussian noise channel and a quantized MSA decoder. This new technique not only results in error floor bounds for MSA decoders, but also for SPA decoders. The obtained bound is based on an absorbing set, and a good error floor approximation can be obtained when the multiplicity of the absorbing set is known.
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.