Ćwiczenia z sieci komputerowych. Semestr VI. 15-02-1999.

Kodem (algorytmem) nazywamy przyporządkowanie wiadomości x_i do określonego ciągu symboli alfabetu kodowego (ciągu zwanego słowem kodowym) w_i.

Kodowaniem nazywamy proces przekształcania wiadomości w słowa kodowe.

Kod jest jednoznacznie dekodowalny jeśli każdemu ciągowi kodowemu odpowiada co najwyżej jedna wiadomość.

WKW by kod był kodem jednoznacznie dekodowalnym bez opóźnień jet żeby żadne słowo nie było użyte jako przedrostek (przyrostek) innego słowa kodowego tego kodu.

Kody dzielą się na nadmiarowe (do transmisji w kanałach z zakłóceniami) i beznadmiarowe.

Kodem nadmiarowym nazywamy kod w którym przy całkowitej ilości pozycji słowa kodowego wynoszącej n , k z tych pozycji wykorzystywanych jest do kodowania informacji (wiadomości) zaś n - k = m pozycji jest nadmiarowych i wykorzystywanych do kontroli (wykrywania lub korygowania błędów).

Kody binarne to kody określone przez układ równań liniowo niezależnych:

Gdzie

j=1..m

w_l - l-ty bit słowa kodowego

T_jl - 1 jeśli l-ta pozycja słowa kodowego wchodzi do j-go równania, lub 0 w przeciwnym przypadku;

Są to tzw. równania testów parzystości kodu.

Kody binarne dzielą się jak na poniższym schemacie:

Dla kodów binarnych mówimy, że pozycje objęte j-tym równaniem sa j-tym zespoełem kontrolnym.

Kod Hamminga skonstruowany jest jak następuje:

n = 2^m-1

gdzie:

n - liczba pozycji w słowie kodowym

m - liczba pozycji kontrolnych;

W kodzie Hamminga pozycje kontrolne wskazywane są przez kolejne potęgi liczby 2 (1, 2, 4, 8..).

Zasady tworzenia słowa kodowego dla kodu Hamminga:

Numer zespołu kontrolego (j)	Pozycja kontrolna (bit słowa kodowego)	Pozycje objęte zespołem kontrolnym
1	2^0	3, 5, 7, 9, ...
2	2^1	3, 6, 7, 10, 11, 14, 15, ...
3	2^2	5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, ...
4	2^3	9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27, 28, 29, 30, 31, ...
...	...	...

Przykład:

Zakodować kodem Hamminga liczbę 134₈.

wiadomość: 134₈ == 1 011 100₂

1	0	1	0	1	1	0	0	0	1	1	słowo kodowe
11	10	9	8	7	6	5	4	3	2	1	poz. słowa kodowego
x		x		x		x		x			zespół kontrolny nr 1
x	x			x	x			x			zespół kontrolny nr 2
				x	x	x					zespół kontrolny nr 3
x	x	x									zespół kontrolny nr 4

Na zespół kontrolny nr 1 wchodzą tu bity 3, 5, 7, 9, 11. Z bitów tych wyznaczamy sumę modulo 2 i wynik wpisujemy na pozycję zespołu tj. na bit nr 1.

Na zespół kontrolny nr 2 wchodzą tu bity 3, 6, 7, 10, 11. Z bitów tych wyznaczamy sumę modulo 2 i wynik wpisujemy na pozycję zespołu tj. na bit nr 2.

Na zespół kontrolny nr 3 wchodzą tu bity 5, 6, 7 (następne byłyby 12, 13, 14, 15 ale nie ma potrzeby brania ich pod uwagę). Z bitów tych wyznaczamy sumę modulo 2 i wynik wpisujemy na pozycję zespołu tj. na bit nr 4.

Na zespół kontrolny nr 4 wchodzą tu bity 9, 10, 11 (nie ma potrzeby brania następnych bitów pod uwagę). Z bitów tych wyznaczamy sumę modulo 2 i wynik wpisujemy na pozycję zespołu tj. na bit nr 8.

W celu sprawdzenia poprawności otrzymanego ciągu kodowego wyznacza się tzw. syndrom. Syndrom jest wyliczany dla pozycji kontrolnych w sposób analogiczny do obliczania zespołów kontrolnych przy czym w skład sumy modulo 2 wchodzą dodatkowo te pozycje kontrolne. Dla poprzedniego przykładu zasadę wyznaczenia syndromu zilustrowana jest poniżej:

1	0	1	0	1	1	0	0	0	1	1	słowo kodowe
11	10	9	8	7	6	5	4	3	2	1	poz. słowa kodowego
x		x		x		x		x		x	zespół kontr. nr 1 syndromu
x	x			x	x			x	x		zespół kontr. nr 2 syndromu
				x	x	x	x				zespół kontr. nr 3 syndromu
x	x	x	x								zespół kontr. nr 4 syndromu

Dla pozycji nr 1 syndromu mamy sumę modulo 2 z pozycji 1, 3, 5, 7, 9, 11 czyli tu: 0.

Dla pozycji nr 2 syndromu mamy sumę modulo 2 z pozycji 2, 3, 6, 7, 10, 11 czyli tu: 0.

Dla pozycji nr 4 syndromu mamy sumę modulo 2 z pozycji 4, 5, 6, 7 czyli tu: 0.

Dla pozycji nr 8 syndromu mamy sumę modulo 2 z pozycji 8, 9, 10, 11 czyli tu: 0.

Otrzymany syndrom:

2^0	2^1	2^2	2^3	zespół
0	0	0	0	wartość zespołu
0*1	0*2	0*4	0*8	= 0 (wartość syndromu)

Jeśli syndrom wynosi 0 to znaczy, że otrzymany ciąg jest prawidłowy w rozumieniu możliwości kontroli kodu Hamminga.

Niezerowa wartość syndromu wskazuje bezpośrednio na pozycję przekłamania.

Przykład:

W poprzednim przykładzie nastąpiło przekłamanie na pozycji 6. Przykład poniższy ilustruje sposób jego wykrycia.

1	0	1	0	1	0	0	0	0	1	1	słowo kodowe
11	10	9	8	7	6	5	4	3	2	1	poz. słowa kodowego
x		x		x		x		x		x	=0 zespół kontr. nr 1 syndromu
x	x			x	x			x	x		=1 zespół kontr. nr 2 syndromu
				x	x	x	x				=1 zespół kontr. nr 3 syndromu
x	x	x	x								=0 zespół kontr. nr 4 syndromu

skąd syndrom:

2^0	2^1	2^2	2^3	zespół
0	1	1	0	wartość zespołu
0*1	1*2	1*4	0*8	= 6 (wartość syndromu czyli pozycja przekłamania)

Jeśli syndrom wskazuje pozycję istniejącą w słowie kodowym a po poprawieniu przekłamania i ponownym wyliczeniu syndromu nadal ma on wartość niezerową to znaczy, że nastąpiły przekłamania wielokrotne. Kod Hamminga nie pozwala na korygowanie przekłamań wielokrotnych.

Jeśli obliczony w dowolnym momencie syndrom wskazuje na pozycję nieistniejącą, to również mamy do czynienia z przekłamaniami wielokrotnymi.

Zadania:

1. Zakodować w kod Hamminga liczbę 11.

1	0	1	0	1	0	1	słowo kodowe
7	6	5	4	3	2	1	poz. słowa kodowego
x		x		x			zespół kontrolny nr 1
x	x			x			zespół kontrolny nr 2
x	x	x					zespół kontrolny nr 3

2. Zakodować w kod Hamminga liczbę 1979.

3. Wykryć przekłamanie w słowie kodowym 1010001.

4. Obliczyć syndrom odebranego ciągu 111011110101011.

beznadmiarowe

nadmiarowe

równomierne

(np. Gray`a, Excess 3, Aikena)

nierównomierne

(np. Huffmana, Shannona-Fano)

blokowe

nieblokowe

nieliniowe

liniowe

(np. Hamminga, cykliczne)

---