The generalized distributive law

In this semitutorial paper we discuss a general message passing algorithm, which we call the generalized distributive law (GDL). The GDL is a synthesi s of the work of many authors in the information theory, digital communicat ions, signal processing, statistics, and artificial intelligence communitie s. It includes as special cases the Baum-Welch algorithm, the fast Fourier transform (FFT) on any finite Abelian group, the Gallager-Tanner-Wiberg dec oding algorithm, Viterbi's algorithm, the BCJR algorithm, Pearl's "belief p ropagation" algorithm, the Shafer-Shenoy probability propagation algorithm, and the turbo decoding algorithm, 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 i t often works approximately even when it is not supposed to.