Distanța de lovire

Cub binar de 3 biți pentru a găsi distanța Hamming	Două exemple de distanță: 100 → 011 are distanța 3 (cale roșie); 010 → 111 h distanță 2 (traseu albastru)
Card binar pe 4 biți pentru a găsi distanța Hamming
Două exemple de distanță: 0100 → 1001 are o distanță de trei 3 (cale roșie); 0110 → 1110 are distanța 1 (traseu albastru)

În teoria informației , distanța Hamming între două șiruri de lungime egală este numărul de poziții în care simbolurile corespunzătoare sunt diferite. Cu alte cuvinte, distanța Hamming măsoară numărul de substituții necesare pentru a converti un șir la altul sau, văzut într-un alt mod, numărul minim de erori care ar fi putut duce la transformarea unui șir în altul.

Exemple

Distanța Hamming între 10 1 1 1 01 și 10 0 1 0 01 este 2.
Distanța Hamming între 2 14 3 8 96 și 2 23 3 7 96 este 3.

Greutatea Hamming a unui șir de lungime k este distanța de Hamming față de șirul format din k zerouri. Deci este numărul de elemente diferite de zero ale unui șir: pentru un șir binar este pur și simplu numărul 1; de exemplu, greutatea Hamming de 11101 este 4.

Proprietate

Pentru o lungime fixă $n$ ${\ displaystyle n}$ $n$ distanța Hamming este o metrică pe setul de șiruri care au acea lungime, deoarece satisface condițiile de non-negativitate, identitatea a două elemente cu distanță zero, simetrie și se poate arăta, prin inducție completă , că îndeplinește și inegalitate triunghiulară .

Distanța Hamming între două elemente $la$ ${\ displaystyle a}$ $la$ Și $b$ ${\ displaystyle b}$ $b$ este greutatea lui Hamming de $a-b$ ${\ displaystyle ab}$ $a-b$ , pentru o alegere adecvată a operatorului " $-$ ${\ displaystyle -}$ $-$ ".

Pentru două șiruri binare $la$ ${\ displaystyle a}$ $la$ Și $b$ ${\ displaystyle b}$ $b$ este echivalent cu operația $la$ ${\ displaystyle a}$ $la$ xor $b$ ${\ displaystyle b}$ $b$ . De asemenea, este echivalent cu distanța geometriei taxiului între două vârfuri ale unui hipercub $n$ ${\ displaystyle n}$ $n$ -dimensional, unde $n$ ${\ displaystyle n}$ $n$ este lungimea corzilor.

Istorie și aplicații

Distanța lui Hamming își ia numele de la Richard Hamming , care a introdus-o în lucrarea sa fundamentală privind recunoașterea erorilor și codurile de corectare . Este utilizat în telecomunicații pentru a număra numărul de biți eronați într-un cuvânt binar cu lungime fixă pentru a estima eroarea. Din acest motiv se mai numește și distanță de semnal . Analiza greutății Hamming a biților este utilizată în mai multe discipline, inclusiv teoria informației , teoria codului și criptografia . Cu toate acestea, pentru a compara șiruri de diferite lungimi sau șiruri pentru care sunt de așteptat și inserții și ștergeri, pe lângă substituții, este mai potrivit să se utilizeze valori mai sofisticate, cum ar fi distanța Levenshtein .

Bibliografie

Richard W. Hamming . Coduri de detectare a erorilor și de corectare a erorilor, Bell System Technical Journal 29 (2): 147-160, 1950.

Elemente conexe

Codul lui Hamming
Distanța Levenshtein , o generalizare a distanței Hamming

Controlul autorității	GND ( DE ) 4783883-8

Portal IT

Portalul de matematică