Pseudo-codeword Landscape

We discuss the performance of low-density-parity-check (LDPC) codes decoded by means of linear programming (LP) at moderate and large signal-to-noise-ratios (SNR). Utilizing a combination of the previously introduced pseudo-codeword-search method and a new "dendro" trick, which allows us to reduce the complexity of the LP decoding, we analyze the dependence of the frame-error-rate (FER) on the SNR. Under maximum-a-posteriori (MAP) decoding the dendro-code, having only checks with connectivity degree three, performs identically to its original code with high-connectivity checks. For a number of popular LDPC codes performing over the additive-white-Gaussian-noise (AWGN) channel we found that either an error-floor sets at a relatively low SNR, or otherwise a transient asymptote, characterized by a faster decay of FER with the SNR increase, precedes the error-floor asymptote. We explain these regimes in terms of the pseudo-codeword spectra of the codes.