Kodowanie i kryptografia

Kody splotowe

dr Robert Borowiec
Politechnika Wrocławska
Instytut Telekomunikacji i Akustyki

pokój 908, C-5
tel. [phone]
e-mail: R

[e-mail]

WWW: https://lst.ita.pwr.wroc.pl/kursy/

©

R

o

b

e

rt

B

o

ro

w

ie

c

2

Plan wykładu

• Historia
• Definicja kodu splotowego
• Sposoby kodowania informacji
• Tworzenie kodu
• Metody dekodowania kodów

splotowych

– algorytm Vitterbiego

• twardo decyzyjny
• miękko decyzyjny

©

R

o

b

e

rt

B

o

ro

w

ie

c

3

Historia

Kody splotowe wprowadził P. Elias w roku
1955. Sekwencyjny algorytm dekodowania
kodów splotowych przedstawił w roku 1957 J.
M. Wozencraft, a jego implementację opisali
niezależnie R. M. Fano i J. L. Massey w roku
1963.
W roku 1967 A. J. Viterbi przedstawił algorytm
dekodowania kodów splotowych, opierający się
na

zasadzie

największego

prawdopodobieństwa, który zapewnił lepsze
właściwości korekcyjne i mniejsze opóźnienie
dekodowania niż algorytm sekwencyjny.

©

R

o

b

e

rt

B

o

ro

w

ie

c

4

Definicja kodu splotowego

• Kod splotowy jest to kod drzewiasty, dla

którego ciąg c

(i)

zależy od ciągu h

(i)

oraz od

skończonej liczby (N - 1) wcześniejszych ciągów
informacyjnych za pośrednictwem pewnej
funkcji f, będącej przekształceniem liniowym

)

,

,

(

)

(

)

(

)

1

(

)

(

i

N

i

N

i

i

f

h

h

h

c

,











 

)

,

(

)

(

)

(

i

i

i

f

h

σ

c



©

R

o

b

e

rt

B

o

ro

w

ie

c

5

Koder kodu splotowego

k .. 2 1

n

...

2 1

k .. 2 1

k .. 2 1

k .. 2 1

Wyjści
e

Ciąg n-
bitowych
symboli
kodowych

...

1

2

n

h

(i)

h

(i-

1)

h

(i-

N+1)

h

(i-N)

Wej

k-bitowe
symbole
informacyj
ne



(i)

-stan modulatora (pamięć)

Nk-komórkowy rejestr przesuwający (N-sekcji po k-
komórek)

Symbol
wej.

©

R

o

b

e

rt

B

o

ro

w

ie

c

6

Macierz generująca

Macierz generująca jest macierzą
półnieskończoną

,

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

2

1

2

1

2

1

2

1





















































N

N

N

N

G

G

G

G

G

G

G

G

G

G

G

G

G





 G

h

c

w której:

Podmacierz G

i

opisuje połączenie k komórek i-

tego segmentu rejestru wejściowego z n
komórkami rejestru wyjściowego

©

R

o

b

e

rt

B

o

ro

w

ie

c

7

Przykład 4.1

Koder splotowy (2,1,3)

©

R

o

b

e

rt

B

o

ro

w

ie

c

8

Stan wyjściowy kodera

0

0

0

0

0

1 1 1 0 1 1 0 1 0 1

0 0

Źródło

binarneWejście

Kanał telekomunikacyjny
Wyjście

Czas

C

1

(i

)

C

2

(i

)

0

-1

Kode
r

h

(i)

h

(i-1)

h

(i-

2)

Czas

0

1

2

3

4

5

6

7

8

9

©

R

o

b

e

rt

B

o

ro

w

ie

c

9

Takt 1

1

1

1

0

0

... 1 1 1 0 1 1 0 1 0

1 1

Źródło

binarneWejście

Kanał telekomunikacyjny
Wyjście

Czas

C

1

(i

)

C

2

(i

)

1

0

Kode
r

h

(i)

h

(i-1)

h

(i-

2)

Czas

0

1

2

3

4

5

6

7

8

9

©

R

o

b

e

rt

B

o

ro

w

ie

c

10

Takt 2

1

0

0

1

0

... ... 1 1 1 0 1 1 0 1

1 0 1 1

Źródło

binarneWejście

Kanał telekomunikacyjny
Wyjście

Czas

C

1

(i

)

C

2

(i

)

2

0

1

Kode
r

h

(i)

h

(i-1)

h

(i-

2)

Czas

0

1

2

3

4

5

6

7

8

9

©

R

o

b

e

rt

B

o

ro

w

ie

c

11

Takt 3

0

0

1

0

1

... ... ... 1 1 0 1 1 0 1

0 0 1 0 1 1

Źródło

binarneWejście

Kanał telekomunikacyjny
Wyjście

Czas

0

C

1

(i

)

C

2

(i

)

3

1

2

Kode
r

h

(i)

h

(i-1)

h

(i-

2)

Czas

0

1

2

3

4

5

6

7

8

9

©

R

o

b

e

rt

B

o

ro

w

ie

c

12

Takt 4

1

0

0

1

0

... ... ... ... 1 1 0 1 1 0

1 0 0 0 1 0 1 1

Źródło

binarneWejście

Kanał telekomunikacyjny
Wyjście

Czas

0

1

C

1

(i

)

C

2

(i

)

4

2

3

Kode
r

h

(i)

h

(i-1)

h

(i-

2)

Czas

0

1

2

3

4

5

6

7

8

9

©

R

o

b

e

rt

B

o

ro

w

ie

c

13

Takt 5

0

0

1

0

1

... ... ... ... ... 1 1 0 1 1

0 0 1 0 0 0 1 0 1 1

Źródło

binarneWejście

Kanał telekomunikacyjny
Wyjście

Czas

0

1

2

C

1

(i

)

C

2

(i

)

5

3

4

Kode
r

h

(i)

h

(i-1)

h

(i-

2)

Czas

0

1

2

3

4

5

6

7

8

9

©

R

o

b

e

rt

B

o

ro

w

ie

c

14

Takt 6

0

1

1

1

0

... ... ... ... ... ... 1 1 0 1

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

Źródło

binarneWejście

Kanał telekomunikacyjny
Wyjście

Czas

0

1

2

3

C

1

(i

)

C

2

(i

)

6

4

5

Kode
r

h

(i)

h

(i-1)

h

(i-

2)

Czas

0

1

2

3

4

5

6

7

8

9

©

R

o

b

e

rt

B

o

ro

w

ie

c

15

Takt 7

0

1

0

1

1

... ... ... ... ... ... ... 1 1 0

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

Źródło

binarneWejście

Kanał telekomunikacyjny
Wyjście

Czas

0

1

2

3

4

C

1

(i

)

C

2

(i

)

7

5

6

Kode
r

h

(i)

h

(i-1)

h

(i-

2)

Czas

0

1

2

3

4

5

6

7

8

9

©

R

o

b

e

rt

B

o

ro

w

ie

c

16

Takt 8

0

0

1

0

1

... ... ... ... ... ... ... ... 1 1

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

Źródło

binarneWejście

Kanał telekomunikacyjny
Wyjście

Czas

0

1

2

3

4

5

C

1

(i

)

C

2

(i

)

8

6

7

Kode
r

h

(i)

h

(i-1)

h

(i-

2)

Czas

0

1

2

3

4

5

6

7

8

9

©

R

o

b

e

rt

B

o

ro

w

ie

c

17

Takt 9

0

1

1

1

0

... ... ... ... ... ... ... ... ... 1

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

Źródło

binarneWejście

Kanał telekomunikacyjny
Wyjście

Czas

0

1

2

3

4

5

6

C

1

(i

)

C

2

(i

)

9

7

8

Kode
r

h

(i)

h

(i-1)

h

(i-

2)

Czas

0

1

2

3

4

5

6

7

8

9

©

R

o

b

e

rt

B

o

ro

w

ie

c

18

Cała informacja nadana

1

0

1

1

1

... ... ... ... ... ... ... ... ... ...

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

Źródło

binarneWejście

Kanał telekomunikacyjny
Wyjście

Czas

0

1

2

3

4

5

6

7

C

1

(i

)

C

2

(i

)

1
0

8

9

Kode
r

h

(i)

h

(i-1)

h

(i-

2)

Czas

0

1

2

3

4

5

6

7

8

9

©

R

o

b

e

rt

B

o

ro

w

ie

c

19

Stan c

01

Stan b

10

Stan d

11

Stan a

00

Stan obecny

Stan następny

Stan a

00

Stan b

10

Stan c

01

Stan d

11

Stan a

00

Stan b

10

Stan c

01

Stan d

11

00

11

01

10

11

00

10

01

Wejście:

1

0

©

R

o

b

e

rt

B

o

ro

w

ie

c

20

Wycieczka

Turysta wybiera się w podróż na
Mazury. Przy okazji postanowił
pozwiedzać mijane miejsca. Wyprawę
zaplanował na pięć dni. Postanowił,
że aby mieć czas na zwiedzanie nie
będzie przejeżdżał więcej niż 200 km
dziennie.

©

R

o

b

e

rt

B

o

ro

w

ie

c

21

Która droga jest najkrótsza?

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

195

122

18

1

171

121

16

9

18

8

80

98

12

3

14

7

96

52

117

126

12

5

79

116

138

108

192

132

133

177

174

178

157

194

194

©

R

o

b

e

rt

B

o

ro

w

ie

c

22

Pierwszy dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

188

171

169

121

195

122

18

1

171

121

16

9

18

8

80

98

12

3

14

7

96

52

117

126

12

5

79

116

138

108

192

132

133

177

174

178

157

194

194

©

R

o

b

e

rt

B

o

ro

w

ie

c

23

Drugi dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

188

171

169

121

268

195

122

18

1

80

98

12

3

14

7

96

52

117

126

12

5

79

116

138

108

192

132

133

177

174

178

157

194

194

26

8

29

4

<

©

R

o

b

e

rt

B

o

ro

w

ie

c

24

Drugi dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

188

171

169

121

268

195

122

18

1

80

96

52

117

126

12

5

79

116

138

108

192

132

133

177

174

178

157

194

194

28

6

31

8

<

98

14

7

286

©

R

o

b

e

rt

B

o

ro

w

ie

c

25

Drugi dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

188

171

169

121

268

195

122

18

1

80

117

126

12

5

79

116

138

108

192

132

133

177

174

178

157

194

194

17

3

26

7

<

98

286

96

52

173

©

R

o

b

e

rt

B

o

ro

w

ie

c

26

Drugi dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

188

171

169

121

268

195

122

18

1

80

117

126

12

5

79

116

138

108

192

132

133

177

174

178

157

194

194

98

286

52

173

©

R

o

b

e

rt

B

o

ro

w

ie

c

27

Drugi dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

188

169

121

268

195

122

18

1

80

126

79

116

138

108

192

132

133

177

174

178

157

194

194

23

8

29

4

<

98

286

52

173

238

117

12

5

©

R

o

b

e

rt

B

o

ro

w

ie

c

28

Drugi dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

188

169

121

268

195

122

18

1

80

116

138

108

192

132

133

177

174

178

157

194

194

24

7

24

8

<

98

286

52

173

238

117

126

79

247

©

R

o

b

e

rt

B

o

ro

w

ie

c

29

Drugi dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

188

169

121

268

195

122

18

1

80

138

108

192

132

133

177

174

178

157

194

194

98

286

52

173

238

117

126

247

285

116

©

R

o

b

e

rt

B

o

ro

w

ie

c

30

Trzeci dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

188

169

121

268

195

122

18

1

138

108

192

132

133

178

157

194

194

44

2

46

3

<

286

173

238

247

285

177

174

442

©

R

o

b

e

rt

B

o

ro

w

ie

c

31

Trzeci dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

188

169

121

268

195

122

18

1

138

108

192

132

133

178

157

194

194

286

173

238

247

285

174

442

©

R

o

b

e

rt

B

o

ro

w

ie

c

32

Trzeci dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

188

169

121

268

195

122

18

1

138

108

192

133

178

157

194

194

173

238

247

285

174

442

305

132

©

R

o

b

e

rt

B

o

ro

w

ie

c

33

Trzeci dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

188

169

121

268

195

122

18

1

108

192

178

157

194

194

37

1

38

5

<

173

238

247

285

174

442

305

132

371

138

133

©

R

o

b

e

rt

B

o

ro

w

ie

c

34

Trzeci dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

188

169

121

268

195

122

18

1

178

157

194

194

35

5

47

7

<

173

238

247

285

174

442

305

132

371

133

108

192

355

©

R

o

b

e

rt

B

o

ro

w

ie

c

35

Trzeci dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

188

169

121

268

195

122

18

1

178

157

194

194

173

238

247

285

174

442

305

132

371

133

108

355

©

R

o

b

e

rt

B

o

ro

w

ie

c

36

Trzeci dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

188

169

121

268

195

122

18

1

178

157

194

194

173

238

247

174

442

305

132

371

133

108

355

©

R

o

b

e

rt

B

o

ro

w

ie

c

37

Trzeci dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

188

121

268

195

122

18

1

178

157

194

194

173

238

247

174

442

305

132

371

133

108

355

©

R

o

b

e

rt

B

o

ro

w

ie

c

38

Czwarty dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

188

121

268

195

122

18

1

194

194

48

3

59

9

<

173

238

247

442

305

371

355

178

157

483

©

R

o

b

e

rt

B

o

ro

w

ie

c

39

Czwarty dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

188

121

268

195

122

18

1

194

194

173

238

247

442

305

371

355

178

483

©

R

o

b

e

rt

B

o

ro

w

ie

c

40

Czwarty dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

188

121

268

195

122

18

1

194

194

173

238

247

305

371

355

178

483

©

R

o

b

e

rt

B

o

ro

w

ie

c

41

Czwarty dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

188

121

195

122

18

1

194

194

173

238

247

305

371

355

178

483

©

R

o

b

e

rt

B

o

ro

w

ie

c

42

Czwarty dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

121

195

122

18

1

194

173

238

247

305

371

355

178

483

565

194

©

R

o

b

e

rt

B

o

ro

w

ie

c

43

Czwarty dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

121

195

122

18

1

173

238

247

305

371

355

178

483

565

194

549

194

©

R

o

b

e

rt

B

o

ro

w

ie

c

44

Piąty dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

121

68

7

173

238

247

305

371

355

483

565

549

73

0

<

67

8

<

195

122

18

1

678

©

R

o

b

e

rt

B

o

ro

w

ie

c

45

Piąty dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

121

173

238

247

305

371

355

483

565

549

678

©

R

o

b

e

rt

B

o

ro

w

ie

c

46

Piąty dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

121

173

305

483

678

©

R

o

b

e

rt

B

o

ro

w

ie

c

47

Piąty dzień podróży

Wrocław

Konin

Łódź

Toruń

Bydgoszcz

Piotrków

Kraków

Gdańsk

Płock

Warszawa

Radom

Olsztyn

Białystok

Ostrów

Suwałki

Kalisz

Częstochowa

Poznań

Gniezno

121

173

305

483

678

©

R

o

b

e

rt

B

o

ro

w

ie

c

48

Dekodowanie kodów splotowych

• Algorytm Vitterbiego

– twardo decyzyjny
– miękko decyzyjny