Kodowanie i kryptografia
Kody splotowe
dr Robert Borowiec
Politechnika Wrocławska
Instytut Telekomunikacji i Akustyki
pokój 908, C-5
tel. 3203083
e-mail: R
WWW: https://lst.ita.pwr.wroc.pl/kursy/
Kodowanie i kryptografia
Kody splotowe
dr Robert Borowiec
Politechnika Wrocławska
Instytut Telekomunikacji i Akustyki
pokój 908, C-5
tel. 3203083
e-mail: R
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
binarneWejś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
binarneWejś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
binarneWejś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
binarneWejś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
binarneWejś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
binarneWejś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
binarneWejś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
binarneWejś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
binarneWejś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
binarneWejś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
binarneWejś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