An introduction to factor graphs

Graphical models such as factor graphs allow a unified approach to a number of key topics in coding and signal processing such as the iterative decoding of turbo codes, LDPC codes and similar codes, joint decoding, equalization, parameter estimation, hidden-Markov models, Kalman filtering, and recursive least squares. Graphical models can represent complex real-world systems, and such representations help to derive practical detection/estimation algorithms in a wide area of applications. Most known signal processing techniques -including gradient methods, Kalman filtering, and particle methods -can be used as components of such algorithms. Other than most of the previous literature, we have used Forney-style factor graphs, which support hierarchical modeling and are compatible with standard block diagrams.

Introduction

Engineers have always liked graphical models such as circuit diagrams, signal flow graphs, trellis diagrams, and a variety of block diagrams. In artificial intelligence, statistics, and neural networks, stochastic models are often formulated as Bayesian networks or Markov random fields. In coding theory, the iterative decoding of turbo codes and similar codes may also be understood in terms of a graphical model of the code.