Research Projects

Error Floor Prediction of LDPC Codes

Pamela Lee, Lara Dolecek¹, 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.

[1]

Evaluation of the Low Frame Error Rate Performance of LDPC Codes Using Importance Sampling. Dolecek, L.; Zhengya Zhang; Wainwright, M.; Anantharam, V.; Nikolic, B.; Information Theory Workshop, 2007. ITW '07. IEEE 2-6 Sept. 2007 Page(s):202 - 207.

[2]

Error floors in LDPC codes: Fast simulation, bounds and hardware emulation. Lee, P.; Dolecek, L.; Zhengya Zhang; Anantharam, V.; Borivoje; Wainwright, M.J.; Information Theory, 2008. ISIT 2008. IEEE International Symposium on 6-11 July 2008 Page(s):444 - 448,

¹Massachusetts Institute of Technology