TP Decoding

Details TP Decoding TP Decoding

2007-10-02

arxiv.org/abs/0710.0564v1

See also: 45th Annual Allerton Conference on Communication, Control, and Computing, Monticello, USA, 2007

Computer Science

Information Theory

8 pages, 9 figures

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

TP Decoding does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with TP Decoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and TP Decoding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-7645