Chapter 8 Trellis and graph based codes基于网格和图形的编码

Chapter 8

Trellis and Graph Based Codes

The main content of

Chapter 8

Trellis based codes:

Convolutional codes

Turbo codes

Graph based codes:

LDPC codes

For these codes, soft decision decoding is possible and near channel capacity performance is achievable.

8-1 The Structure of Convolutional Codes (CC)

Fig 8.1-2, K=3, k=1, n=3,

convolutional coder Figure 8.1-2，the function generators are ：g1=[100], g2=[101], g3=[111] or （4,5,7）

They are the impulse responses from the encoder input to the three outputs.

11

1

1

()(1)1(2)2(3)3

(1)(2)(3)(1)(2)(3)11122

2When the input to the encoder is the information sequence , the three output are

,,,,,................In the transform domain , where D denot =*=*=*=u c

u g c

u g c u g c c c c c c c D -112

223es the and D=z ,

g ()1

g (unit delay )1g ()1D D D D D D ==+=++

(1)

1(2)

2(3)3(1)3(2)32(3)3()The output transforms are c ()()()c ()()()c ()()(),

The transform of the output code sequence :()c ()c ()c ()i i i D u D

D D g D D D g D D D g D D D D D D D ￥======++?u u u u c c Due to interleaving!Due to delay!

Example 8.1-1

Fig 8.1-2, CC with

K=3, k=1, n=3345

12223(1)3451(2)

234672(3)2357

3(1)3(2)32(3)32(100111)

()1()1

()1()1()()()1()()()1()()()1()()()() =1+D +D +u D D D D

g D g D D

g D D D

c D u D g D D D D c D u D g D D D D D D c D u D g D D D D D D c D c D D c D D c D ==+++==+=++==+++==+++++==+++++=++=u 5789101112131517192223D +D +D +D +D +D +D +D +D +D +D +D +D ()c +

=111001011111110101010011100111001011101111110101

8.1-1 Tree，Trellis，and State Diagrams Three alternative methods to describe a CC: (1)Tree diagram: Fig 8.1-5 with 8.1-2,

repeat after K stages;

(2) Trellis diagram: Fig 8.1-6 with 8.1-2,

steady states after K stages.

States means the states of first (K-1)th stages of shift registers.

Fig 8.1-2, K=3, k=1, n=3, convolutional coder

8.1-6 Trellis diagram K=3, k=1, n=300

01

1

1011

Duo to “1”

Generally for a convolutional code:

1. The number of states (nodes) is 2k(K-1);

2. For each node we have 2k branches in, 2k branches out;

3. For each stage we have 2k(K-1)2k =2kK path metrics and 2k(K-1)survivors with Viterbi decoding algorithm.

(3) State diagram: for Fig. 8.1-2 CC

Fig 8.1-7 state diagram

K=3, k=1, n=3

?For k＞1, Fig 8.1-3 as an example, we have Fig 8.1-8 for tree diagram, Fig 8.1-9 for trellis diagram and Fig 8.1-10 for state diagram.

?For non binary convolution encoder: Fig 8.1-11.

8.1-2 The transfer function of a

convolutional code

we can add distance properties in the

state diagram of a specific CC to get its very useful transfer function.

As an example, Fig 8.1-12 is such a state diagram with distance properties for the

CC (1,3,3) shown in Fig 8.1-2 (Fig 8.1-7

is its original state diagram).

3

2

2

2state equations 8.1Look at the for each states we have four Z Solving the state equations we have the -17transfer function

C a b b c d d c d e b

X X ZX X ZX ZX X Z X Z X X Z X =+=+=+=entering branches （）

·

·

·

·

·a

c

d

3

Z

2

Z 2

Z Z

2

Z Z

Z

Fig 8.1-12

distance properties, to (000)

(8.1-17)

From Fig 8.1-12 we can get the state equations, and further have the transfer Functions:

(6)/26

26810126 (Z)/ 12 248

2(even d)w here, 0

(odd d) T erm s in the transfer function m ean that d e a

d d d d T X X Z Z

Z Z Z Z a

Z a -￥===-=++++=ì=í??d there ar a pathes from st e ate a L

, e.g., there only one path (acbe) from state a to e has distance 6 to all zero path.

T he 6 here is the m inim um free distance of this code. to e d to w ith distance

all zero path

Further,

we can add the additional properties for

the trellis diagram

3

2

2

23

62

36

42

8

52

8

5310

Thus 8.17 becom es 8.1-20 for CC in Fig 8.1-2Z The transfer function becom es (8.1-21):(,,)/1(1)

C a b b c d d c d e b

e a X JY X JYZX X JZX JZX X JYZ X JYZ X X JZ X T Y Z J X X J YZ

JYZ J J YZ J Y Z J Y Z J Y Z =+=+=+===-+=++++（）（）：6310

7310

2J Y Z J Y Z ++L

·

·

·

·

·c

d

2

J Z 2

JYZ JZ

JZ

JYZ

2

JYZ 3

JYZ

a

Figure 8.1-13

Y: Duo to 1

J: # of branches

Then, we have added the additional properties for the transitions from a to e:

1.The power of Y: The # of branches of the path

with d distance from a to e due to input of “1”;

2. The power of J : The # of branches of the path with d distance from a to e.

The first term in (8.1-21) is . It means:

there is only one path from a to e with distance 6to all zero path, and in this path there is

only one branch duo to input of “1”, and there are total 3 branches in this path .

It is easy to extend to nonbinary codes (Fig 8.1-14, and Fig 8.1-15) from Fig. 8.1-11.

?catastrophic error propagation code:

The state diagram will contain a zero distance path transition from some nonzero state back to the same state (Fig 8.1-17,18).

Finite channel errors cause infinite decode errors.361 J YZ ′

8.1-3 Systematic, Nonrecursive, and recursive CC

1.Systematic CC (SCC):

The information sequence directly appears as part of the code sequence.

Generally, if G(D) is of the form ,where P(D) is a k ×(n-k) polynomial matrix, the CC is systematic.)k =éù??

G(D)I P(D

本文来源：https://www.bwwdw.com/article/vmbl.html