0122229现代数字通信与编码理论 November 10,2011 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) gapsprovide a means of visualizing the ts that defe the code Morverhe graphs directly specify iterative decoding algorithms. 4.6.1 Codes and Behavioral Modeling Let F"denote the vector space of all n-tuples over a finite field F We know that a linear(n)block code can be represented by several methods: ■By a set ofk generators{g,lssk.The code C=∈Fglx=∑a,g,a,∈F,} By a set of (n-k)generators (h.Isjsn-k for the dual code.The code C is then C=xEFkx,h >=0 for allj By a trellis representation.The code Cis then the set of all n-tuples corresponding to paths through the trellis. In the following we will see that these repre esentations are all special cases of a general class of representations called behavioral We will use the following notation.A symbol variable X;takes values x,in a symbol alphabet In coding,is often a vector space over a finite field,e.g,F,and x are the corresponding m-tuples.A symbol configuration space is a Cartesian product x=Π光 of a collectioni of symbol alphabets,where Z is any discrete index set(called symbol index ser).The elements of are denoted byx=,and will be called symbol configurations.In other words.a configuration is a particular assignment of values to all variables.The configuration space is the set of configurations. 1 0122229 现代数字通信与编码理论 November 10, 2011 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 n F q 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 {| , } n q jj j q j C =∈ = ∈ xx g F F ∑a a . „ By a set of (n-k) generators {hj, 1≤j≤n-k} for the dual code. The code C is then { | , 0 for all } n q j C = ∈ < >= x xh F j „ 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 i x ∈X in a symbol alphabet Xi. In coding, Xi is often a vector space over a finite field, e.g., m F q , and xi are the corresponding m-tuples. A symbol configuration space X is a Cartesian product i i I ∈ X X =∏ of a collection {Xi, i∈I} of symbol alphabets, where I is any discrete index set (called symbol index set). The elements of X are denoted by { , } i i x = x i ∈ ∈∈ X IX , and will be called symbol configurations. In other words, a configuration is a particular assignment of values to all variables. The configuration space is the set of configurations