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.
x W śą xźą
WagÄ™ Hamminga ciÄ…gu bitowego oznaczamy .
Przykład:
" W śą01101źą=3
" W śą01110źą=3
" W śą00000źą=0
" W śą10000źą=1
x1 x2
" odległość Hamminga dwóch ciągów bitowych i definiuje się jako liczbę
indeksów, na których wartości indeksów różnią się. Odległość tę oznaczamy jako
d śą x1, x2źą
. Formalnie można zapisać:
d śą x1, x2źą=W śąśąx1ƒÄ…x2źąźą
gdzie wynikiem operacji dodawania jest ciąg bitowy, którego wyrazami są sumy
x1 x2
2
odpowiadających wyrazów ciągu i modulo .
- 3 -
Przykład:
" d śą0110,1001źą=4
" d śą01,11źą=W śąśą01źą ,śą11źąźą=W śą10źą=1
" d śą001,100źą=W śąśą001źąƒÄ…śą100źąźą=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
n
kodowane ma długość to można zapisać słów kluczowych. Część z nich należy do
2n
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.
śą xK , x źą x
Załóżmy, że nadawca wysłał wiadomość , gdzie oznacza przesyłane dane,
R K
x śąx' , x' źą
a odpowiadający im kod nadmiarowy. Odbiorca odbierze wiadomość .
R K R
Aby stwierdzić, czy otrzymane dane są poprawne odbiorca musi sam obliczyć kod nadmiarowy
2źą
x 'K
xśąR x 'RƒÄ…xśą2 źą
dla wiadomości , a następnie syndrom błędu, który z definicji jest równy .
R
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.
1
Numeracja bitów zaczyna się od , natomiast jako pierwszy sprawdzany jest bit na
pozycji nƒÄ…1 . I tak:
śąn=1źą śąn-1źą śąnźą śąnźą
ć% pozycja 1 : pomiń 0 bitów , sprawdz
1 bit , pomiń 1 bit ,
śąnźą
sprawdz
1 bi itd.
śąn=2źą śąn-1źą śąnźą śąnźą
ć% pozycja 2 : pomiń 1 bit , sprawdz
2 bity , pomiń 2 bity ,
śąnźą
sprawdz
2 bity itd.
śąn=4źą śąn-1źą śąnźą śąnźą
ć% pozycja 4 : pomiń 3 bity , sprawdz
4 bity , pomiń 4 bity ,
śąnźą
sprawdz
4 bity itd.
- 4 -
ć% &
śąn=iźą i-1
ć% pozycja i : pomiń bitów, sprawdz
i bitów, pomiń i bitów, sprawdz
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
1 1 1 0 0 0 1 0 1 0 0 0
1 0 0 1 1 0 1 1 0 1 0 0
H =
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
0Å"1 ƒÄ… 1Å"1 ƒÄ… 0Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"0 ƒÄ… 1Å"0 ƒÄ… 0Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 1Å"0 ƒÄ… 1Å"0 ƒÄ… 1Å"0 2
0Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"1 ƒÄ… 0Å"1 ƒÄ… 1Å"0 ƒÄ… 1Å"1 ƒÄ… 1Å"0 ƒÄ… 1Å"0 2
TÅ"H= =
0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"1 ƒÄ… 0Å"1 ƒÄ… 1Å"0 ƒÄ… 1Å"0 ƒÄ… 1Å"1 ƒÄ… 1Å"0 4
[ ] [ ]
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 0
2 0
PR= modulo 2=
4 0
[ ] []
2 0
Poprawnie zakodowana litera T.
O=010010110101
0Å"1 ƒÄ… 1Å"1 ƒÄ… 0Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"0 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"0 ƒÄ… 1Å"0 2
0Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"0 4
OÅ"H= =
0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"1 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"0 3
[ ] [ ]
0Å"0 ƒÄ… 1Å"0 ƒÄ… 0Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"1 ƒÄ… 1Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"0 ƒÄ… 0Å"0 ƒÄ… 1Å"1 3
2 0
4 0
PR= modulo 2=
3 1
[ ] [ ]
3 1
Wystąpiło naruszenie bitu!
1 1 1 0 0 0 1 0 1 0 0 0
1 0 0 1 1 0 1 1 0 1 0 0
H =
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=010011110101
Poprawnie zakodowana litera O.
- 6 -
M =010011011011
0Å"1 ƒÄ… 1Å"1 ƒÄ… 0Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"0 ƒÄ… 1Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"0 ƒÄ… 1Å"0 2
0Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"0 ƒÄ… 1Å"0 2
MÅ"H = =
0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"1 ƒÄ… 1Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 1Å"0 4
[ ] []
0Å"0 ƒÄ… 1Å"0 ƒÄ… 0Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"0 ƒÄ… 1Å"0 ƒÄ… 1Å"1 4
2 0
2 0
PR= modulo 2=
4 0
[ ] [ ]
4 0
Poprawnie zakodowana litera M.
A=010000011101
0Å"1 ƒÄ… 1Å"1 ƒÄ… 0Å"1 ƒÄ… 0Å"0 ƒÄ… 0Å"0 ƒÄ… 0Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"0 ƒÄ… 1Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"0 ƒÄ… 1Å"0 2
0Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"0 ƒÄ… 0Å"1 ƒÄ… 0Å"1 ƒÄ… 0Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"1 ƒÄ… 1Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"0 2
AÅ"H = =
0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 0Å"1 ƒÄ… 0Å"0 ƒÄ… 0Å"1 ƒÄ… 0Å"1 ƒÄ… 1Å"1 ƒÄ… 1Å"0 ƒÄ… 1Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"0 2
[ ] []
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 0
2 0
PR= modulo 2=
2 0
[] []
2 0
Poprawnie zakodowana litera A.
S=010100010101
0Å"1 ƒÄ… 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 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"1 ƒÄ… 0Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"0 3
SÅ"H = =
0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 0Å"1 ƒÄ… 0Å"1 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"0 3
[ ] []
0Å"0 ƒÄ… 1Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"1 ƒÄ… 0Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"0 ƒÄ… 0Å"0 ƒÄ… 1Å"1 2
1 1
3 1
PR= modulo 2=
3 1
[] []
2 0
Wystąpiło naruszenie bitu!
1 1 1 0 0 0 1 0 1 0 0 0
1 0 0 1 1 0 1 1 0 1 0 0
H =
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
0Å"1 ƒÄ… 1Å"1 ƒÄ… 0Å"1 ƒÄ… 1Å"0 ƒÄ… 1Å"0 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"0 ƒÄ… 1Å"0 ƒÄ… 1Å"0 2
0Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 1Å"0 ƒÄ… 1Å"0 4
ZÅ"H = =
0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"1 ƒÄ… 0Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"0 ƒÄ… 1Å"1 ƒÄ… 1Å"0 4
[ ] [ ]
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
2 0
4 0
PR= modulo 2=
4 0
[ ] [ ]
2 0
Poprawnie zakodowana litera Z.
K =010010110110
0Å"1 ƒÄ… 1Å"1 ƒÄ… 0Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"0 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"0 ƒÄ… 1Å"0 ƒÄ… 0Å"0 2
0Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"0 4
KÅ"H= =
0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"1 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"0 4
[ ] [ ]
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
2 0
4 0
PR= modulo 2=
4 0
[ ] [ ]
2 0
Poprawnie zakodowana litera K.
P=010100001100
0Å"1 ƒÄ… 1Å"1 ƒÄ… 0Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"0 ƒÄ… 0Å"0 ƒÄ… 0Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"0 ƒÄ… 0Å"0 2
0Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"1 ƒÄ… 0Å"0 ƒÄ… 0Å"1 ƒÄ… 0Å"1 ƒÄ… 1Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 0Å"0 2
PÅ"H = =
0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 0Å"1 ƒÄ… 0Å"1 ƒÄ… 0Å"1 ƒÄ… 1Å"0 ƒÄ… 1Å"0 ƒÄ… 0Å"1 ƒÄ… 0Å"0 2
[ ] []
0Å"0 ƒÄ… 1Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"1 ƒÄ… 0Å"1 ƒÄ… 0Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"0 ƒÄ… 1Å"0 ƒÄ… 0Å"0 ƒÄ… 0Å"1 0
2 0
2 0
PR= modulo 2=
2 0
[] []
0 0
Poprawnie zakodowana litera P.
- 8 -
U =010101011000
0Å"1 ƒÄ… 1Å"1 ƒÄ… 0Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"0 ƒÄ… 1Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 0Å"0 ƒÄ… 0Å"0 2
0Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"1 ƒÄ… 1Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"1 ƒÄ… 0Å"0 ƒÄ… 0Å"0 2
UÅ"H= =
0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"0 ƒÄ… 1Å"1 ƒÄ… 0Å"1 ƒÄ… 1Å"1 ƒÄ… 1Å"0 ƒÄ… 0Å"0 ƒÄ… 0Å"1 ƒÄ… 0Å"0 4
[ ] []
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 0
2 0
PR= modulo 2=
4 0
[ ] [ ]
2 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 -