Wykład 5
Protekcja błędów
1. Przestrzeń Hamminga
2. Detekcja i korekcja błędów
3. Kod z kontrolą parzystości
4. Kody cykliczne
5. Korekcja pojedynczych błędów
6. Kod z podwójną kontrolą
parzystości
7. Kod Hamminga
8. Korekcja błędów
wielokrotnych
TD5-1 / 29
Przestrzeń
Hamminga
TD5-2 / 29
Kodowanie detekcyjne i korekcyjne
w przestrzeni Hamminga
Idea detekcji i korekcji
TD5-3 / 29
Kod detekcyjny – wykrywający do k
przekłamań.
Kod korekcyjny – korygujący do k
przekłamań.
Przestrzeń Hamminga – zbiór wierzchołków n-
wymiarowej kostki o krawędzi jednostkowej.
Odległość w przestrzeni Hamminga –
minimalna liczba krawędzi między dwoma
punktami.
0
1
n=
1
0
0
0
1
n=
2
1
0
1
1
0
0
0
0
0
1
n=
3
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
Przestrzeń 4-wymiarowa
TD5-4 / 29
0
00
0
0
00
1
n=
4
0
0
10
0
0
11
0
10
0
0
10
1
0
11
0
0
1
11
1
00
0
1
00
1
1
0
10
1
0
11
1
10
0
1
10
1
1
11
0
1
1
11
Odległość kodowa
TD5-5 / 29
Kody detekcyjne i korekcyjne używają tylko
wybranych punktów z przestrzeni Hamminga.
Odległość kodowa – to minimalna odległość
między dowolną parą punktów kodowych
(używanych przez kod).
Detekcja – wykrycie, że odebrany punkt nie jest
punktem kodowym.
k
1
k +1
d
min
= k +1
. . .
Aby kod wykrywał do k przekłamań, jego minimalna
odległość kodowa musi wynosić k + 1.
Przykład 4-wymiarowy
TD5-6 / 29
0
00
0
0
00
1
n=
4
0
0
10
0
0
11
0
10
0
0
10
1
0
11
0
0
1
11
1
00
0
1
00
1
1
0
10
1
0
11
1
10
0
1
10
1
1
11
0
1
1
11
Kod wykrywający pojedyncze przekłamania (k = 1, d
min
=2)
Odległość kodowa -
korekcja
TD5-7 / 29
Korekcja – przejście do najbliższego punktu
kodowego
k +1
k
2k +1
d
min
= 2k +1
. . .
. . .
korekcja
Aby kod korygował do k przekłamań, jego minimalna
odległość kodowa musi wynosić 2k + 1.
Przykład 5-wymiarowy
TD5-8 / 29
00
00
0
00
00
1
n=
5
00
0
10
00
0
11
00
10
0
00
10
1
00
11
0
00
1
11
01
00
0
001
00
1
01
0
10
01
0
11
01
10
0
01
10
1
01
11
0
01
1
11
Kody korygujące pojedyncze przekłamania (k = 1, d
min
=3)
10
00
0
10
00
1
10
0
10
10
0
11
10
10
0
10
10
1
10
11
0
10
1
11
11
00
0
101
00
1
11
0
10
11
0
11
11
10
0
11
10
1
11
11
0
11
1
11
Kody detekcyjne
TD5-9 / 29
•Kody z kontrolą parzystości
•Kody cykliczne
Kody parzystości
TD5-10 / 29
Odbiorcza suma kontrolna
d =
1
2
3
…
m–1
m
m+1
Nadawcza suma kontrolna
a
m+1
= a
1
a
2
a
3
… a
m–1
a
m
A
m
A
3
A
2
A
1
a
m+1
a
m
a
1
a
3
a
2
…
Koder
A
m
A
3
A
2
A
1
m+1
m
1
3
2
…
Dekoder
…
Błąd
Kody cykliczne - teoria
TD5-11 / 29
Zapiszmy ciąg bitów jako wielomian fikcyjnej zmiennej x, np.
ciąg 100011011 zapiszmy jako W(x) = x
8
+x
4
+x
3
+x+1.
Koncepcja kodów
Wielomian M(x) reprezentujący dane nadawane dzielimy przez
tzw. wielomian generujący G(x) stopnia k.
Resztę z dzielenia R(x) wysyłamy po danych (k bitów).
Tak więc nadawany jest wielomian W(x) = x
k
M(x) + R(x).
W odbiorniku dzieli się odebrane M(x) przez G(x) wyznaczając
resztę R(x).
Jeżeli obliczone R(x) jest równe odebranemu R(x), to uznaje się,
że transmisja była bezbłędna.
Wykrywane są wszystkie paczki błędów o długości niewiększej
niż k oraz większość dłuższych błędów.
Kody cykliczne - praktyka
TD5-12 / 29
Wielomiany generacyjne
W protokole HDLC
Wielomian R
*
(x) to zanegowana reszta z dzielenia M(x) / G(x).
Nadawany jest wielomian W(x) = x
k
M(x) + R
*
(x).
Odbiornik oblicza r(x) jako resztę z dzielenia W(x) / G(x)
i porównuje r(x) z ustalonym wielomianem.
CRC-16 (ITU-T) G(x) = x
16
+x
12
+x
5
+1
CRC-16 (ANSI)
G(x) = x
16
+x
15
+x
2
+1
CRC-12
G(x) = x
12
+x
11
+x
3
+1
CRC-32
G(x) = x
32
+x
26
+x
23
+x
22
+x
16
+x
12
+x
11
+x
10
+
+x
8
+x
7
+x
5
+x
4
+x
2
+x+1
Kodowanie w HDLC
TD5-13 / 29
Koder
1
5
1
4
1
3
1
2
1
1
Dekoder
1
0
9 8 7 6 5 4
3 2 1 0
+
+
+
dane M(x)
*)
Na początku rejestr ładuje się jedynkami
1
5
1
4
1
3
1
2
1
1
1
0
9 8 7 6 5 4
3 2 1 0
+
+
+
dane odbierane W(x)
*)
Na początku rejestr ładuje się zerami
Kody korekcyjne
TD5-14 / 29
•Kody z podwójną kontrolą parzystości
•Kody Hamminga
Podwójna parzystość
TD5-15 / 29
Σ
p d
8
d
7
d
6
d
5
d
4
d
3
d
2
d
1
0
0
0
1
0
0
0
0
0
Σ 0 0 1 0 0 0 0 0 0
Korekcyjny kod
Hamminga
TD5-16 / 29
Kod korygujący pojedyncze przekłamanie.
m – liczba bitów informacyjnych
(użytecznych),
k – liczba bitów kontrolnych,
n = m + k
d
i
– wynik i-tej sumy kontrolnej (binarnej)
d
k
d
k–1
… d
2
d
1
– zero lub binarny numer przekłamanej pozycji
Liczba bitów kontrolnych k musi zatem spełniać warunek
2
k
> m + k
m 1 2 – 4 5 –
11
12 –
26
27 –
57
58 –
120
121 –
247
k 2
3
4
5
6
7
8
Przykład kodu Hamminga
TD5-17 / 29
m =
4,
k = 3,
n = 7,
Nr
poz.
d
3
d
2
d
1
-
0 0 0
1
0 0 1
2
0 1 0
3
0 1 1
4
1 0 0
5
1 0 1
6
1 1 0
7
1 1 1
Odbiorcze sumy kontrolne
d
1
=
1
3
5
7
d
2
=
2
3
6
7
d
3
=
4
5
6
7
Pozycje kontrolne: 1, 2, 4
Nadawcze sumy kontrolne
a
1
= a
3
a
5
a
7
a
2
= a
3
a
6
a
7
a
4
= a
5
a
6
a
7
Nadajnik kodu Hamminga
TD5-18 / 29
Pozycje kontrolne: 1, 2, 4
Nadawcze sumy kontrolne
a
1
= a
3
a
5
a
7
a
2
= a
3
a
6
a
7
a
4
= a
5
a
6
a
7
A
1
A
2
A
3
A
4
a
4
a
1
a
2
a
3
a
7
a
5
a
6
Odbiornik kodu
Hamminga
TD5-19 / 29
Odbiorcze sumy kontrolne
d
1
=
1
3
5
7
d
2
=
2
3
6
7
d
3
=
4
5
6
7
1
2
3
4
A
4
A
1
A
2
A
3
d
3
d
2
d
1
5
6
7
7
0
4 3 2 1
6 5
Kody cykliczne a korekcja
TD5-20 / 29
Dekoder kodu cyklicznego
Reszta r(x) z dzielenia W(x) / G(x)
(adres słowa w pamięci)
Pamięć z ciągami e(x) błędów, które
odpowiadają resztom r(x)
W(x) = x
k
M(x) + R
*
(x).
+
Dane odebrane M(x)
Dane skorygowane M(x) r(x)
Wykład 5a
Modulacje - podstawy
1. Łącze i jego elementy
2. Nośniki i ich modulacje
3. Modulacje sinusoidalne
TD5-21 / 29
Wstęp
Łącze i jego elementy
Nośnik, wiadomość, sygnał
TD5-22 / 29
Kanał
telekomunikacyjny
TD5-23 / 29
Nośnik – wielkość
fizyczna sztucznie
wytworzona, zjawisko
posiadające możliwość
rozprzestrzeniania się
Modu-
lator
Kanał
analogo
wy
Demod
u-
lator
Zakłócenia
Wiadomo
ść
nadawan
a
Sygnał analogowy Nośnik
Nośnik
Wiadomo
ść
odbieran
a
Modulacja – proces
nakładania wiadomości
na nośnik
Modulator – urządzenie
wykonujące modulację
Sygnał –
wiadomość
nałożona na
nośnik
Łącze – zespół środków
technicznych służących do
przesyłania sygnału
Kanał transmisji
danych
TD5-24 /
29
Szeregowy styk
binarny
Mode
m
Kanał
analogo
wy
Mode
m
Zakłócenia
Dane
nadawa
ne
Dane
odbiera
ne
Styk S1
Styk S1
Styk S2
Styk S2
Kanał binarny
Nośnik
TD5-25 / 29
Nośnik
u
n
(t
) = f
(a
1
, a
2
, …, a
m
, t )
Nośnik stały
f
(A, t ) = A
Nośnik sinusoidalny
f
(A,
,
, t ) = A sin(
t
+
)
Nośnik impulsowy
f
(A,
,
, d, liczba, kod, kształt, … , t )
Modulacje
TD5-26 / 29
Modulacja prosta
u
x
(A, t ) = A(x
(t
))
gdzie x(t
) – przesyłana
wiadomość
TD5-27 / 29
Modulacja
napięciowa
1 – 10 V
Modulacja prądowa
4 – 20 mA
Modulacje sinusoidalne
AM – modulacja amplitudy
u
x
(A, t ) = A(x
(t
)) sin(
t +
)
TD5-28 / 29
FM – modulacja
częstotliwości
u
x
(
, t ) = A
sin(
(x (t ))
t +
)
PM – modulacja fazy
u
x
(
, t ) = A
sin(
t +
(x
(t )))
Modulacje mieszane: AM-PM,
QAM
u
x
(A,
, t ) = A(x (t ))
sin(
t +
(x
(t )))
Modulac
ja
kąta
Modulacje AM i FM
TD5-29 / 29
x( t
)
AM
FM