En teoria de la informacion se denomina distancia de Hamming a la efectividad de los codigos de bloque y depende de la diferencia entre una palabra de codigo valida y otra. Cuanto mayor sea esta diferencia, menor es la posibilidad de que un codigo valido se transforme en otro codigo valido por una serie de errores. A esta diferencia se le llama distancia de Hamming, y se define como el numero de bits que tienen que cambiarse para transformar una palabra de codigo valida en otra palabra de codigo valida.
Si dos palabras de codigo difieren en una distancia d , se necesitan d errores para convertir una en la otra.

Por ejemplo:

• La distancia Hamming entre 10 1 1 1 01 y 10 0 1 0 01 es 2.
• La distancia Hamming entre 2 14 3 8 96 y 2 23 3 7 96 es 3.
• La distancia Hamming entre " t e n e r " y " r e s e s " es 3.

Deteccion y correccion de errores [ editar ]

La distancia de Hamming es utilizada para definir algunas nociones esenciales en teoria de codigos, tales como codigos detectores de errores y codigos correctores de errores . En particular, se dice que un codigo ${\displaystyle C}$ detecta ${\displaystyle k}$-errores si dos palabras cualesquiera ${\displaystyle c_{1},c_{2}\in C}$ que tienen una distancia de Hamming menor que ${\displaystyle k}$ coinciden. Dicho de otro modo, un codigo detecta ${\displaystyle k}$-errores si y solo si la distancia de Hamming minima entre dos palabras cualesquiera en el es a lo menos ${\displaystyle k+1}$.

Se dice que un codigo ${\displaystyle C}$ corrige ${\displaystyle k}$-errores si para cada palabra ${\displaystyle w}$ en el subyacente espacio de Hamming ${\displaystyle H}$ existe al menos una palabra ${\displaystyle c\in C}$ tal que la distancia de Hamming entre ${\displaystyle w}$ y ${\displaystyle c}$ es menos que ${\displaystyle k}$. En otras palabras, un codigo corrige ${\displaystyle k}$-errores si y solo si la minima distancia de Hamming entre dos cualesquiera de sus palabras es por lo menos ${\displaystyle 2k+1}$. Esto es mas facil de comprender geometricamente como que dos bolas cerradas cualesquiera de radio ${\displaystyle k}$ centradas en distintas palabras son disjuntas. En este contexto se conoce a estas bolas como esferas de Hamming .

De esta manera, un codigo que tiene distancia de Hamming minima ${\displaystyle d}$ entre sus palabras puede detectar a lo mas ${\displaystyle d-1}$ errores y puede corregir ${\displaystyle \lfloor (d-1)/2\rfloor }$ errores. Este ultimo numero es tambien conocido como el radio de empaquetado o la capacidad de correccion del codigo.

Historia y aplicaciones [ editar ]

La distancia de Hamming se denomina asi gracias a su inventor Richard Hamming , profesor de la Universidad de Nebraska, que fue el que introdujo el termino para establecer una metrica capaz de establecer un codigo para la deteccion y auto-correccion de codigos . Se emplea en la transmision de informacion digitalizada para contar el numero de desvios en cadenas de igual longitud y estimar el error, por esto se denomina a veces como distancia de senal .

La distancia de Hamming tiene las siguientes propiedades.

• ${\displaystyle d(a,b)=d(b,a)}$
• ${\displaystyle d(a,b)=0}$ si y solo si ${\displaystyle a=b}$
• ${\displaystyle d(a,b)+d(b,c)\geq d(a,c)}$

donde d es el numero de bits p que difieren entre el mensaje emitido y el recibido.

Si ${\displaystyle d\geq p+1}$ entonces se puede detectar un error de peso p

Si ${\displaystyle d\geq 2p+1}$ entonces se puede corregir p digitos.

Ejemplo: Si queremos detectar 3 errores entonces la distancia minima de Hamming debe ser de ${\displaystyle (3)+1=4}$. Si queremos corregir 3 errores entonces la distancia minima de Hamming debe ser de ${\displaystyle 2*(3)+1=7}$.

Vease tambien [ editar ]

• Codigo Hamming
• Distancia de Levenshtein