TP Decoding - Computer Science > Information TheoryReportar como inadecuado

TP Decoding - Computer Science > Information Theory - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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.

Autor: Yi Lu, Cyril Measson, Andrea Montanari


Documentos relacionados