Abstract
We present a unified graphical model framework for describing compound codes and deriving iterative decoding algorithms. After reviewing a variety of graphical models (Markov random fields, Tanner graphs, and Bayesian networks), we derive a general distributed marginalization algorithm for functions described by factor graphs. From this general algorithm, Pearl's (1986) belief propagation algorithm is easily derived as a special case. We point out that iterative decoding algorithms for various codes, including "turbo decoding" of parallel-concatenated convolutional codes, may be viewed as probability propagation in a graphical model of the code. We focus on Bayesian network descriptions of codes, which give a natural input/state/output/channel description of a code and channel, and we indicate how iterative decoders can be developed for parallel-and serially concatenated coding systems, product codes, and low-density parity-check codes.
Keywords
Factor graphComputer scienceBelief propagationSerial concatenated convolutional codesGraphical modelTurbo codeConcatenated error correction codeSequential decodingAlgorithmTheoretical computer scienceDecoding methodsConvolutional codeLow-density parity-check codeList decodingBlock codeArtificial intelligence
Affiliated Institutions
Related Publications
Turbo decoding as an instance of Pearl's "belief propagation" algorithm
We describe the close connection between the now celebrated iterative turbo decoding algorithm of Berrou et al. (1993) and an algorithm that has been well known in the artificia...
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...
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 ...
Using Linear Programming to Decode Binary Linear Codes
A new method is given for performing approximate maximum-likelihood (ML) decoding of an arbitrary binary linear code based on observations received from any discrete memoryless ...
Publication Info
- Year
- 1998
- Type
- article
- Volume
- 16
- Issue
- 2
- Pages
- 219-230
- Citations
- 386
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
386
OpenAlex
22
Influential
277
CrossRef
Cite This
Frank R. Kschischang,
Brendan J. Frey
(1998).
Iterative decoding of compound codes by probability propagation in graphical models.
IEEE Journal on Selected Areas in Communications
, 16
(2)
, 219-230.
https://doi.org/10.1109/49.661110
Identifiers
- DOI
- 10.1109/49.661110