The generalized distributive law
- Creators
- Aji, Srinivas M.
- McEliece, Robert J.
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.
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.Files
| Name | Size | Download all |
|---|---|---|
|
md5:d8905aed71eaa51d4da107719a7ce432
|
410.3 kB | Preview Download |
Additional details
- Eprint ID
- 1541
- Resolver ID
- CaltechAUTHORS:AJIieeetit00
- Created
-
2006-01-28Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field