The interest in our paper mainly stems from the great interest in "codes defined on graphs and iterative decoding," as these types of schemes—which include low-density parity-check codes, turbo codes, and other families—come very close to achieving the fundamental limits on code performance established by Claude Shannon, yet have reasonable decoding complexity. The issue of the IEEE Transactions on Information Theory in which our paper was published collects together many of the key papers in this area.

Factor graphs explicitly capture the factorization structure of a function of many variables. The sum product algorithm is an easy-to-describe procedure that operates on a factor graph by passing "messages" on the graph edges in order to compute various marginal functions associated with the represented function. Interestingly, in this framework one can capture a wide variety of algorithms, including the forward/backward algorithm, the Viterbi algorithm, the "turbo decoding" algorithm, Pearl's belief propagation algorithm; a version of the Kalman filter, and even certain Fast Fourier transform algorithms.

In the framework of factor graphs, a wide variety of important inference algorithms known by various names in different disciplines can all be seen as instances of the sum-product algorithm.

Frank R. Kschischang
Professor and Canada Research Chair
Edward S. Rogers Sr. Department of Electrical and Computer Engineering
University of Toronto