TP Decoding - Computer Science > Information TheoryReport as inadecuate

TP Decoding - Computer Science > Information Theory - Download this document for free, or read online. Document in PDF available to download.

Abstract: `Tree pruning- TP is an algorithm for probabilistic inference on binaryMarkov random fields. It has been recently derived by Dror Weitz and used toconstruct the first fully polynomial approximation scheme for countingindependent sets up to the `tree uniqueness threshold.- It can be regarded as aclever method for pruning the belief propagation computation tree, in such away to exactly account for the effect of loops.In this paper we generalize the original algorithm to make it suitable fordecoding linear codes, and discuss various schemes for pruning the computationtree. Further, we present the outcomes of numerical simulations on severallinear codes, showing that tree pruning allows to interpolate continuouslybetween belief propagation and maximum a posteriori decoding. Finally, wediscuss theoretical implications of the new method.

Author: Yi Lu, Cyril Measson, Andrea Montanari


Related documents