Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences


UC Berkeley


2009 Research Summary

Error Floor Prediction of LDPC Codes

View Current Project Information

Pamela Lee, Lara Dolecek1, Zhengya Zhang, Venkat Anantharam, Martin Wainwright, Borivoje Nikolic and Sudeep Kamath

National Science Foundation CCF-0635372, Marvell, Intel, Infineon Technologies and UC MICRO

The error-correcting performance of low-density parity check (LDPC) codes, when decoded using practical iterative decoding algorithms, is known to be close to Shannon limits for codes with suitably large blocklengths. A substantial limitation to the use of finite-length LDPC codes is the presence of an error floor in the low frame error rate (FER) region. We develop two methods, a stochastic one based on importance sampling and a deterministic one based on high signal-to-noise ratio (SNR) asymptotics, each suitably applied to absorbing sets within the LDPC code, to predict error floors. Our results are in very close agreement with hardware-based experimental results, and moreover extend the prediction of the error probability to as low as 10-30. The importance sampling scheme uses a mean-shifted version of the original Gaussian density, appropriately centered between a codeword and a dominant absorbing set, to produce an unbiased estimator of the FER with substantial computational savings over a standard Monte Carlo estimator. The deterministic estimates are based on channel-independent absorbing regions and are guaranteed to be a lower bound to the error probability in the high SNR regime. The usefulness of these results is demonstrated for both the standard Gaussian channel and a channel with Gaussian mixture noise.

L. Dolecek, Z. Zhang, M. Wainwright, V. Anantharam, and B. Nikolic, "Evaluation of the Low Frame Error Rate Performance of LDPC Codes Using Importance Sampling," IEEE Information Theory Workshop, September 2007, pp. 202-207.
P. Lee, L. Dolecek, Z. Zhang, V. Anantharam, B. Nikolic, and M. J. Wainwright, "Error Floors in LDPC Codes: Fast Simulation, Bounds and Hardware Emulation," IEEE International Symposium on Information Theory, July 2008, pp. 444-448.

1Massachusetts Institute of Technology