XDU, Fall 2011 Lecture Notes 4.6 Behavioral Models of Codes and Factor Graph Representation

It is well known that turbo codes, LDPC codes, and repeat-accumulate (RA) codes can approach Shannon limit very closely. A common feature of these capacity-approaching coding schemes is that they all may be understood as codes defined on graphs. In this section, we will introduce the subject of codes on graphs. As we will see, (factor) graphs provide a means of visualizing the constraints that define the code. Moreover, the graphs directly specify iterative decoding algorithms. 4.6.1 Codes and Behavioral Modeling Let nqF denote the vector space of all n-tuples over a finite field Fq. We know that a linear (n, k, d) block code can be represented by several methods: By a set of k generators {gj, 1≤j≤k}. The code { | ,}nq j j j q j a a = ∈ = ∈∑x x gF FC. By a set of (n-k) generators {hj, 1≤j≤n-k} for the dual code. The code C is then { | , 0 for all}nq j j = ∈ <>=x x hFC By a trellis representation. The code C is then the set of all n-tuples corresponding to paths through the trellis. In the following we will see that these representations are all special cases of a general class of representations called behavioral realizations. We will use the following notation. A symbol variable Xi takes values i ix ∈X in a symbol alphabet Xi. In coding, Xi is often a vector space over a finite field, e.g., mqF, and xi are the corresponding m-tuples. A symbol configuration space X is a Cartesian product i i I