Distanţă Hamming

De la Wikipedia, enciclopedia liberă

Cub binar pe 3 biţi pentru găsirea distanţei Hamming	Două exemple de distanţe: 100->011 are distanţa 3 (drumul roşu); 010->111 are distanţa 2 (drumul albastru)
Hipercub binar pe 4 biţi pentru găsirea distanţei Hamming
Două exemple de distanţe: 0100->1001 are distanţa 3 (drumul roşu); 0110->1110 are distanţa 1 (drumul albastru)

În teoria informaţiei, distanţa Hamming dintre două şiruri de lungime egală este numărul de poziţii ale căror simboluri corespunzătoare sunt diferite. Cu alte cuvinte, ea măsoară numărul minim de substituţii necesare pentru a schimba un şir în celălalt, sau numărul minim de erori care au transformat un şir în celălalt.

[modifică] Exemple

Distanţa Hamming dintre:

• 1011101 şi 1001001 este 2.
• 2173896 şi 2233796 este 3.
• "pacte" şi "carte" este 2.

[modifică] Proprietăţi speciale

Pentru o lungime fixată n, distanţa Hamming este o metrică în spaţiul vectorial al cuvintelor de această lungime, deoarece în mod evident îndeplineşte condiţiile de ne-negativitate, reflexivitate şi simetrie, şi poate fi demonstrat uşor prin inducţie completă că satisface şi inegalitatea triunghiulară. Distanţa Hamming dintre două cuvinte a şi b poate fi văzută şi ca ponderea Hamming pentru a−b, la o alegere potrivită a operatorului −.

Pentru şirurile binare a şi b, distanţa Hamming este egală cu numărul de biţi 1 din a xor b. Spaţiul metric al şirurilor binare de lungime n, împreună cu distanţa Hamming, este cunoscut drept cubul Hamming. Un şir binar de lungime n poate fi văzut şi ca un vector în considerând fiecare simbol ca o coordonată reală; în aceste condiţii, şirurile formează vârfurile unui hipercub n-dimensional, iar distanţa Hamming a şirurilor este echivalentă distanţei Manhattan dintre vârfuri.