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]](http://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
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
