Error Correction Error Correction Code (2)

(1)

Error Correction Error Correction Code (2)

Code (2)

Fire Tom Wada

Professor Information Professor, Information

Engineering, Univ. of the Ryukyus

(2)

Two major FEC technologies Two major FEC technologies

1.

Reed Solomon code (Block Code) eed So o o code ( oc Code)

2.

Convolutional code

3.

Serially concatenated code

Source Information

Reed Solomon

C d

Interleaving Convolution Code

Concatenated Coded

Information Code Code Coded

Concatenated

Goes to Storage, Transmission Concatenated

(3)

(n k) Block Code (n, k) Block Code

k bit k bit k bit BLOCK

i

_t-2

i

_t-1

i

_t

Information

ENCODE ENCODE ENCODE

code

w

_t-2

w

_t-1

w

_t

E E E

Ti t i f ti bl k i i d d t ti t d n bit n bit n bit

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

k : information length

n : code length

(4)

Convolutional Code Convolutional Code

i

k bit

i

k bit

i

k bit

I f i

i

_t-2

i

_t-1

i

_t

Information

code

w

_t-2

n bit

w

_t-1

n bit

w

_t

n bit n bit n bit n bit

Constraint length K

Time t code w_tis determined by past K information.

K : Constraint length

Code Rate : R=k/n

(5)

Simple Convolutional Coder Simple Convolutional Coder

L c

c c

L

2 1 0

i i i

L

12 11

10

c c c

L

22 21

20

c c c

₂₀ ₂₁ ₂₂

i D

i i

c = ⊕ = ( 1 +

²

)

t t

t

t t

i D

D i

i i

c

i D

i i

c

) 1

( ) 1

(

2 2

1 2

2 1

+ +

=

⊕

=

+

=

⊕

=

−

D is delay operator

d d t l t it b l t i i

c_1t, c_2t depends on not only current it bu also past i_t-1, i_t-2

(6)

Simple Convolutional Coder(2) 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

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

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 State Transition Diagram

Number of State: 4

Time t 0 1 2 3 4 5

i 1 1 0 0 1 0

i_t 1 1 0 0 1 0

F1=i_t-1 0 1 1 0 0 1

F2=i 0 0 1 1 0 0

F2=i_t-2 0 0 1 1 0 0

c_1t 1 1 1 1 1 0

c_2t_2t 1 0 0 1 1 1

(8)

State Transition Diagram(2) State Transition Diagram(2)

Time t 0 1 2 3 4 5 t=0

t=4

i_t 1 1 0 0 1 0

F1=i_t-1 0 1 1 0 0 1

t=1 t=3

t=5

F2=i_t-2 0 0 1 1 0 0

c_1t 1 1 1 1 1 0

t=2

c_2t 1 0 0 1 1 1

In each time t a traveler stays in one state

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

And move to different state cycle by cycle.

(9)

Trellis Diagram Trellis Diagram

Convert the State transition diagram to 2D diagram

Vertical axis : states

Horizontal axis : time

time time

00 ^00/0 00 ^00/0 00 ^00/0 00 ^00/0 00 ^00/0 00

states

00 00

01

00 01

00/0 11/1

11/0

00/0 11/1

11/0 00/0

11/1 00/0

11/1

00 01

00/0 11/1

11/0

10 10 10

00/1 01/0 10/1

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

10/1 10

00/1 01/0 10/1

11 11 11

10/0 01/1

10/0

01/1 11

10/0 01/1

(10)

Encoding in Trellis Encoding in Trellis

Input information determines

Time t 0 1 2 3 4 5

i_t 1 1 0 0 1 0

a path in Trellis

Each Branch outputs 2bit code.

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

00 00 00 ^00/0 00 00

11/1

00/0 11/1 00/0

11/1 00/0

11/1

00/0 00

11/1

00/0 00

11/1

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

11

01 01 ^11/0 01 01

00/1 01/0

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

11/0 01

00/1 01/0

11/0 01

00/1 01/0

11 11

01

10 11

01/0 10/1

10/0

01/0 10/1

10/0 01/0

10/1 10

11

01/0 10/1

10/0

10 11

01/0 10/1

10 10/0

11 01/1 11 01/1 11 01/1 11 01/1 11

10

(11)

Punctured Convolutional Code Punctured Convolutional Code

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

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

or some code output is removed.

Then Code Rate can be modified

ck R

_original

= k =

ck cn

original

n

l cn

R

_punctured

ck

= −

(12)

Merit of Punctured Code Merit of Punctured Code

Larger code rate is better.g

Using Punctured technology,

1 When communication channel condition is good

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 h

change.

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

rate addaptively

(13)

R=2/3 example R=2/3 example

L c

c c

c

L c

3 2 1

0

i i i

i ^c

¹⁰

^c

¹¹

^c

¹²

^c

¹³

^c

¹⁴

^L

L

24 23

22 21

20

c c c c c

i i i

i

₀

i

₁

i

₂

i

₃

i

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

(14)

Viterbi Decode Viterbi Decode

Viterbi Decode is one method of Maximum likelihood

d di f C l ti l d

decoding for Convolutional code.

Maximum likelihood decoding

Likelihood function is P(x |r):

Likelihood function is P(x_i|r):

Probability of seding x_i under the condition of receiving r

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

Sender take one

x

_?

r

R i fi d th

)

| ( x r

P

_i

message and send it out!

Receiver find the

maximum conditional Probability

(15)

Viterbi Decode(2) Viterbi Decode(2)

Branch metric a c e c is the Likelihood function of s e e ood u c o o each branch.

Ln{p(x |r )}

-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 Viterbi Decoding Example

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

Calculate Each Branch metric (This time Hamming distance)

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

11 Rece-

ived 10 11 01 11 01

00 00

01

00 01

00(2) 11(0)

11(0)

00(1) 11(1)

11(1) 00(1)

11(1) 00(2)

11(0)

00 01

00(2) 11(0)

11(0)

00 01

00(1) 11(1)

11(1)

01 01

10

01 10

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

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

10(0)

01 10

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

01 10

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

11 11 11

( ) 10(1)

01(1)

( ) 10(2)

01(0) ( )

11

( ) 10(1)

01(1) 11

( ) 10(2)

01(0)

(17)

Viterbi Decoding Example(2) Viterbi Decoding Example(2)

Calculate Path metric in order to find minimum path metric th

path.

Until t=2 Lower path has smaller path metric, Th T k it!

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

3 5

Then Take it!

00 00

01

00 01

00(2) 11(0)

11(0)

00(1) 11(1)

11(1) 00(1)

11(1) 00(2)

11(0)

00 01

00(2) 11(0)

11(0)

00 01

00(1) 11(1)

11(1)

3

2

01 01

10

01 10

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

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

10(0)

01 10

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

01 10

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

2

11 11 11

( ) 10(1)

01(1)

( ) 10(2)

01(0) ( )

11

( ) 10(1)

01(1) 11

( ) 10(2)

01(0)

0 0

(18)

Viterbi Decoding Example(3) Viterbi Decoding Example(3)

path.

Until t=6

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

3 2 2 3 3

00 00

01

00 01

00(2) 11(0)

11(0)

00(1) 11(1)

11(1) 00(1)

11(1) 00(2)

11(0)

00 01

00(2) 11(0)

11(0)

00 01

00(1) 11(1)

11(1)

3 3 2 2 3

01 01

10

01 10

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

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

10(0)

01 10

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

01 10

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

2

1

3

2

11 11 11

( ) 10(1)

01(1)

( ) 10(2)

01(0) ( )

11

( ) 10(1)

01(1) 11

( ) 10(2)

01(0)

0 1

1

1 2

2

0 1 1 2 22

(19)

Viterbi Decoding Example(4) Viterbi Decoding Example(4)

Select Minimum Path Metric and get original information

In this example two minimum path

In this example, two minimum path

Upper path : 1 1 0 0 1 0

Lower path : 1 1 1 1 1 1

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

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

00 00 00 ⁰⁰⁽²⁾ 00 00

11(0)

00(1) 11(1) 00(1)

11(1) 00(2)

11(0)

00(2) 00

11(0)

00(1) 00

11(1)

2

01 01 01 01

(0) 11(0)

00(2)

( ) 11(1)

00(1) ( )

(0)

01

(0) 11(0)

00(2)

01

( ) 11(1)

00(1)

2

10 10 10

01(1) 10(1) 10(1)

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

10(0) 10

01(1) 10(1) 10(1)

10

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

1

2

11 ₀₁₍₁₎ 11 ₀₁₍₀₎ 11 ₀₁₍₁₎ 11 ₀₁₍₀₎ 11

(20)

Received signal has many level Received signal has many level

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

11 10 11 01 11 01

U ll i d i l i l (M L l ) h

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

SIGNAL SIGNAL

LEVEL

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

4 5 6

1 2 3

0

(21)

Hard Decision

HARD DECISION

Hard Decision

SIGNAL LINE LEVEL

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

4 5 6 7

1 2 3 4

0 1

HARD

Loosing Reliability

Information by Hard Decision!

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

HARD DECISION OUTPUTS

Highly Low

W h t di ti i h!

y

Highly reliable 1

Low

reliable 1 We have to distinguish!

(22)

Soft Decision Soft Decision

Use soft decision metric Use so dec s o e c

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!

Reliable ‘0’ Reliable ‘1’

HOW TO COMPUTE BRANCH METRIC No effect on Viterbi decoding!

Looks like Erased or Punctured!

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

LEVEL= 65

HOW TO COMPUTE BRANCH METRIC

(23)

Soft Decision Viterbi Soft Decision Viterbi

Calculate Branch Metric based on Soft-Table

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

LEVEL 65 63 54 36 66 27

00 00

01

00 01

00(1) 11(0)

11(0)

00(2) 11(0)

11(0) 00(2)

11(0) 00(3)

11(0)

00 01

00(4) 11(0)

11(0)

00 01

00(3) 11(1)

11(1)

01 01

10

01 10

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

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

10(0)

01 10

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

01 10

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

11 11 11

10(0) 01(1)

10(2)

01(0) 11

10(2)

01(2) 11

10(4) 01(0)

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

(24)

Soft Decision Viterbi(2) Soft Decision Viterbi(2)

path.

Until t=6

00 ⁰⁰⁽³⁾ 00 ⁰⁰⁽²⁾ 00 ⁰⁰⁽¹⁾ 00 ⁰⁰⁽²⁾ 00 ⁰⁰⁽⁴⁾ 00 ⁰⁰⁽³⁾ 00

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

LEVEL 65 63 54 36 66 27

3 5 2 0 3 4

00 00

01

00 01

00(1) 11(0)

11(0)

00(2) 11(0)

11(0) 00(2)

11(0) 00(3)

11(0)

00 01

00(4) 11(0)

11(0)

00 01

00(3) 11(1)

11(1)

3 3 2 0 4

10 10 10

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

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

10(0) 10

00(4) 01(2)

10(2) 10

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

0 2

0 3 3 0

11 11 11

10(0) 01(1)

10(2)

01(0) 11

10(2)

01(2) 11

10(4) 01(0)

0 1

0

1 3

3

3 0

0 1 1 3 33

(25)

Soft Decision Viterbi(3) Soft Decision Viterbi(3)

Select Minimum Path Metric and get original information

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

In this example : 1 1 0 0 1 0

00 ⁰⁰⁽³⁾ 00 ⁰⁰⁽²⁾ 00 ⁰⁰⁽¹⁾ 00 ⁰⁰⁽²⁾ 00 ⁰⁰⁽⁴⁾ 00 ⁰⁰⁽³⁾ 00

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

LEVEL 65 63 54 36 66 27

0

01 01 01 01

11(0) 11(0)

00(1)

11(0) 11(0)

00(2) 11(0)

11(0)

01

11(0) 11(0)

00(4)

01

11(1) 11(1)

00(3)

0

10 10 10

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

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

10(0) 10

00(4) 01(2)

10(2) 10

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

0

0 0

11 11 11

10(0) 01(1)

10(2)

01(0) 11

10(2)

01(2) 11

10(4) 01(0)

0

0 0

(26)

Summary Summary

2 types of FECyp

Block code such as RS

Convolutional Code

Code Rate

Punctured

Viterbi Decoder : Maximum likelihood decoding

Trellis

H d D i i S ft D i i

Hard Decision vs. Soft Decision

Branch Metric, Path Metric