TP decoding

Yi Lu, Cyril Méasson, Andrea Montanari

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

'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.

Original languageEnglish (US)
Title of host publication45th Annual Allerton Conference on Communication, Control, and Computing 2007
PublisherUniversity of Illinois at Urbana-Champaign, Coordinated Science Laboratory and Department of Computer and Electrical Engineering
Pages322-329
Number of pages8
ISBN (Electronic)9781605600864
StatePublished - Jan 1 2007
Externally publishedYes
Event45th Annual Allerton Conference on Communication, Control, and Computing 2007 - Monticello, United States
Duration: Sep 26 2007Sep 28 2007

Publication series

Name45th Annual Allerton Conference on Communication, Control, and Computing 2007
Volume1

Other

Other45th Annual Allerton Conference on Communication, Control, and Computing 2007
CountryUnited States
CityMonticello
Period9/26/079/28/07

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'TP decoding'. Together they form a unique fingerprint.

  • Cite this

    Lu, Y., Méasson, C., & Montanari, A. (2007). TP decoding. In 45th Annual Allerton Conference on Communication, Control, and Computing 2007 (pp. 322-329). (45th Annual Allerton Conference on Communication, Control, and Computing 2007; Vol. 1). University of Illinois at Urbana-Champaign, Coordinated Science Laboratory and Department of Computer and Electrical Engineering.