This chapter introduces a new code description. We first develop a graphical representation for the factorization of a function of several variables into a product of functions of a lower number of variables. This representation allows us to derive efficient algorithms for computing the marginals of the original function with respect to any one of its variables. Given a function describing membership in a code C . its marginalization leads to a method for decoding C . Thus, graphical representations of codes provide a natural setting for the description of symbol-by-symbol decoding techniques, much as the code trellis is a natural setting for the description of maximum-likelihood decoding using the Viterbi algorithm. This chapter is centered on these representations of codes and on a general procedure (the sum-product algorithm) for their decoding. The importance of the theory presented here lies in the fact that all known codes that approach capacity and are practically decodable admit a simple graphical representation. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
This chapter introduces a new code description. We first develop a graphical representation for the factorization of a function of several variables into a product of functions of a lower number of variables. This representation allows us to derive efficient algorithms for computing the marginals of the original function with respect to any one of its variables. Given a function describing membership in a code C . its marginalization leads to a method for decoding C . Thus, graphical representations of codes provide a natural setting for the description of symbol-by-symbol decoding techniques, much as the code trellis is a natural setting for the description of maximum-likelihood decoding using the Viterbi algorithm. This chapter is centered on these representations of codes and on a general procedure (the sum-product algorithm) for their decoding. The importance of the theory presented here lies in the fact that all known codes that approach capacity and are practically decodable admit a simple graphical representation. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
Iterative decoding techniques have become a viable alternative for constructing high performance coding systems. In particular, the recent success of turbo codes indicates that performance close to the Shannon limit may be achieved. In this thesis, it is showed that many iterative decoding algorithms are special cases of two generic algorithms, the min-sum and sum-product algorithms, which also include non-iterative algorithms such as Viterbi decoding. The min-sum and sum-product algorithms are developed and presented as generalized trellis algorithms, where the time axis of the trellis is replaced by an arbitrary graph, the "Tanner graph". With cycle-free Tanner graphs, the resulting decoding algorithms (e.g., Viterbi decoding) are maximum-likelihood but suffer from an exponentially increasing complexity. Iterative decoding occurs when the Tanner graph has cycles (e.g., turbo codes); the resulting algorithms are in general suboptimal, but significant complexity reductions are possible compared to the cycle-free case. Several performance estimates for iterative decoding are developed, including a generalization of the union bound used with Viterbi decoding and a characterization of errors that are uncorrectable after infinitely many decoding iterations.
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 a realization has leaf edges representing symbols, ordinary edges representing states, and vertices representing local constraints. Such a graph can be decoded by any version of the sum-product algorithm. Any state realization of a code can be put into normal form without essential change in the corresponding graph or in its decoding complexity. Group or linear codes are generated by group or linear state realizations. On a cycle-free graph, there exists a well-defined minimal canonical realization, and the sum-product algorithm is exact. However, the cut-set bound shows that graphs with cycles may have a superior performance-complexity tradeoff, although the sum-product algorithm is then inexact and iterative, and minimal realizations are not well-defined. Efficient cyclic and cycle-free realizations of Reed-Muller (RM) codes are given as examples. The dual of a normal group realization, appropriately defined, generates the dual group code. The dual realization has the same graph topology as the primal realization, replaces symbol and state variables by their character groups, and replaces primal local constraints by their duals. This fundamental result has many applications, including to dual state spaces, dual minimal trellises, duals to Tanner (1981) graphs, dual input/output (I/O) systems, and dual kernel and image representations. Finally a group code may be decoded using the dual graph, with appropriate Fourier transforms of the inputs and outputs; this can simplify decoding of high-rate codes.
Until recently, most known decoding procedures for error-correcting codes were based either on algebraically calculating the error pattern or on some sort of tree or trellis search. With the advent of turbo coding, a third decoding principle has finally had its breakthrough: iterative decoding. With respect to Viterbi decoding, a code is most naturally described by means of a trellis diagram. The main thesis of the present paper is that, with respect to iterative decoding, the natural way of describing a code is by means of a Tanner graph, which may be viewed as a generalized trellis. More precisely, it is the "time axis" of a trellis that is generalized to a Tanner graph.
A growing interest in the theory and application of iterative decoding algorithms was ignited by the impressive bit-error rate performance of the turbo-decoding algorithm demonstrated by Berrou et al. [3]. In the last several years, the turbo decoding algorithm has been generalized and mathematically formulated using a graph-theoretic approach. Such iterative decoding algorithms operate by “messagepassing” in graphs associated with codes and hence, they are referred to as the message-passing algorithms. The theory of codes on graphs has helped to improve the error performance of low-complexity decoding schemes. Also, it has opened new research avenues for investigating alternative suboptimal decoding schemes. One of the key results in the theory of codes on graphs comes from Kschischang et al. [8,9]. They generalized the concept of codes on graphs by introducing the idea of general functions on graphs. They derived a general distributed marginalization algorithm for function described by factor graphs. The theory of factor graphs and the sum-product algorithm generalizes a variety of algorithms developed in computer science and engineering. The belief propagation algorithm, developed by Pearl [14], operating on Bayesian networks is an instance of the sum-product algorithm operating on an appropriate factor graph.
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.
We consider two graph-based techniques for correcting the errors introduced into a transmission by a noisy channel. In the first technique, which is based on decoding with a layered graph known as a trellis, we examine a generalization of heuristically good codes called lexicodes. We propose and analyze a method for designing generalized lexicodes that minimize or constrain various trellis decoding parameters. The second technique is based on decoding with factor graphs, which Are typically smaller than trellis representations and have enjoyed Much attention in the recent literature. We look at a specific type of factor graphs known as Tanner graphs, for which a decoding algorithm is known. This decoding algorithm has been proven to converge always to a maximum-likelihood decoding if and only if the corresponding Tanner graph is cycle-free. However, we show that cycle-free Tannergraphs cannot support good codes, because of their weak structure. This weakness has a direct affect on codes of Tanner graphs with cycles, which we analyze as well.