Factor Graphs

Belief propagation and many algorithms used in digital communications and signal processing are all representations of a more general message-passing algorithm, the sum-product algorithm, operating on factor graphs. This algorithm computes marginals of a global probabilistic function in terms of local functions. The factor graph of a code is a visual expression of this factorization into local probabilistic functions. Aji and McEliece present an equivalent but alternative formulation with their generalized distributive law (GDL). In this chapter we discuss the sum-product algorithm after examining graphical models for probabilistic inference.