期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 47, 期 2, 页码 498-519出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/18.910572
关键词
belief propagation; factor graphs; fast Fourier transform; forward/backward algorithm; graphical models; iterative decoding; Kalman filtering; marginalization; sum-product algorithm; Tanner graphs; Viterbi algorithm
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据