Transmisja Danych
Laboratorium
Tomasz Kapusta
Kierunek Informatyka
III rok stacjonarnych studiów I stopnia
Rok akademicki 2011/2012
prowadzący
dr inż. Jarosław Zygarlicki
Laboratorium 1
Kodowanie nadmiarowe –
kod Hamminga
Politechnika Opolska 2011
- 1 -
Spis Treści
1. Wstęp teoretyczny............................................................................................... 3
1.1. Kodowanie nadmiarowe
.............................................................................. 3
1.2. Kod Hamminga
..........................................................................................
3
2. Przebieg ćwiczenia.............................................................................................. 5
2.1. Wynik działania programu
..........................................................................
5
2.2. Macierz z zawartymi błędami
......................................................................
5
2.3. Macierz H
..................................................................................................
6
2.4. Ręczna analiza kodu
.................................................................................... 6
2.5. Macierz poprawiona
...................................................................................
9
- 2 -
1. Wstęp teoretyczny
1.1. Kodowanie nadmiarowe
Metody kodowania nadmiarowego polegają na dodaniu do wiadomości dodatkowych
symboli, dzięki którym można stwierdzić, czy i w którym miejscu wiadomości wystąpił błąd.
Kody nadmiarowe dzielimy na:
•
liniowe – oblicza się je korzystając z operacji liniowych, głównie z operacji dodawania
w arytmetyce nad ciałem
Galois
. Najczęściej stosowanym kodem liniowym jest
kod Hamminga
.
•
nieliniowe – oblicza się je korzystając z operacji nieliniowych, wykorzystując wielomiany,
np.
CRC-16-CCIT
,
CRC-32-IEEE 802.3
.
1.2. Kod Hamminga
Kod Hamminga
– to liniowy kod korekcyjny.
•
Waga Hamminga
dowolnego ciągu bitów nazywamy liczbę jedynek w tym ciągu.
Wagę Hamminga
ciągu bitowego x oznaczamy W x .
Przykład:
•
W 01101=3
•
W 01110=3
•
W 00000=0
•
W 10000=1
•
odległość Hamminga
dwóch ciągów bitowych x
1
i x
2
definiuje się jako liczbę
indeksów, na których wartości indeksów różnią się. Odległość tę oznaczamy jako
d x
1,
x
2
. Formalnie można zapisać:
d x
1,
x
2
=
W x
1
x
2
gdzie wynikiem operacji dodawania jest ciąg bitowy, którego wyrazami są sumy
odpowiadających wyrazów ciągu x
1
i x
2
modulo 2 .
- 3 -
Przykład:
•
d 0110,1001=4
•
d 01,11=W 01 ,11=W 10=1
•
d 001,100=W 001100=W 101=2
•
słowo informacyjne
to ciąg bitów reprezentujących dane przeznaczenie dla transmisji.
•
słowo nadmiarowe
to ciąg bitów służących do kontroli poprawności transmitowanych
danych oraz do ich ewentualnej korekty.
•
słowo kodowe
to ciąg bitów z bitami słowa informacyjnego i nadmiarowego. Jeśli słowo
kodowane ma długość n to można zapisać 2
n
słów kluczowych. Część z nich należy do
kodu, pozostałe uznawane są za niepotrzebne. Do tego, aby stwierdzić, czy dane słowo
kodowe należy do kodu służy
algorytm odnajdywania błędu
.
Załóżmy, że nadawca wysłał wiadomość x
K
, x
R
, gdzie x
K
oznacza przesyłane dane,
a x
R
odpowiadający im kod nadmiarowy. Odbiorca odbierze wiadomość x '
K
, x '
R
.
Aby stwierdzić, czy otrzymane dane są poprawne odbiorca musi sam obliczyć kod nadmiarowy
x
R
2
dla wiadomości x '
K
, a następnie syndrom błędu, który z definicji jest równy x '
R
x
R
2
.
Jeżeli syndrom błędu jest różny od 0, oznacza to że w transmisji wystąpił błąd.
Algorytm użycia parzystości dla ogólnego kodu Hamminga jest następujący:
•
wszystkie pozycje bitów, które są potęgami dwójki, są użyte jako
bity parzystości
,
•
wszystkie pozostałe pozycje służą do kodowania danych,
•
każdy bit parzystości obliczany jest na podstawie parzystości pewnych bitów w kodowanym
słowie. Pozycja bitu parzystości określa, które bity mają być sprawdzane, a które pomijane.
Numeracja bitów zaczyna się od 1 , natomiast jako pierwszy sprawdzany jest bit na
pozycji n1 . I tak:
◦
pozycja 1
n=1 : pomiń 0 bitów n−1 , sprawdź 1 bit n , pomiń 1 bit n ,
sprawdź 1 bi n itd.
◦
pozycja 2
n=2 : pomiń 1 bit n−1 , sprawdź 2 bity n , pomiń 2 bity n ,
sprawdź 2 bity n itd.
◦
pozycja 4
n=4 : pomiń 3 bity n−1 , sprawdź 4 bity n , pomiń 4 bity n ,
sprawdź 4 bity n itd.
- 4 -
◦
…
◦
pozycja i
n=i : pomiń i−1 bitów, sprawdź i bitów, pomiń i bitów, sprawdź i bitów
itd.
2. Przebieg ćwiczenie
2.1. Wynik działania programu
Podaj tekst ktory chcesz zakodowac.
Pamietaj, mozesz uzyc tylko duzych liter, bez polskich znakow.
Wpisz maksymalnie 20 znaków.
[ @ ] WPISZ TEKST: TOMASZ KAPUSTA
[ @ ] Zakodowany i uszkodzony napis to: TKMAQZ KAPUSTA
blad w zapisie litery nr 2, w 6 kolumnie zapisu BIN. Poprawiono blad.
blad w zapisie litery nr 5, w 7 kolumnie zapisu BIN. Poprawiono blad.
[ @ ] Odkodowany i poprawiony napis to: TOMASZ KAPUSTA
2.2. Macierz z zawartymi błędami
0 1 0 1 0 1 0 0 1 1 1 1
0 1 0 0 1 0 1 1 0 1 0 1
0 1 0 0 1 1 0 1 1 0 1 1
0 1 0 0 0 0 0 1 1 1 0 1
0 1 0 1 0 0 0 1 0 1 0 1
0 1 0 1 1 0 1 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 1 0 1 1 0 1 1 0
0 1 0 0 0 0 0 1 1 1 0 1
0 1 0 1 0 0 0 0 1 1 0 0
0 1 0 1 0 1 0 1 1 0 0 0
0 1 0 1 0 0 1 1 0 1 0 1
0 1 0 1 0 1 0 0 1 1 1 1
0 1 0 0 0 0 0 1 1 1 0 1
- 5 -
2.3. Macierz H
H =
[
1 1 1 0 0 0 1 0 1 0 0 0
1 0 0 1 1 0 1 1 0 1 0 0
0 1 0 1 0 1 1 1 0 0 1 0
0 0 1 0 1 1 0 1 0 0 0 1
]
2.4. Ręczna analiza kodu
T =010101001111
T⋅H =
[
0⋅1 1⋅1 0⋅1 1⋅0 0⋅0 1⋅0 0⋅1 0⋅0 1⋅1 1⋅0 1⋅0 1⋅0
0⋅1 1⋅0 0⋅0 1⋅1 0⋅1 1⋅0 0⋅1 0⋅1 1⋅0 1⋅1 1⋅0 1⋅0
0⋅0 1⋅1 0⋅0 1⋅1 0⋅0 1⋅1 0⋅1 0⋅1 1⋅0 1⋅0 1⋅1 1⋅0
0⋅0 1⋅0 0⋅1 1⋅0 0⋅1 1⋅1 0⋅0 0⋅1 1⋅0 1⋅0 1⋅0 1⋅1
]
=
[
2
2
4
2
]
P
R
=
[
2
2
4
2
]
modulo 2=
[
0
0
0
0
]
Poprawnie zakodowana litera
T
.
O=010010110101
O⋅H =
[
0⋅1 1⋅1 0⋅1 0⋅0 1⋅0 0⋅0 1⋅1 1⋅0 0⋅1 1⋅0 0⋅0 1⋅0
0⋅1 1⋅0 0⋅0 0⋅1 1⋅1 0⋅0 1⋅1 1⋅1 0⋅0 1⋅1 0⋅0 1⋅0
0⋅0 1⋅1 0⋅0 0⋅1 1⋅0 0⋅1 1⋅1 1⋅1 0⋅0 1⋅0 0⋅1 1⋅0
0⋅0 1⋅0 0⋅1 0⋅0 1⋅1 0⋅1 1⋅0 1⋅1 0⋅0 1⋅0 0⋅0 1⋅1
]
=
[
2
4
3
3
]
P
R
=
[
2
4
3
3
]
modulo 2=
[
0
0
1
1
]
Wystąpiło naruszenie bitu!
H =
[
1 1 1 0 0 0 1 0 1 0 0 0
1 0 0 1 1 0 1 1 0 1 0 0
0 1 0 1 0 1 1 1 0 0 1 0
0 0 1 0 1 1 0 1 0 0 0 1
]
Naruszony został 6-sty bit więc zmieniamy jego wartość na przeciwną.
O=01001 0110101
O=010011 110101
Poprawnie zakodowana litera
O
.
- 6 -
M =010011011011
M⋅H =
[
0⋅1 1⋅1 0⋅1 0⋅0 1⋅0 1⋅0 0⋅1 1⋅0 1⋅1 0⋅0 1⋅0 1⋅0
0⋅1 1⋅0 0⋅0 0⋅1 1⋅1 1⋅0 0⋅1 1⋅1 1⋅0 0⋅1 1⋅0 1⋅0
0⋅0 1⋅1 0⋅0 0⋅1 1⋅0 1⋅1 0⋅1 1⋅1 1⋅0 0⋅0 1⋅1 1⋅0
0⋅0 1⋅0 0⋅1 0⋅0 1⋅1 1⋅1 0⋅0 1⋅1 1⋅0 0⋅0 1⋅0 1⋅1
]
=
[
2
2
4
4
]
P
R
=
[
2
2
4
4
]
modulo 2=
[
0
0
0
0
]
Poprawnie zakodowana litera
M
.
A=010000011101
A⋅H =
[
0⋅1 1⋅1 0⋅1 0⋅0 0⋅0 0⋅0 0⋅1 1⋅0 1⋅1 1⋅0 0⋅0 1⋅0
0⋅1 1⋅0 0⋅0 0⋅1 0⋅1 0⋅0 0⋅1 1⋅1 1⋅0 1⋅1 0⋅0 1⋅0
0⋅0 1⋅1 0⋅0 0⋅1 0⋅0 0⋅1 0⋅1 1⋅1 1⋅0 1⋅0 0⋅1 1⋅0
0⋅0 1⋅0 0⋅1 0⋅0 0⋅1 0⋅1 0⋅0 1⋅1 1⋅0 1⋅0 0⋅0 1⋅1
]
=
[
2
2
2
2
]
P
R
=
[
2
2
2
2
]
modulo 2=
[
0
0
0
0
]
Poprawnie zakodowana litera
A
.
S=010100010101
S⋅H =
[
0⋅1 1⋅1 0⋅1 1⋅0 0⋅0 0⋅0 0⋅1 1⋅0 0⋅1 1⋅0 0⋅0 1⋅0
0⋅1 1⋅0 0⋅0 1⋅1 0⋅1 0⋅0 0⋅1 1⋅1 0⋅0 1⋅1 0⋅0 1⋅0
0⋅0 1⋅1 0⋅0 1⋅1 0⋅0 0⋅1 0⋅1 1⋅1 0⋅0 1⋅0 0⋅1 1⋅0
0⋅0 1⋅0 0⋅1 1⋅0 0⋅1 0⋅1 0⋅0 1⋅1 0⋅0 1⋅0 0⋅0 1⋅1
]
=
[
1
3
3
2
]
P
R
=
[
1
3
3
2
]
modulo 2=
[
1
1
1
0
]
Wystąpiło naruszenie bitu!
H =
[
1 1 1 0 0 0 1 0 1 0 0 0
1 0 0 1 1 0 1 1 0 1 0 0
0 1 0 1 0 1 1 1 0 0 1 0
0 0 1 0 1 1 0 1 0 0 0 1
]
Naruszony został 7-dmy bit więc zmieniamy jego wartość na przeciwną.
- 7 -
S=010100 0 10101
S=0101001 10101
Poprawnie zakodowana litera
S
.
Z =010110100111
Z⋅H =
[
0⋅1 1⋅1 0⋅1 1⋅0 1⋅0 0⋅0 1⋅1 0⋅0 0⋅1 1⋅0 1⋅0 1⋅0
0⋅1 1⋅0 0⋅0 1⋅1 1⋅1 0⋅0 1⋅1 0⋅1 0⋅0 1⋅1 1⋅0 1⋅0
0⋅0 1⋅1 0⋅0 1⋅1 1⋅0 0⋅1 1⋅1 0⋅1 0⋅0 1⋅0 1⋅1 1⋅0
0⋅0 1⋅0 0⋅1 1⋅0 1⋅1 0⋅1 1⋅0 0⋅1 0⋅0 1⋅0 1⋅0 1⋅1
]
=
[
2
4
4
2
]
P
R
=
[
2
4
4
2
]
modulo 2=
[
0
0
0
0
]
Poprawnie zakodowana litera
Z
.
K =010010110110
K⋅H=
[
0⋅1 1⋅1 0⋅1 0⋅0 1⋅0 0⋅0 1⋅1 1⋅0 0⋅1 1⋅0 1⋅0 0⋅0
0⋅1 1⋅0 0⋅0 0⋅1 1⋅1 0⋅0 1⋅1 1⋅1 0⋅0 1⋅1 1⋅0 0⋅0
0⋅0 1⋅1 0⋅0 0⋅1 1⋅0 0⋅1 1⋅1 1⋅1 0⋅0 1⋅0 1⋅1 0⋅0
0⋅0 1⋅0 0⋅1 0⋅0 1⋅1 0⋅1 1⋅0 1⋅1 0⋅0 1⋅0 1⋅0 0⋅1
]
=
[
2
4
4
2
]
P
R
=
[
2
4
4
2
]
modulo 2=
[
0
0
0
0
]
Poprawnie zakodowana litera
K
.
P=010100001100
P⋅H =
[
0⋅1 1⋅1 0⋅1 1⋅0 0⋅0 0⋅0 0⋅1 0⋅0 1⋅1 1⋅0 0⋅0 0⋅0
0⋅1 1⋅0 0⋅0 1⋅1 0⋅1 0⋅0 0⋅1 0⋅1 1⋅0 1⋅1 0⋅0 0⋅0
0⋅0 1⋅1 0⋅0 1⋅1 0⋅0 0⋅1 0⋅1 0⋅1 1⋅0 1⋅0 0⋅1 0⋅0
0⋅0 1⋅0 0⋅1 1⋅0 0⋅1 0⋅1 0⋅0 0⋅1 1⋅0 1⋅0 0⋅0 0⋅1
]
=
[
2
2
2
0
]
P
R
=
[
2
2
2
0
]
modulo 2=
[
0
0
0
0
]
Poprawnie zakodowana litera
P
.
- 8 -
U =010101011000
U⋅H=
[
0⋅1 1⋅1 0⋅1 1⋅0 0⋅0 1⋅0 0⋅1 1⋅0 1⋅1 0⋅0 0⋅0 0⋅0
0⋅1 1⋅0 0⋅0 1⋅1 0⋅1 1⋅0 0⋅1 1⋅1 1⋅0 0⋅1 0⋅0 0⋅0
0⋅0 1⋅1 0⋅0 1⋅1 0⋅0 1⋅1 0⋅1 1⋅1 1⋅0 0⋅0 0⋅1 0⋅0
0⋅0 1⋅0 0⋅1 1⋅0 0⋅1 1⋅1 0⋅0 1⋅1 1⋅0 0⋅0 0⋅0 0⋅1
]
=
[
2
2
4
2
]
P
R
=
[
2
2
4
2
]
modulo 2=
[
0
0
0
0
]
Poprawnie zakodowana litera
U
.
2.5. Macierz poprawiona
0 1 0 1 0 1 0 0 1 1 1 1
0 1 0 0 1 1 1 1 0 1 0 1
0 1 0 0 1 1 0 1 1 0 1 1
0 1 0 0 0 0 0 1 1 1 0 1
0 1 0 1 0 0 1 1 0 1 0 1
0 1 0 1 1 0 1 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 1 0 1 1 0 1 1 0
0 1 0 0 0 0 0 1 1 1 0 1
0 1 0 1 0 0 0 0 1 1 0 0
0 1 0 1 0 1 0 1 1 0 0 0
0 1 0 1 0 0 1 1 0 1 0 1
0 1 0 1 0 1 0 0 1 1 1 1
0 1 0 0 0 0 0 1 1 1 0 1
- 9 -