Error Correction Code (2)

(1)

Error Correction Code (2)

Fire Tom Wada

Professor, Information

Engineering, Univ. of the Ryukyus

(2)

Two major FEC technologies

1.

Reed Solomon code (Block Code)

2.

Convolutional code

3.

Serially concatenated code

Source Information

Reed Solomon

Code

Interleaving Convolution Code

Concatenated Coded

Goes to Storage, Transmission Concatenated

(3)

(n, k) Block Code

 Time t information block i_t is coded to time t code w_t.

 k : information length

 n : code length

i

_t-2

k bit

i

_t-1

k bit

i

_t

k bit Information

code

w

_t-2

n bit

w

_t-1

n bit

w

_t

n bit

ENCODE ENCODE ENCODE

BLOCK

(4)

Convolutional Code

 Time t code w_tis determined by past K information.

 K : Constraint length

 Code Rate : R=k/n

i

_t-2

k bit

i

_t-1

k bit

i

_t

k bit Information

code

w

_t-2

n bit

w

_t-1

n bit

w

_t

n bit Constraint length K

(5)

Simple Convolutional Coder



2 1 0

i i

i c

10

c

11

c

12



22 21

20

c c c

t t

t

t t

i D

D i

i i

c

i D

i i

c

) 1

( ) 1

(

2 2

1 2

2 2

1



















　 D is delay operator

 　 c , c depends on not only current it bu also past i , i

(6)

Simple Convolutional Coder(2)

Time t 0 1 2 3 4 5

i_t 1 1 0 0 1 0

F1=i_t-1 0 1 1 0 0 1

F2=i_t-2 0 0 1 1 0 0

c_1t 1 1 1 1 1 0

c_2t 1 0 0 1 1 1

 If input information is “110010” then

 Output code is “11 10 10 11 11 01”.

 Constraint length K=3, R=1/2

(7)

State Transition Diagram

 Number of State: 4

Time t 0 1 2 3 4 5

i_t 1 1 0 0 1 0

F1=i_t-1 0 1 1 0 0 1

F2=i_t-2 0 0 1 1 0 0

c_1t 1 1 1 1 1 0

c_2t 1 0 0 1 1 1

(8)

State Transition Diagram(2)

Time t 0 1 2 3 4 5

i_t 1 1 0 0 1 0

F1=i_t-1 0 1 1 0 0 1

F2=i_t-2 0 0 1 1 0 0

c_1t 1 1 1 1 1 0

c_2t 1 0 0 1 1 1

t=0 t=1

t=2

t=3 t=4

t=5

 In each time t, a traveler stays in one state.

 And move to different state cycle by cycle.

(9)

Trellis Diagram

 Convert the State transition diagram to 2D diagram

 Vertical axis : states

 Horizontal axis : time

states

time

00 00

01

00 01 10

11

00 01 10

11

00 01 10

11

00/0 11/1

11/0 00/1 01/0 10/1

10/0 01/1

00/0 11/1

11/0 00/1 01/0 10/1

10/0 01/1 00/0

11/1

01/0 10/1 00/0

11/1

00 01 10

11

00/0 11/1

11/0 00/1 01/0 10/1

10/0 01/1

(10)

Encoding in Trellis

 Input information determines a path in Trellis

 Each Branch outputs 2bit code.

Time t 0 1 2 3 4 5

i_t 1 1 0 0 1 0

F1=i_t-1 0 1 1 0 0 1 F2=i_t-2 0 0 1 1 0 0

c_1t 1 1 1 1 1 0

c_2t 1 0 0 1 1 1

00 00

01

00 01 10 11

00/0 11/1

11/0 00/1 01/0 10/1

10/0 01/1

00/0 11/1

11/0 00/1 01/0 10/1

10/0 01/1 00/0

11/1

01/0 10/1 00/0

11/1

00 01 10 11

00/0 11/1

11/0 00/1 01/0 10/1

10/0 01/1

00 01 10 11

00/0 11/1

11/0 00/1 01/0 10/1

10/0 01/1

t=0 t=1 t=2 t=3 t=4 t=5

11

10

11

01

(11)

Punctured Convolutional Code

 The example Encoder has Code Rate R=1/2

 Punctured Convolutional Code means that one or some code output is removed.

 Then Code Rate can be modified

l cn

R ck

cn ck n

R k

punctured original

 



(12)

Merit of Punctured Code

 Larger code rate is better.

 Using Punctured technology,

1. When communication channel condition is good, weak error correction but high code rate can be chosen.

2. When communication channel condition is bud, strong error correction but low code rate can be chosen.

3. This capability can be supported by small circuit change.

One coder or decoder can be used for several code rate addaptively

(13)

R=2/3 example



3 2 1

0

i i i

i ^c

¹⁰

^c

¹¹

^c

¹²

^c

¹³

^c

¹⁴

^



24 23

22 21

20

c c c c c

23 13

22 12

21 11

20

: C

10

C C C C C C C

punctured Non 

: C C C C C C

Punctured

3 2 1

0

i i i

i

(14)

Viterbi Decode

 Viterbi Decode is one method of Maximum likelihood decoding for Convolutional code.

 Maximum likelihood decoding

 Likelihood function is P(xi|r):

 Probability of seding x_i under the condition of receiving r

N message x₁, x₂, x₃, …, x_N

Sender take one message and send it out!

x

_?

r

Receiver find the

maximum conditional Probability

)

|

( x r

P

_i

(15)

Viterbi Decode(2)



Branch metric is the Likelihood function of each branch.

-Ln{p(x_k|r_i)}

High possibility  small value

Example : Hamming distance



Path metric is the sum of branch metrics

along the possible TRELLIS PATH.

(16)

Viterbi Decoding Example

 R=1/2, Receive 11 10 11 01 11 01

 Calculate Each Branch metric (This time Hamming distance)

00 00

01

00 01 10 11

00(2) 11(0)

11(0) 00(2) 01(1) 10(1) 10(1)

01(1)

00(1) 11(1)

11(1) 00(1) 01(0) 10(2) 10(2)

01(0) 00(1)

11(1)

01(2) 10(0) 00(2)

11(0)

00 01 10 11

00(2) 11(0)

11(0) 00(2) 01(1) 10(1) 10(1)

01(1)

00 01 10 11

00(1) 11(1)

11(1) 00(1) 01(0) 10(2) 10(2)

01(0)

t=0 t=1 t=2 t=3 t=4 t=5 t=6

Rece- 11

ived 10 11 01 11 01

(17)

Viterbi Decoding Example(2)

 Calculate Path metric in order to find minimum path metric path.

 Until t=2

00 00

01

00 01 10 11

00(2) 11(0)

11(0) 00(2) 01(1) 10(1) 10(1)

01(1)

00(1) 11(1)

11(1) 00(1) 01(0) 10(2) 10(2)

01(0) 00(1)

11(1)

01(2) 10(0) 00(2)

11(0)

00 01 10 11

00(2) 11(0)

11(0) 00(2) 01(1) 10(1) 10(1)

01(1)

00 01 10 11

00(1) 11(1)

11(1) 00(1) 01(0) 10(2) 10(2)

01(0)

t=0 t=1 t=2 t=3 t=4 t=5 t=6

3 3

2

0

5

2

Lower path has smaller path metric, Then Take it!

(18)

Viterbi Decoding Example(3)

 Calculate Path metric in order to find minimum path metric path.

 Until t=6

00 00

01

00 01 10 11

00(2) 11(0)

11(0) 00(2) 01(1) 10(1) 10(1)

01(1)

00(1) 11(1)

11(1) 00(1) 01(0) 10(2) 10(2)

01(0) 00(1)

11(1)

01(2) 10(0) 00(2)

11(0)

00 01 10 11

00(2) 11(0)

11(0) 00(2) 01(1) 10(1) 10(1)

01(1)

00 01 10 11

00(1) 11(1)

11(1) 00(1) 01(0) 10(2) 10(2)

01(0)

t=0 t=1 t=2 t=3 t=4 t=5 t=6

3 3

2

0 1

1 3 2

1 3 2 2

2 2

2 3

2 2 3 3

(19)

Viterbi Decoding Example(4)

00 00

01

00 01 10 11

00(2) 11(0)

11(0) 00(2) 01(1) 10(1) 10(1)

00(1) 11(1)

11(1) 00(1) 01(0) 10(2) 10(2) 00(1)

11(1)

01(2) 10(0) 00(2)

11(0)

00 01 10 11

00(2) 11(0)

11(0) 00(2) 01(1) 10(1) 10(1)

00 01 10 11

00(1) 11(1)

11(1) 00(1) 01(0) 10(2) 10(2)

t=0 t=1 t=2 t=3 t=4 t=5 t=6

1

2

 Select Minimum Path Metric and get original information

 In this example, two minimum path

 Upper path : 1 1 0 0 1 0

 Lower path : 1 1 1 1 1 1

 If we increase the time, we might find ONLY ONE MINIMUM PATH.

(20)

Received signal has many level

 In the previous example, we have assumed the received sequence is

 11 10 11 01 11 01

 Usually, received signal is analog (Many Levels) such as

SIGNAL LEVEL

0 1 2 3 4 5 6

7 6 5 6 3 5 4 3 6 6 6 2 7

(21)

HARD DECISION

LINE

Hard Decision

1 1 1 0 1 1 0 1 1 1 0 1

SIGNAL LEVEL

0 1 2 3 4 5 6

7 6 5 6 3 5 4 3 6 6 6 2 7

HARD DECISION OUTPUTS

Highly Low

We have to distinguish!

Loosing Reliability

Information by Hard Decision!

(22)

Soft Decision



Use soft decision metric

One Example

LEVEL 0 1 2 3 4 5 6 7

Branch Metric for ‘0’ 0 0 0 0 0 1 2 3 Branch Metric for ‘1’ 3 2 1 0 0 0 0 0 Difference -3 -2 -1 0 0 1 2 3

No effect on Viterbi decoding!

Looks like Erased or Punctured!

Reliable ‘0’ Reliable ‘1’

00 00(branch metric = 1 + 2 = 3)

LEVEL= 65

HOW TO COMPUTE BRANCH METRIC

(23)

Soft Decision Viterbi

00 00

01

00 01 10 11

00(1) 11(0)

11(0) 00(1) 01(1) 10(0) 10(0)

01(1)

00(2) 11(0)

11(0) 00(2) 01(0) 10(2) 10(2)

01(0) 00(2)

11(0)

01(2) 10(0) 00(3)

11(0)

00 01 10 11

00(4) 11(0)

11(0) 00(4) 01(2) 10(2) 10(2)

01(2)

00 01 10 11

00(3) 11(1)

11(1) 00(3) 01(0) 10(4) 10(4)

01(0)

t=0 t=1 t=2 t=3 t=4 t=5 t=6

LEVEL 65 63 54 36 66 27

LEVEL 0 1 2 3 4 5 6 7

Branch Metric for ‘0’ 0 0 0 0 0 1 2 3

 Calculate Branch Metric based on Soft-Table

(24)

Soft Decision Viterbi(2)

Calculate Path metric in order to find minimum path metric path.

Until t=6

00 00

01

00 01 10 11

00(1) 11(0)

11(0) 00(1) 01(1) 10(0) 10(0)

01(1)

00(2) 11(0)

11(0) 00(2) 01(0) 10(2) 10(2)

01(0) 00(2)

11(0)

01(2) 10(0) 00(3)

11(0)

00 01 10 11

00(4) 11(0)

11(0) 00(4) 01(2) 10(2) 10(2)

01(2)

00 01 10 11

00(3) 11(1)

11(1) 00(3) 01(0) 10(4) 10(4)

01(0)

t=0 t=1 t=2 t=3 t=4 t=5 t=6

LEVEL 65 3 63 54 36 66 27

0

5 3

0 2

1 0 3

2

1 3 2

0

3 3 0

0 3

3 4

4

(25)

Soft Decision Viterbi(3)

00 00

01

00 01 10 11

00(1) 11(0)

11(0) 00(1) 01(1) 10(0) 10(0)

01(1)

00(2) 11(0)

11(0) 00(2) 01(0) 10(2) 10(2)

01(0) 00(2)

11(0)

01(2) 10(0) 00(3)

11(0)

00 01 10 11

00(4) 11(0)

11(0) 00(4) 01(2) 10(2) 10(2)

01(2)

00 01 10 11

00(3) 11(1)

11(1) 00(3) 01(0) 10(4) 10(4)

01(0)

t=0 t=1 t=2 t=3 t=4 t=5 t=6

LEVEL 65 63 54 36 66 27

 Select Minimum Path Metric and get original information

 In this example : 1 1 0 0 1 0

0

(26)

Summary

 2 types of FEC

 Block code such as RS

 Convolutional Code

 Convolutional Code

 Code Rate

 Punctured

 Viterbi Decoder : Maximum likelihood decoding

 Trellis

 Hard Decision vs. Soft Decision

 Branch Metric, Path Metric