Allerton Conference on Communication, Control, and Computing

Error floor approximation for LDPC codes in the AWGN channel

Brian K. Butler, Paul H. Siegel

Published Sep 1, 2011• 26 citations

Abstract

This paper addresses the prediction of error floors of variable-regular Low Density Parity Check (LDPC) codes in the Additive White Gaussian Noise (AWGN) channel. Specifically, we focus on the Sum-Product Algorithm (SPA) decoder in the log-domain at high SNRs. We hypothesize that several published error floor levels are due to numerical saturation within their decoders when handling high SNRs. We take care to develop a log-domain SPA decoder that does not saturate near-certain messages and find the error rates of our decoder to be lower by at least several orders of magnitude. We study the behavior of near-codewords / trapping sets that dominate the reported error floors. J. Sun, in his Ph.D. thesis, used a linear system model to show that error floors due to elementary trapping sets don't exist under certain conditions, assuming that the SPA decoder is non-saturating [1]. We develop a refined linear model which we find to be capable of predicting the error floors caused by elementary trapping sets for saturating decoders. Performance results of several codes at several levels of decoder saturation are presented.

DOI: 10.1109/allerton.2011.6120169

Related papers

Error Floor Approximation for LDPC Codes in the AWGN Channel

Brian K. Butler, Paul H. Siegel

This paper addresses the prediction of error floors of low-density parity-check (LDPC) codes with variable nodes of constant degree in the additive white Gaussian noise (AWGN) channel. Specifically, we focus on the performance of the sum-product algorithm (SPA) decoder formulated in the log-likelihood ratio (LLR) domain. We hypothesize that several published error floor levels are due to the manner in which decoder implementations handled the LLRs at high SNRs. We employ an LLR-domain SPA decoder that does not saturate near-certain messages and find the error rates of our decoder to be lower by at least several orders of magnitude. We study the behavior of trapping sets (or near-codewords) that are the dominant cause of the reported error floors. We develop a refined linear model, based on the work of Sun and others, that accurately predicts error floors caused by elementary tapping sets for saturating decoders. Performance results of several codes at several levels of decoder saturation are presented.

arXiv:1202.2826Feb 13, 20123 citations

Error Floor Approximation for LDPC Codes in the AWGN Channel

Brian K. Butler, Paul H. Siegel

This paper addresses the prediction of error floors of low-density parity-check codes transmitted over the additive white Gaussian noise channel. Using a linear state-space model to estimate the behavior of the sum-product algorithm (SPA) decoder in the vicinity of trapping sets (TSs), we study the performance of the SPA decoder in the log-likelihood ratio (LLR) domain as a function of the LLR saturation level. When applied to several widely studied codes, the model accurately predicts a significant decrease in the error floor as the saturation level is allowed to increase. For nonsaturating decoders, however, we find that the state-space model breaks down after a small number of iterations due to the strong correlation of LLR messages. We then revisit Richardson's importance-sampling methodology for estimating error floors due to TSs when those floors are too low for Monte Carlo simulation. We propose modifications that account for the behavior of a nonsaturating decoder and present the resulting error floor estimates for the Margulis code. These estimates are much lower, significantly steeper, and more sensitive to iteration count than those previously reported.

IEEE Transactions on Information TheoryOct 17, 201472 citations

A Semi Linear State Space Model for Error Floor Estimation of LDPC codes over the AWGN Channel

Ali Farsiabi, Amir H. Banihashemi

IEEE International Symposium on Information Theory (ISIT)Jun 26, 20220 citations

A Semi Linear State Space Model for Error Floor Estimation of LDPC Codes Over the AWGN Channel

Ali Farsiabi, Amir H. Banihashemi

In this paper, we propose a novel state-space model to represent the behavior of sum-product algorithm (SPA) in the vicinity of a trapping set (TS) of a low-density parity-check (LDPC) code over the additive white Gaussian noise (AWGN) channel in the error floor region. The proposed model takes into account the non-linear behavior of SPA in the initial iterations using a quadratic approximation, and dynamically adjusts the operating point of the model in accordance to the statistical properties of TS messages. This is in contrast to the existing linear state-space models which linearly approximate the non-linear behavior of SPA at around the operating point of zero in all iterations. Simulation results are provided to demonstrate the higher accuracy of the proposed model in estimating the error floor of LDPC codes compared to the linear state-space model. We also make connections to the semi-analytical code-dependent technique proposed by Richardson for the error floor estimation of LDPC codes, and demonstrate that the proposed state-space model not only is a fully-analytical code-independent counterpart to that method, but also has less complexity and, in some cases, more accuracy.

IEEE Transactions on CommunicationsOct 6, 20221 citation

Will the real error floor please stand up?

Xiaojie Zhang, Paul H. Siegel

In this paper we continue our study of the influence of message saturation and quantization on the error-rate performance of iterative, message-passing decoders for low-density parity-check (LDPC) codes. We extend our previous analytical results for the min-sum algorithm (MSA) and its variants to the sum-product algorithm (SPA), demonstrating the significant impact of message saturation on the appearance and location of error floors. Simulation results for selected LDPC codes on the binary symmetric channel (BSC) and the additive white Gaussian noise channel (AWGNC) confirm that the benefits of a quasiuniform quantization scheme, already observed in the context of MSA decoding, apply also to SPA-based decoding.

International Conference on Signal Processing and Communications (SPCOM)Jul 1, 20128 citations

LDPC Code Density Evolution in the Error Floor Region

Brian K. Butler, Paul H. Siegel

This short paper explores density evolution (DE) for low-density parity-check (LDPC) codes at signal-to-noise-ratios (SNRs) that are significantly above the decoding threshold. The focus is on the additive white Gaussian noise channel and LDPC codes in which the variable nodes have regular degree. Prior work, using DE, produced results in the error floor region which were asymptotic in the belief-propagation decoder's log-likelihood ratio (LLR) values. We develop expressions which closely approximate the LLR growth behavior at moderate LLR magnitudes. We then produce bounds on the mean extrinsic check-node LLR values required, as a function of SNR, such that the growth rate of the LLRs exceeds that of a particular trapping set's internal LLRs such that its error floor contribution may be eliminated. We find that our predictions for the mean LLRs to be accurate in the error floor region, but the predictions for the LLR variance to be lacking beyond several initial iterations.

arXiv:1409.5783Sep 19, 20141 citation