Distància de Hamming

En teoria de l'informació es denomina distància d'Hamming a l'efectivitat dels còdics de bloc i depén de la diferència entre una paraula de còdic vàlida i una atra. Quant major siga esta diferència, menor és la possibilitat de que un còdic vàlit es transforme en un atre còdic vàlit per una série d'errors. A esta diferència se li crida distància de Hamming, i es definix com el número de bits que tenen que canviar-se per a transformar una paraula de còdic vàlida en una atra paraula de còdic vàlida.
Si dos paraules de còdic diferixen en una distancia d, es necessiten d errors per a convertir una en l'atra.

Per eixemple:

• La distància Hamming entre 1011101 i 1001001 és 2.
• La distància Hamming entre 2143896 i 2233796 és 3.
• La distància Hamming entre "tinir" i "risis" és 3.

Detecció i correcció d'errors

La distància de Hamming és utilisada per a definir algunes nocions essencials en teoria de còdics, tals com a còdics detectors d'errors i còdics correctors d'errors. En particular, es diu que un còdic $C$ detecta $k$-errors si dos paraules qualssevol $c_1,c_2\in C$ que tenen una distància de Hamming menor que $k$ coincidixen. Dit d'un atre modo, un còdic detecta $k$-errors si i solament si la distància de Hamming mínima entre dos paraules qualssevol en ell és a lo menys $k+1$.

Es diu que un còdic $C$ corrig $k$-errors si per a cada paraula $w$ en el subjacent espai de Hamming $H$ existix a lo manco una paraula $c\in C$ tal que la distància de Hamming entre $w$ i $c$ és menys que $k$. En atres paraules, un còdic corrig $k$-errors si i solament si la mínima distància de Hamming entre dos qualssevol de les seues paraules és per lo manco $2k+1$. Açò és més fàcil de comprendre geomètricament com que dos boles tancades qualssevol de radi $k$ centrades en distintes paraules són disjuntas. En este context es coneix a estes boles com a esferes de Hamming.

D'esta manera, un còdic que té distància de Hamming mínima $d$ entre les seues paraules pot detectar a lo més $d-1$ errors i pot corregir $\lfloor (d-1)/2\rfloor$ errors. Este últim número és també conegut com el radi d'empaquetat o la capacitat de correcció del còdic.

Història i aplicacions

La distància de Hamming es denomina aixina gràcies al seu inventor Richard Hamming, professor de l'Universitat de Nebraska, que va ser el que va introduir el terme per a establir una mètrica capaç d'establir un còdic per a la detecció i auto-correcció de còdics. S'ampra en la transmissió d'informació digitalisada per a contar el número de desviacions en cadenes d'igual llongitut i estimar l'error, per açò es denomina a voltes com a distància de senyal.

La distància de Hamming té les següents propietats.

• $d(a,b)=d(b,a)$
• $d(a,b)=0$ si i solament si $a=b$
• $d(a,b)+d(b,c)\ge d(a,c)$

a on d és el número de bits p que diferixen entre el mensage emés i el rebut.

Si $d\ge p+1$ llavors es pot detectar un error de pes p

Si $d\ge 2p+1$ llavors es pot corregir p dígits.

Eixemple: Si volem detectar 3 errors llavors la distància mínima de Hamming deu ser de $(3)+1=4$. Si volem corregir 3 errors llavors la distància mínima de Hamming deu ser de $2*(3)+1=7$.

Vore també

• Còdic Hamming
• Distància de Levenshtein