Iterative decoding of compound codes by probability propagation in graphical models

TLDR

Iterative decoding algorithms such as turbo decoding can be interpreted as probability propagation in a graphical model of the code. The paper proposes a unified graphical model framework to describe compound codes and derive iterative decoding algorithms. The authors derive a general distributed marginalization algorithm on factor graphs and demonstrate how Bayesian network descriptions of codes yield iterative decoders for parallel‑serial concatenated, product, and LDPC codes. This general algorithm recovers Pearl’s belief‑propagation algorithm as a special case.

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.