Ce este distanța Hamming?

Distanța Hamming

Distanța Hamming este o metrică pentru compararea a două șiruri de date binare. În timp ce se compară două șiruri binare de lungime egală, distanța Hamming reprezintă numărul de poziții de biți în care cei doi biți sunt diferiți.

Distanța Hamming între două șiruri, a și b este notată ca d(a,b).

Este utilizată pentru detectarea sau corectarea erorilor atunci când datele sunt transmise prin rețele de calculatoare. Este, de asemenea, utilizată în teoria codificării pentru compararea cuvintelor de date de lungime egală.

Calcularea distanței Hamming

Pentru a calcula distanța Hamming între două șiruri, și , efectuăm operația XOR a acestora, (a⊕ b), și apoi numărăm numărul total de 1-uri din șirul rezultat.

Exemplu

Să presupunem că există două șiruri 1101 1001 și 1001 1101.

11011001 ⊕ 10011101 = 01000100. Deoarece, aceasta conține doi 1, distanța Hamming, d(11011001, 10011101) = 2.

Distanța Hamming minimă

Într-un set de șiruri de lungimi egale, distanța Hamming minimă este cea mai mică distanță Hamming între toate perechile posibile de șiruri din acel set.

Exemplu

Să presupunem că există patru șiruri 010, 011, 101 și 111.

.