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.
Keywords
Sequential decodingDecoding methodsAlgorithmViterbi algorithmComputer scienceTheoretical computer scienceList decodingIterative Viterbi decodingBCJR algorithmBerlekamp–Welch algorithmConcatenated error correction codeBlock code
Affiliated Institutions
Related Publications
Codes and iterative decoding on general graphs
Abstract A general framework, based on ideas of Tanner, for the description of codes and iterative decoding (“turbo coding”) is developed. Just like trellis‐based code descripti...
A general algorithm for distributing information in a graph
We present a general "message-passing" algorithm for distributing information in a graph. This algorithm may help us to understand the approximate correctness of both the Gallag...
Codes and Decoding on General Graphs
Iterative decoding techniques have become a viable alternative for constructing high performance coding systems. In particular, the recent success of turbo codes indicates that ...
Iterative decoding of compound codes by probability propagation in graphical models
We present a unified graphical model framework for describing compound codes and deriving iterative decoding algorithms. After reviewing a variety of graphical models (Markov ra...
Factor graphs and the sum-product algorithm
Algorithms that must deal with complicated global functions of many variables often exploit the manner in which the given functions factor as a product of "local" functions, eac...
Publication Info
- Year
- 2000
- Type
- article
- Volume
- 46
- Issue
- 2
- Pages
- 325-343
- Citations
- 742
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
742
OpenAlex
89
Influential
403
CrossRef
Cite This
S.M. Aji,
Robert J. McEliece
(2000).
The generalized distributive law.
IEEE Transactions on Information Theory
, 46
(2)
, 325-343.
https://doi.org/10.1109/18.825794
Identifiers
- DOI
- 10.1109/18.825794