Co to jest odległość Hamminga?

Dystans Hamminga

Dystans Hamminga jest metryką służącą do porównywania dwóch binarnych ciągów danych. Podczas porównywania dwóch ciągów binarnych o równej długości, odległość Hamminga jest liczbą pozycji bitowych, w których dwa bity są różne.

Dystans Hamminga między dwoma ciągami, a i b jest oznaczany jako d(a,b).

Jest on używany do wykrywania błędów lub korekcji błędów, gdy dane są przesyłane przez sieci komputerowe. Jest również używany w teorii kodowania do porównywania słów danych o równej długości.

Obliczanie odległości Hamminga

Aby obliczyć odległość Hamminga między dwoma ciągami, i , wykonujemy ich operację XOR, (a⊕ b), a następnie liczymy całkowitą liczbę 1s w wynikowym ciągu.

Przykład

Załóżmy, że istnieją dwa ciągi 1101 1001 i 1001 1101.

11011001 ⊕ 10011101 = 01000100. Ponieważ, zawiera on dwie jedynki, odległość Hamminga, d(11011001, 10011101) = 2.

Minimalna odległość Hamminga

W zbiorze ciągów o równych długościach, minimalna odległość Hamminga jest najmniejszą odległością Hamminga pomiędzy wszystkimi możliwymi parami ciągów w tym zbiorze.

Przykład

Załóżmy, że istnieją cztery ciągi 010, 011, 101 i 111.

.