Co je Hammingova vzdálenost?

Hammingova vzdálenost

Hammingova vzdálenost je metrika pro porovnání dvou binárních datových řetězců. Při porovnávání dvou binárních řetězců stejné délky je Hammingova vzdálenost počtem bitových pozic, ve kterých se oba bity liší.

Hammingova vzdálenost mezi dvěma řetězci a a b se označuje jako d(a,b).

Používá se k detekci nebo opravě chyb při přenosu dat po počítačových sítích. Používá se také v teorii kódování pro porovnávání stejně dlouhých datových slov.

Výpočet Hammingovy vzdálenosti

Pro výpočet Hammingovy vzdálenosti mezi dvěma řetězci a , provedeme jejich operaci XOR, (a⊕ b), a poté spočítáme celkový počet jedniček ve výsledném řetězci.

Příklad

Předpokládejme, že existují dva řetězce 1101 1001 a 1001 1101.

11011001 ⊕ 10011101 = 01000100. Protože obsahuje dvě jedničky, je Hammingova vzdálenost d(11011001, 10011101) = 2.

Minimální Hammingova vzdálenost

V množině řetězců stejných délek je minimální Hammingova vzdálenost nejmenší Hammingova vzdálenost mezi všemi možnými dvojicemi řetězců v této množině.

Příklad

Předpokládejme, že existují čtyři řetězce 010, 011, 101 a 111.

.