IEEE Transactions on Communications

A Threshold-Based Min-Sum Algorithm to Lower the Error Floors of Quantized LDPC Decoders

Homayoon Hatami, David G. M. Mitchell, Daniel J. Costello, Thomas E. Fuja

Published Jan 27, 2020• 27 citations

Abstract

For decoding low-density parity-check (LDPC) codes, the attenuated min-sum algorithm (AMSA) and the offset min-sum algorithm (OMSA) can outperform the conventional min-sum algorithm (MSA) at low signal-to-noise-ratios (SNRs), i.e., in the “waterfall region” of the bit error rate curve. This paper demonstrates that, for quantized decoders, MSA actually outperforms AMSA and OMSA in the “error floor” region, and that all three algorithms suffer from a relatively high error floor. This motivates the introduction of a modified MSA that is designed to outperform MSA, AMSA, and OMSA across all SNRs. The new algorithm is based on the assumption that trapping sets are the major cause of the error floor for quantized LDPC decoders. A performance estimation tool based on trapping sets is used to verify the effectiveness of the new algorithm and also to guide parameter selection. We also show that the implementation complexity of the new algorithm is only slightly higher than that of AMSA or OMSA. Finally, the simulated performance of the new algorithm, using several classes of LDPC codes (including spatially coupled LDPC codes), is shown to outperform MSA, AMSA, and OMSA across all SNRs.

DOI: 10.1109/tcomm.2020.2969902

Related papers

An Absorbing Set Analysis of Quantized LDPC Decoders

Homayoon Hatami

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.

Nov 16, 20220 citations

A Modified Min-Sum Algorithm for Quantized LDPC Decoders

Homayoon Hatami, David G. M. Mitchell, Daniel J. Costello +1 more

It is well known that for decoding low-density parity-check (LDPC) codes, the attenuated min-sum algorithm (AMSA) and the offset min-sum algorithm (OMSA) can outperform the conventional min-sum algorithm (MSA) at low signal-to-noise-ratios (SNRs). In this paper, we demonstrate that, for quantized LDPC decoders, although the MSA achieves better high SNR performance than the AMSA and OMSA, each of the MSA, AMSA, and OMSA all suffer from a relatively high error floor. Therefore, we propose a novel modification of the MSA for decoding quantized LDPC codes with the aim of lowering the error floor. Compared to the quantized MSA, the proposed modification is also helpful at low SNRs, where it matches the waterfall performance of the quantized AMSA and OMSA. The new algorithm is designed based on the assumption that trapping/absorbing sets (or other problematic graphical objects) are the major cause of the error floor for quantized LDPC decoders, and it aims to reduce the probability that these problematic objects lead to decoding errors.

IEEE International Symposium on Information Theory (ISIT)Jul 1, 20192 citations

Lower bounds for quantized LDPC min-sum decoders based on absorbing sets

Homayoon Hatami, David G. M. Mitchell, Daniel J. Costello +1 more

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.

Allerton Conference on Communication, Control, and ComputingOct 1, 20174 citations

Efficient Implementation of a Threshold Modified Min-Sum Algorithm for LDPC Decoders

Yanfang Liu, Wei Tang, David G. M. Mitchell

In this brief, we present a hardware efficient implementation of a threshold modified min-sum algorithm (MSA) to improve the performance of a low density parity-check (LDPC) decoder. The proposed architecture introduces a novel lookup table based threshold attenuation technique, called threshold attenuated MSA (TAMSA). The proposed TAMSA implementation is shown to improve bit error rate (BER) performance compared to the conventional AMSA and MSA. Furthermore, a layered version of the TAMSA implementation is investigated to reduce hardware cost. Utilizing circuit optimization techniques, including a parallel computing structure, the proposed layered TAMSA field-programmable gate array (FPGA) implementation results show that the modified architecture requires no extra circuit power or circuit area compared to conventional AMSA, and only 0.07% extra leaf cells compared to conventional MSA.

IEEE Transactions on Circuits & Systems II Express BriefsJun 11, 202018 citations

Performance of Quantized Min-Sum Decoding Algorithms for Irregular LDPC Codes

Daesun Oh, Keshab K. Parhi

This paper analyzes the performance of quantized min-sum decoding algorithms for irregular low-density parity-check (LDPC) codes. For regular LDPC codes, it is known that the normalized or offset min-sum decoding algorithm with quantization bits less than 6 bits achieves good performances over wide range of signal-to-noise ratios (SNR). However, finite precision effects in decoding irregular LDPC codes are different from that in decoding regular LDPC codes which is caused by the difference of convergence speeds between low degree nodes and high degree nodes. This paper proposes a novel method to improve the performance of the conventional normalized or offset min-sum decoding algorithm when it is approximated with finite precision for hardware implementations. The proposed method applies down-scaling factors to intrinsic information which has effects on increasing the reliability of extrinsic information at variable nodes and compensating the quantization errors caused by finite precision. Computer simulation results for irregular LDPC codes show that the proposed normalized and offset min-sum decoding algorithms achieve better performances at high SNR compared to the conventional normalized and offset min-sum algorithms under (6:2) quantization scheme.

IEEE International Symposium on Circuits and Systems proceedingsMay 1, 200715 citations

Optimally quantized offset min-sum algorithm for flexible LDPC decoder

Daesun Oh, Keshab K. Parhi

In this paper, we analyze the performance of quantized offset min-sum (MS) decoding algorithm and propose an optimally quantized offset MS algorithm for a flexible low-density parity-check (LDPC) decoder. It is known that the offset MS decoding algorithm is implemented with simplified hardware complexity and achieves good decoding performance. However, the finite precision effects in decoding LDPC codes result in performance different from floating point. The performance degradation is caused by different dynamic ranges of input data at high signal-to-noise ratio (SNR). The proposed offset MS algorithm uses the received data directly instead of log-likelihood ratio (LLR) data as the intrinsic information. It can achieve better performance than the conventional one since its offset factor is more effective at a wide range of SNR and the intrinsic information is quantized more robustly since it is independent of channel information. Also, it is possible for the proposed scheme to use a same quantization scheme for a flexible LDPC decoder, which can decode several kinds of LDPC codes. Simulation results show that our optimally quantized offset MS algorithms with 5-bits for (1728, 864) and (1728, 1296) irregular LDPC codes achieve better performance compared with the conventional offset MS algorithms with 6-bits quantization scheme.

Asilomar Conference on Signals, Systems and Computers (ACSSC)Oct 1, 200814 citations