eeE,e的一个端，点属于K,另一个端点属于乃，则称G为二部图(bipartite graph). 若节点集匕中所有节点的度数都相同并且节点集，中所有节点的度数也都相同，则称G 为正则二部图(regular bipartite graph),否则称为非正则二部图(irregular bipartite graph), A cycle is a subgraph C=(VE)ofG=(V,E),whose vertices can be placed around a circle.The length ofa cycle Cis defined as /(C)E The girth of is the length of its shortest:g(G)C)where Cis the collection of all the cycles of G. A Tanmer graph is a bipartite graph in which a first set of vertices represents the symbol variables i,a second set of vertices represents the local constraints (C,ke),and an edge connects a variable vertex to a constraint vertex if and only if (iff)the corresponding symbol variable is volved in the ding local c aint.Fig.4.6.2 shows a Tanne graph for the (84,4)RMcode defined by the parity-check matrix 11110000 (4.1) 00001111 X0● 1●人 H ●大 为●< 狂 4● 5● H 6●Y 为● Fig.4.6.2 Tanner graph of parity-check representation for(8,4,4)code Here,symbol variables are represented by filled circles,and constraints (checks)by squares labeled by a+'sign.The four check nodes (vertices)represent the binary linear equations that each codeword must satisfy.In a valid codeword,the neighbors of every check4 ∀e∈ E ，e 的一个端点属于V1，另一个端点属于V2 ，则称G 为二部图(bipartite graph)。 若节点集V1中所有节点的度数都相同并且节点集V2 中所有节点的度数也都相同,则称G 为正则二部图(regular bipartite graph)，否则称为非正则二部图(irregular bipartite graph)。 „ A cycle is a subgraph ( ', ') of ( , ) C V E G VE = = , whose vertices can be placed around a circle. The length of a cycle C is defined as ( ) | ' | | ' | lC V E = = . „ The girth of G is the length of its shortest cycle: ( ) min ( ) { } C gG lC ∈ = C , where C is the collection of all the cycles of G. A Tanner graph is a bipartite graph in which a first set of vertices represents the symbol variables {Xi, i∈I}, a second set of vertices represents the local constraints {Ck, k∈K}, and an edge connects a variable vertex to a constraint vertex if and only if (iff) the corresponding symbol variable is involved in the corresponding local constraint. Fig. 4.6.2 shows a Tanner graph for the (8, 4, 4) RM code defined by the parity-check matrix 11110000 01011010 00111100 00001111 ⎡ ⎤ ⎢ ⎥ = ⎣ ⎦ H (4.1) x0 x1 x2 x3 x4 x5 x6 x7 Fig. 4.6.2 Tanner graph of parity-check representation for (8, 4, 4) code. Here, symbol variables are represented by filled circles, and constraints (checks) by squares labeled by a ‘+’ sign. The four check nodes (vertices) represent the binary linear equations that each codeword must satisfy. In a valid codeword, the neighbors of every check