Laboratorium 1 Kodowanie nadmiarowe kod Hamminga

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

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

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 oznaczamy .

Przykład:

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 . Formalnie można zapisać:

gdzie wynikiem operacji dodawania jest ciąg bitowy, którego wyrazami są sumy odpowiadających wyrazów ciągu i modulo .

Przykład:

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ść to można zapisać 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ść , gdzie oznacza przesyłane dane,
a odpowiadający im kod nadmiarowy. Odbiorca odbierze wiadomość .
Aby stwierdzić, czy otrzymane dane są poprawne odbiorca musi sam obliczyć kod nadmiarowy dla wiadomości , a następnie syndrom błędu, który z definicji jest równy . 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 , natomiast jako pierwszy sprawdzany jest bit na pozycji . I tak: