A factor graph is a bipartite graph that expresses how a "global" function of several variables factors into a product of "local" functions. In this tutorial talk, we describe a generic message-passing algorithm-the sum-product algorithm-that operates in a factor graph. It turns out that many algorithms, including Pearl's belief propagation algorithm, Viterbi's algorithm, certain fast Fourier transform algorithms, the forward/backward BCJR algorithm, and the turbo decoding algorithm, can be viewed as specific instances of the sum-product algorithm. We briefly describe the relationships between factor graphs and the "generalized distributive law" approach taken by Aji and McEliece.

[This talk is the result of joint work with Brendan Frey and Hans-Andrea Loeliger].

Slides used during the talk

Back to Codes, Systems and Graphical Models