CaltechAUTHORS
  A Caltech Library Service

The generalized distributive law

Aji, Srinivas M. and McEliece, Robert J. (2000) The generalized distributive law. IEEE Transactions on Information Theory, 46 (2). pp. 325-343. ISSN 0018-9448. http://resolver.caltech.edu/CaltechAUTHORS:AJIieeetit00

[img]
Preview
PDF
See Usage Policy.

400Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:AJIieeetit00

Abstract

We discuss a general message passing algorithm, which we call the generalized distributive law (GDL). The GDL is a synthesis of the work of many authors in information theory, digital communications, signal processing, statistics, and artificial intelligence. It includes as special cases the Baum-Welch algorithm, the fast Fourier transform (FFT) on any finite Abelian group, the Gallager-Tanner-Wiberg decoding algorithm, Viterbi's algorithm, the BCJR algorithm, Pearl's “belief propagation” 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 it often works approximately even when it is not supposed to.


Item Type:Article
Additional Information:© Copyright 2000 IEEE. Reprinted with permission. Manuscript received July 8, 1998; revised September 23, 1999. This work was supported by NSF under Grant NCR-9505975, AFOSR under Grant 5F49620-97-1-0313, and a Grant from Qualcomm. A portion of McEliece’s contribution was performed at the Sony Corporation in Tokyo, Japan, while he was a holder of a Sony Sabbatical Chair. Preliminary versions of this paper were presented at the IEEE International Symposium on Information Theory, Ulm, Germany, June 1997, and at ISCTA 1997, Ambleside U.K., July 1997. Communicated by F. R. Kschischang, Associate Editor for Coding Theory.
Subject Keywords:Belief propagation, distributive law, graphical models, junction trees, turbo codes, decoding, graph theory, message passing
Record Number:CaltechAUTHORS:AJIieeetit00
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:AJIieeetit00
Alternative URL:http://dx.doi.org/10.1109/18.825794
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1541
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:28 Jan 2006
Last Modified:26 Dec 2012 08:44

Repository Staff Only: item control page