Factor graphs and the sum-product algorithm
IEEE Transactions on Information TheoryPublished 1 January 2001
Frank R. Kschischang, Brendan J. Frey, Hans‐Andrea Loeliger
Citations6,481
SJR quartileQ1
SJR score1.46
SNIP1.76
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A generic message-passing algorithm, the sum-product algorithm, that operates in a factor graph, that computes-either exactly or approximately-various marginal functions derived from the global function.
Abstract
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 (1988) belief propagation algorithm for Bayesian networks, the Kalman filter, and certain fast Fourier transform (FFT) algorithms.
Keywords
Computer Science
Proceedings of the IEEEA tutorial on hidden Markov models and selected applications in speech recognition
22,785 Citations1989L. R. Rabiner
IEEE Transactions on Information TheoryLow-density parity-check codes
10,471 Citations1962Robert G. Gallager
A simple but nonoptimum decoding scheme operating directly from the channel a posteriori probabilities is described and the probability of error using this decoder on a binary symmetric channel is shown to decrease at least exponentially with a root of the block length.
Near Shannon limit error-correcting coding and decoding: Turbo-codes. 1
6,688 Citations2002Claude Berrou, Alain Glavieux +1 more
A new class of convolutional codes called turbo-codes, whose performances in terms of bit error rate (BER) are close to the Shannon limit, is discussed.
IEEE Transactions on Information TheoryOptimal decoding of linear codes for minimizing symbol error rate (Corresp.)
5,120 Citations1974L.R. Bahl, John Cocke +2 more
The general problem of estimating the a posteriori probabilities of the states and transitions of a Markov source observed through a discrete memoryless channel is considered and an optimal decoding algorithm is derived.
Journal of the Royal Statistical Society Series B (Statistical Methodology)Local Computations with Probabilities on Graphical Structures and Their Application to Expert Systems
3,970 Citations1988Steffen L. Lauritzen, David J. Spiegelhalter
This work exploits a range of local representations for the joint probability distribution, combined with topological changes to the original network termed 'marrying' and 'filling-in', which allows efficient algorithms for transfer between representations, providing rapid absorption and propagation of evidence.
IEEE Transactions on Information TheoryGood error-correcting codes based on very sparse matrices
3,690 Citations1999David Mackay
IEEE Transactions on Information TheoryA recursive approach to low complexity codes
3,099 Citations1981R. Michael Tanner
It is shown that choosing a transmission order for the digits that is appropriate for the graph and the subcodes can give the code excellent burst-error correction abilities.
Introduction to Bayesian Networks
2,585 Citations2019
Discrete mathematics and its applicationsDiscrete Mathematics and Its Applications
1,610 Citations2010
Graphical ModelsLearning and Relearning in Boltzmann Machines
1,052 Citations2001Geoffrey E. Hinton, T. J. Sejnowski
This chapter contains sections titled: Relaxation Searches, Easy and Hard learning, The Boltzmann Machine Learning Algorithm, An Example of Hard Learning, Achieving Reliable Computation with Unreliable Hardware, and an Example of the Effects of Damage.
Codes and Decoding on General Graphs
908 Citations1996N. Wiberg
It is showed that many iterative decoding algorithms are special cases of two generic algorithms, the min-sum and sum-product algorithms, which also include non-iterative algorithms such as Viterbi decoding.
IEEE Journal on Selected Areas in CommunicationsTurbo decoding as an instance of Pearl's "belief propagation" algorithm
905 Citations1998Robert J. McEliece, David Mackay +1 more
It is shown that Pearl's algorithm can be used to routinely derive previously known iterative, but suboptimal, decoding algorithms for a number of other error-control systems, including Gallager's low-density parity-check codes, serially concatenated codes, and product codes.
IEEE Transactions on Information TheoryThe generalized distributive law
754 Citations2000S.M. Aji, Robert J. McEliece
Although this algorithm is guaranteed to give exact answers only in certain cases (the "junction tree" condition), unfortunately not including the cases of GTW with cycles or turbo decoding, there is much experimental evidence, and a few theorems, suggesting that it often works approximately even when it is not supposed to.
IEEE Transactions on Information TheoryCodes on graphs: normal realizations
659 Citations2001G. David Forney
Discrete mathematics and its applicationsHandbook of Discrete and Combinatorial Mathematics
473 Citations1999
Computers & Mathematics with ApplicationsGraphical models for machine learning and digital communication
465 Citations1999
Lecture notes in computer scienceGood codes based on very sparse matrices
443 Citations1995David Mackay, Radford M. Neal
A new family of error-correcting codes for the binary symmetric channel is presented, designed to encode a sparse source, and are defined in terms of very sparse invertible matrices, in such a way that the decoder can treat the signal and the noise symmetrically.
Cambridge University Press eBooksGibbs States on Countable Sets
432 Citations1974Christopher J. Preston
Dynamics reportedModels for Dynamics
419 Citations1989Jan C. Willems
The purpose of this paper is to give a tutorial exposition of what the authors consider to be the basic mathematical concepts in the theory of dynamical systems.
IEEE Journal on Selected Areas in CommunicationsIterative decoding of compound codes by probability propagation in graphical models
387 Citations1998Frank R. Kschischang, Brendan J. Frey
It is pointed out that iterative decoding algorithms for various codes, including "turbo decoding" of parallel-concatenated convolutional codes, may be viewed as probability propagation in a graphical model of the code.
The MIT Press eBooksGraphical Models for Machine Learning and Digital Communication
353 Citations1998Brendan J. Frey
European Transactions on TelecommunicationsCodes and iterative decoding on general graphs
316 Citations1995N. Wiberg, Hans‐Andrea Loeliger +1 more
International Statistical ReviewAn Introduction to Spatial Point Processes and Markov Random Fields
78 Citations1981Valerie Isham
The role of Markov random fields as equilibrium processes for the temporal evolution of spatial processes is discussed and various applications and examples are given.
IEEE Transactions on CommunicationsInterleaver properties and their applications to the trellis complexity analysis of turbo codes
55 Citations2001Roberto Garello, G. Montorsi +2 more
The basic theory of interleaver behavior is revisited in a semi-tutorial manner, and extended to encompass noncausal interleavers, and a procedure of complexity reduction by coordinate permutation is presented.
A general algorithm for distributing information in a graph
9 Citations2002S.M. Aji, Robert J. McEliece
A general "message-passing" algorithm for distributing information in a graph that may help to understand the approximate correctness of both the Gallager-Tanner-Wiberg algorithm, and the turbo-decoding algorithm.