Distancia de Hamming - norman-ipn/Errores GitHub Wiki

En Teoría de la Información se denomina distancia de Hamming a la efectividad de los códigos de bloque y depende de la diferencia entre una palabra de código válida y otra. Cuanto mayor sea esta diferencia, menor es la posibilidad de que un código válido se transforme en otro código válido por una serie de errores. A esta diferencia se le llama distancia de Hamming, y se define como el número de bits que tienen que cambiarse para transformar una palabra de código válida en otra palabra de código válida. Si dos palabras de código difieren en una distancia d, se necesitan d errores para convertir una en la otra.

Por ejemplo:

La distancia Hamming entre 1011101 y 1001001 es 2.
La distancia Hamming entre 2143896 y 2233796 es 3.
La distancia Hamming entre "tener" y "reses" es 3.

Algoritmo

consiste en comprar caracter por caracter, dando como resultados el numero de caracteres diferentes que existen entre una cadena y otra.

En el siguiente ejemplo, comparamos 2 cadenas, en este caso usamos h1=DISTANCIA y h2=DISTROSION :

Vamos evaluando caracter por caracter:

Historia y aplicaciones

La distancia de Hamming se denomina así gracias a su inventor Richard Hamming, profesor de la Universidad de Nebraska, que fue el que introdujo el término para establecer una métrica capaz de establecer un código para la detección y auto-corrección de códigos. Se emplea en la transmisión de información digitalizada para contar el número de desvíos en cadenas de igual longitud y estimar el error, por esto se denomina a veces como distancia de señal.

"d" es el nº de bits "p" en que son diferentes el mensaje emitido del recibido.
Si d=> p+1 entonces se puede detectar un error de peso "p"
Si d=> 2p+1 entonces se puede corregir p dígitos.

Ejemplo: Si queremos detectar 3 errores entonces la distancia mínima de Hamming debe ser de (3)+1 = 4. Si queremos corregir 3 errores entonces la distancia mínima de Hamming debe ser de 2*(3)+1 = 7.

Bibliografía

Distancia de Hamming: http://es.wikipedia.org/wiki/Distancia_de_Hamming

Distancia de Hamming: https://sites.google.com/site/algoritmossimilaridaddistancia/distancia-de-hamming