Abstract
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 Gallager-Tanner-Wiberg algorithm, and the turbo-decoding algorithm.
Keywords
Computer scienceCorrectnessTheoretical computer scienceDecoding methodsGraphMessage passingAlgorithmParallel computing
Affiliated Institutions
Related Publications
The generalized distributive law
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, d...
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...
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...
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 ...
Good error-correcting codes based on very sparse matrices
We study two families of error-correcting codes defined in terms of very sparse matrices. "MN" (MacKay-Neal (1995)) codes are recently invented, and "Gallager codes" were first ...
Publication Info
- Year
- 2002
- Type
- article
- Pages
- 6-6
- Citations
- 9
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
9
OpenAlex
3
Influential
8
CrossRef
Cite This
S.M. Aji,
Robert J. McEliece
(2002).
A general algorithm for distributing information in a graph.
Proceedings of IEEE International Symposium on Information Theory
, 6-6.
https://doi.org/10.1109/isit.1997.612921
Identifiers
- DOI
- 10.1109/isit.1997.612921