Odległość Hamminga

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Odległość Hamminga (ang. Hamming distance) D_H – w teorii informacji jest to wprowadzona przez Richarda Hamminga miara odmienności dwóch ciągów o takiej samej długości, wyrażająca liczbę miejsc (pozycji), na których te dwa ciągi się różnią. Innymi słowy jest to najmniejsza liczba zmian (operacji zastępowania elementu innym), jakie pozwalają przeprowadzić jeden ciąg na drugi.

Własności[edytuj | edytuj kod]

Dla ustalonej długości n, odległość Hamminga jest metryką na przestrzeni wektorowej słów o tej długości, ponieważ spełnia warunki: jest nieujemna, symetryczna, a stosując metodę indukcji zupełnej można pokazać, że spełnia również nierówność trójkąta. Odległość Hamminga dwóch słów a i b można także interpretować jako ciężar Hamminga słowa ab dla odpowiedniego wyboru operatora −.

Dla ciągów binarnych a i b odległość Hamminga jest równa liczbie jedynek w słowie a XOR b. Przestrzeń metryczna słów binarnych o długości n, z odległością Hamminga, jest nazywana kostką Hamminga. Słowa binarne o długości n moża traktować jako wektory w przestrzeni \mathbb{R}^n przyjmując każdy symbol w łańcuchu jako współrzędną rzeczywistą; przy tym zanurzeniu takie łańcuchy stanowią wierzchołki n-wymiarowej hiperkostki, a odległość Hamminga słów jest równoważna metryce taksówkowej pomiędzy wierzchołkami.

Opis[edytuj | edytuj kod]

Ścisła implementacja zależy oczywiście od definicji użytych ciągów. Na przykład dwa ciągi bajtów zapisanych w pamięci komputera można, zależnie od potrzeb, potraktować jako ciągi binarne lub ciągi literowe zakodowane w ASCII; odpowiednio odległość Hamminga będziemy definiować jako liczbę różnych bitów lub różnych bajtów.

Odległość Hamminga pozwala określić pewne właściwości kodowania:

  • możliwa liczba korekcji błędów jest mniejsza niż \begin{matrix}\frac{D_H-1}{2}\end{matrix},
  • możliwa liczba detekcji błędów jest mniejsza niż D_H.

Następnie można określić, że dla:

  • D_H = 1 – nie jest możliwe wykrycie błędów,
  • D_H = 2 – jest możliwe wykrycie błędu, jednak niemożliwa jest korekcja,
  • D_H = 3 – możliwa jest korekcja.

Przykłady:

  • odległość pomiędzy ciągami 10011101 i 10111001 wynosi 2.
  • odległość pomiędzy ciągami zagrabić i zatrąbił wynosi 3.

Uogólnieniem odległości Hamminga jest odległość Levenshteina, uwzględniająca nie tylko zamianę znaku na inny, ale także wstawianie i usuwanie znaków z ciągu (a więc obejmująca napisy o różnych długościach).