TY - GEN
T1 - TP decoding
AU - Lu, Yi
AU - Méasson, Cyril
AU - Montanari, Andrea
PY - 2007
Y1 - 2007
N2 - 'Tree pruning' (TP) is an algorithm for probabilistic inference on binary Markov random fields. It has been recently derived by Dror Weitz and used to construct the first fully polynomial approximation scheme for counting independent sets up to the 'tree uniqueness threshold.' It can be regarded as a clever method for pruning the belief propagation computation tree, in such a way to exactly account for the effect of loops. In this paper we generalize the original algorithm to make it suitable for decoding linear codes, and discuss various schemes for pruning the computation tree. Further, we present the outcomes of numerical simulations on several linear codes, showing that tree pruning allows to interpolate continuously between belief propagation and maximum a posteriori decoding. Finally, we discuss theoretical implications of the new method.
AB - 'Tree pruning' (TP) is an algorithm for probabilistic inference on binary Markov random fields. It has been recently derived by Dror Weitz and used to construct the first fully polynomial approximation scheme for counting independent sets up to the 'tree uniqueness threshold.' It can be regarded as a clever method for pruning the belief propagation computation tree, in such a way to exactly account for the effect of loops. In this paper we generalize the original algorithm to make it suitable for decoding linear codes, and discuss various schemes for pruning the computation tree. Further, we present the outcomes of numerical simulations on several linear codes, showing that tree pruning allows to interpolate continuously between belief propagation and maximum a posteriori decoding. Finally, we discuss theoretical implications of the new method.
UR - http://www.scopus.com/inward/record.url?scp=84940644972&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84940644972&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84940644972
T3 - 45th Annual Allerton Conference on Communication, Control, and Computing 2007
SP - 322
EP - 329
BT - 45th Annual Allerton Conference on Communication, Control, and Computing 2007
PB - University of Illinois at Urbana-Champaign, Coordinated Science Laboratory and Department of Computer and Electrical Engineering
T2 - 45th Annual Allerton Conference on Communication, Control, and Computing 2007
Y2 - 26 September 2007 through 28 September 2007
ER -