TY - GEN
T1 - Loop calculus helps to improve belief propagation and linear programming decodings of low-density-parity-check codes
AU - Chertkov, Michael
AU - Chernyak, Vladimir Y.
PY - 2006
Y1 - 2006
N2 - We illustrate the utility of the recently developed loop calculus [1], [2] for improving the Belief Propagation (BP) algorithm. If the algorithm that minimizes the Bethe free energy fails we modify the free energy by accounting for a critical loop in a graphical representation of the code. The log-likelihood specific critical loop is found by means of the loop calculus. The general method is tested using an example of the Linear Programming (LP) decoding, that can be viewed as a special limit of the BP decoding. Considering the (155, 64, 20) code that performs over Additive-White-Gaussian channel we show that the loop calculus improves the LP decoding and corrects all previously found dangerous configurations of log-likelihoods related to pseudo-codewords with low effective distance, thus reducing the code's error-floor.
AB - We illustrate the utility of the recently developed loop calculus [1], [2] for improving the Belief Propagation (BP) algorithm. If the algorithm that minimizes the Bethe free energy fails we modify the free energy by accounting for a critical loop in a graphical representation of the code. The log-likelihood specific critical loop is found by means of the loop calculus. The general method is tested using an example of the Linear Programming (LP) decoding, that can be viewed as a special limit of the BP decoding. Considering the (155, 64, 20) code that performs over Additive-White-Gaussian channel we show that the loop calculus improves the LP decoding and corrects all previously found dangerous configurations of log-likelihoods related to pseudo-codewords with low effective distance, thus reducing the code's error-floor.
UR - http://www.scopus.com/inward/record.url?scp=84940656304&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84940656304&partnerID=8YFLogxK
M3 - Conference contribution
T3 - 44th Annual Allerton Conference on Communication, Control, and Computing 2006
SP - 31
EP - 40
BT - 44th Annual Allerton Conference on Communication, Control, and Computing 2006
PB - University of Illinois at Urbana-Champaign, Coordinated Science Laboratory and Department of Computer and Electrical Engineering
T2 - 44th Annual Allerton Conference on Communication, Control, and Computing 2006
Y2 - 27 September 2006 through 29 September 2006
ER -