kodowanie

KODOWANIE A TRANSMISJA W KANAŁACH ŁĄCZNOŚCI Z ZAKŁÓCENIAMI

Odległość Hamminga

Definicja:

Odległością Hamminga [D(Sj, Sj)] między i-tym i j-tym wyrazem kodowym nazywamy liczbę pozycji, na których wyrazy Sj, Sj mają różne elementy binarne.

£>(S,Ą)= t ({/,,!{/,.)

k = 1

Formalnie:

# —"suma modułowa"

Uj_k, Uj_k elementy wyrazów kodowych Sj i Sj odpowiednio.

Dla kodu binarnego Qu = {0; 1}

L

Z(Sić/)= I IUi_k-U_Jk\

np. dla dwóch wyrazów kodowych S1 =001101 i S2 = 011110 D(S_1tS₂) = 3

Odległość Hamminga jest przydatnym parametrem do określania stopnia zabezpieczenia kodu przed przekłamaniem. Zatem spośród 2^L wyrazów kodowych trzeba wybrać n tak by minimalna odległość Hamminga była odpowiednio duża, gdyż tylko tak można uodpornić kod. Odległość Hamminga dla całego kodu, to minimum z odległości Hamminga dla wszystkich par zbioru. Ale no co taka minimalna odległość? Otóż dla pary, która różni się miedzy sobą na niewielu pozycjach najłatwiej o przekłamanie. Można z definicji odległości Hamminga wysnuć pewną radę istotną przy konstruowaniu kodu.

Jeśli chcemy wykryć m błędów, to odległość Hamminga dla całego kodu to: d > m + 1,

zaś gdy chcemy skorygować m błędów, to d > 2m + 1

Dlaczego tak jest?

Załóżmy, że jeśli odległość Hamminga dla danego kodu wynosi 5, to nie ma żadnej możliwości, by z jednego wyrazu kodowego przejść do innego zmieniając mniej niż 5 bitów. Jeśli zmienimy co najwyżej 4, to będziemy mieli wyraz nie występujący (zabroniony). Czyli wykryć musimy nawet 4 przekłamania (5=4+1). Zastanówmy sie ile przekłamań możemy naprawić.

Weźmy parę wyrazów, dla których odległość Hamminga wynosi 5 (czyli tyle, ile dla całego kodu — to najbardziej niebezpieczny przypadek) d(S₁,S₂) = 5