Abstract

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 descriptions are naturally matched to Viterbi decoding, code descriptions based on Tanner graphs (which may be viewed as generalized trellises) are naturally matched to iterative decoding. Two basic iterative decoding algorithms (which are versions of the algorithms of Berrou et al. and of Hagenauer, respectively) are shown to be natural generalizations of the forward‐backward algorithm (Bahl et al.) and the Viterbi algorithm, respectively, to arbitrary Tanner graphs. The careful derivation of these algorithms clarifies, in particular, which a priori probabilities are admissible and how they are properly dealt with. For cycle codes (a class of binary linear block codes), a complete characterization is given of the error patterns that are corrected by the generalized Viterbi algorithm after infinitely many iterations.

Keywords

Iterative Viterbi decodingTanner graphViterbi algorithmSequential decodingAlgorithmTurbo codeDecoding methodsViterbi decoderComputer scienceList decodingSoft output Viterbi algorithmConvolutional codeBlock codeTheoretical computer scienceLinear codeMathematicsConcatenated error correction code

Affiliated Institutions

Related Publications

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 ...

1996 908 citations

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...

2000 IEEE Transactions on Information Theory 742 citations

Codes on graphs: normal realizations

A generalized state realization of the Wiberg (1996) type is called normal if symbol variables have degree 1 and state variables have degree 2. A natural graphical model of such...

2001 IEEE Transactions on Information Theory 656 citations

Publication Info

Year
1995
Type
article
Volume
6
Issue
5
Pages
513-525
Citations
312
Access
Closed

External Links

Social Impact

Social media, news, blog, policy document mentions

Citation Metrics

312
OpenAlex

Cite This

N. Wiberg, Hans‐Andrea Loeliger, Ralf Kötter (1995). Codes and iterative decoding on general graphs. European Transactions on Telecommunications , 6 (5) , 513-525. https://doi.org/10.1002/ett.4460060507

Identifiers

DOI
10.1002/ett.4460060507