Journal
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume 47, Issue 2, Pages 498-519Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/18.910572
Keywords
belief propagation; factor graphs; fast Fourier transform; forward/backward algorithm; graphical models; iterative decoding; Kalman filtering; marginalization; sum-product algorithm; Tanner graphs; Viterbi algorithm
Ask authors/readers for more resources
Algorithms that must deal with complicated global functions of many variables often exploit the manner in which the given functions factor as a product of local functions, each of which depends on a subset of the variables. Such a factorization can be visualized with a bipartite graph that we call a factor graph. In this tutorial paper, we present a generic message-passing algorithm, the sum-product algorithm, that operates in a factor graph, Following a single, simple computational rule, the sum-product algorithm computes-either exactly or approximately-various marginal functions derived from the global function. A wide variety of algorithms developed in artificial intelligence, signal processing, and digital communications can be derived as specific instances of the sum-product algorithm, including the forward/backward algorithm, the Viterbi algorithm, the iterative turbo decoding algorithm, Pearl's belief propagation algorithm for Bayesian networks, the Kalman filter, and certain fast Fourier transform (FFT) algorithms.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available