En teoría de la información , la distancia de Hamming entre dos cadenas o vectores de igual longitud es el número de posiciones en las que los símbolos correspondientes son diferentes. En otras palabras, mide el número mínimo de sustituciones necesarias para cambiar una cadena por otra o, de manera equivalente, el número mínimo de errores que podrían haber transformado una cadena en otra. En un contexto más general, la distancia de Hamming es una de varias métricas de cadena para medir la distancia de edición entre dos secuencias. Lleva el nombre del matemático estadounidense Richard Hamming .
Una aplicación importante es la teoría de la codificación , más específicamente para bloquear códigos , en los que las cadenas de igual longitud son vectores sobre un campo finito .
La distancia de Hamming entre dos cadenas de símbolos de igual longitud es el número de posiciones en las que los símbolos correspondientes son diferentes. [1]
Los símbolos pueden ser letras, bits o dígitos decimales, entre otras posibilidades. Por ejemplo, la distancia de Hamming entre:
Para una longitud fija n , la distancia de Hamming es una métrica sobre el conjunto de las palabras de longitud n (también conocida como espacio de Hamming ), ya que cumple las condiciones de no negatividad, simetría, la distancia de Hamming de dos palabras es 0 si y sólo si las dos palabras son idénticas, y también satisface la desigualdad del triángulo : [2] De hecho, si fijamos tres palabras a , b y c , entonces siempre que haya una diferencia entre la i -ésima letra de a y la i -ésima letra de c , entonces debe haber una diferencia entre la i- ésima letra de a y la i -ésima letra de b , o entre la i- ésima letra de b y la i- ésima letra de c . Por tanto, la distancia de Hamming entre a y c no es mayor que la suma de las distancias de Hamming entre a y b y entre b y c . La distancia de Hamming entre dos palabras a y b también puede verse como el peso de Hamming de a − b para una elección adecuada del operador −, de la misma manera que la diferencia entre dos números enteros puede verse como una distancia desde cero en la recta numérica. [ se necesita aclaración ]
Para las cadenas binarias a y b, la distancia de Hamming es igual al número de unos ( recuento de población ) en un XOR b . [3] El espacio métrico de cadenas binarias de longitud n , con la distancia de Hamming, se conoce como cubo de Hamming ; es equivalente como espacio métrico al conjunto de distancias entre vértices en un gráfico de hipercubo . También se puede ver una cadena binaria de longitud n como un vector tratando cada símbolo de la cadena como una coordenada real; con esta incrustación, las cuerdas forman los vértices de un hipercubo de n dimensiones , y la distancia de Hamming de las cuerdas es equivalente a la distancia de Manhattan entre los vértices.
La distancia mínima de Hamming o distancia mínima (normalmente denotada por dmin ) se utiliza para definir algunas nociones esenciales en la teoría de la codificación , como los códigos de detección y corrección de errores . En particular, se dice que un código C tiene k error al detectar si, y sólo si, la distancia mínima de Hamming entre dos de sus palabras de código cualesquiera es al menos k +1. [2]
Por ejemplo, considere un código que consta de dos palabras clave "000" y "111". La distancia de Hamming entre estas dos palabras es 3 y, por lo tanto, la detección de errores es k = 2. Esto significa que si se invierte un bit o dos bits, se puede detectar el error. Si se invierten tres bits, "000" se convierte en "111" y no se puede detectar el error.
Se dice que un código C corrige errores k si, para cada palabra w en el espacio de Hamming subyacente H , existe como máximo una palabra de código c (de C ) tal que la distancia de Hamming entre w y c sea como máximo k . En otras palabras, un código corrige k errores si la distancia mínima de Hamming entre dos de sus palabras de código es al menos 2 k +1. Esto también se entiende geométricamente como cualquier bola cerrada de radio k centrada en distintas palabras de código que está disjunta. [2] Estas bolas también se denominan en este contexto esferas de Hamming . [4]
Por ejemplo, considere el mismo código de 3 bits que consta de dos palabras de código "000" y "111". El espacio Hamming consta de 8 palabras 000, 001, 010, 011, 100, 101, 110 y 111. La palabra clave "000" y las palabras de error de un solo bit "001", "010", "100" son todas menores que o igual a la distancia de Hamming de 1 a "000". Asimismo, la palabra clave "111" y sus palabras de error de un solo bit "110", "101" y "011" están todas dentro de una distancia de 1 Hamming del "111" original. En este código, un error de un solo bit siempre está dentro de 1 distancia de Hamming de los códigos originales, y el código puede corregir 1 error , es decir k=1 . Dado que la distancia de Hamming entre "000" y "111" es 3, y éstas comprenden el conjunto completo de palabras en código en el código, la distancia mínima de Hamming es 3, lo que satisface 2k+1 = 3 .
Por lo tanto, un código con una distancia mínima de Hamming d entre sus palabras de código puede detectar como máximo errores d -1 y puede corregir errores ⌊( d -1)/2⌋. [2] Este último número también se denomina radio de empaquetamiento o capacidad de corrección de errores del código. [4]
La distancia de Hamming lleva el nombre de Richard Hamming , quien introdujo el concepto en su artículo fundamental sobre códigos Hamming , Códigos de detección y corrección de errores , en 1950. [5] El análisis del peso de Hamming de bits se utiliza en varias disciplinas, incluida la teoría de la información y la teoría de la codificación. y criptografía . [6]
Se utiliza en telecomunicaciones para contar el número de bits invertidos en una palabra binaria de longitud fija como estimación del error y, por lo tanto, a veces se le llama distancia de la señal . [7] Para cadenas q -arias sobre un alfabeto de tamaño q ≥ 2, la distancia de Hamming se aplica en el caso del canal simétrico q-ario , mientras que la distancia de Lee se utiliza para la manipulación por desplazamiento de fase o, más generalmente, para canales susceptibles a errores de sincronización. porque la distancia de Lee representa errores de ±1. [8] Si o ambas distancias coinciden porque algún par de elementos difieren de 1, pero las distancias son diferentes para mayores .
La distancia de Hamming también se utiliza en sistemática como medida de distancia genética. [9]
Sin embargo, para comparar cadenas de diferentes longitudes, o cadenas en las que no solo se deben esperar sustituciones sino también inserciones o eliminaciones, una métrica más sofisticada como la distancia de Levenshtein es más apropiada.
La siguiente función, escrita en Python 3, devuelve la distancia de Hamming entre dos cadenas:
def distancia_hamming ( cadena1 : cadena , cadena2 : cadena ) -> int : """Devuelve la distancia de Hamming entre dos cuerdas.""" si len ( cadena1 ) ! = len ( cadena2 ): rise ValueError ( "Las cadenas deben tener la misma longitud" ) . dist_counter = 0 para n en el rango ( len ( cadena1 )): si cadena1 [ n ] ! = cadena2 [ n ]: dist_counter += 1 devolver dist_counterO, en una expresión más corta:
suma ( char1 ! = char2 para char1 , char2 en zip ( cadena1 , cadena2 ))La función hamming_distance(), implementada en Python 3 , calcula la distancia de Hamming entre dos cadenas (u otros objetos iterables ) de igual longitud creando una secuencia de valores booleanos que indican discrepancias y coincidencias entre posiciones correspondientes en las dos entradas, luego sumando la secuencia con True y Valores falsos, interpretados como uno y cero, respectivamente.
def hamming_distance ( s1 : str , s2 : str ) -> int : """Devuelve la distancia de Hamming entre secuencias de igual longitud.""" if len ( s1 ) != len ( s2 ): rise ValueError ( "No definido para secuencias de longitud desigual." ) return sum ( char1 ! = char2 para char1 , char2 en zip ( s1 , s2 )) donde la función zip() fusiona dos colecciones de igual longitud en pares.
La siguiente función de C calculará la distancia de Hamming de dos números enteros (considerados como valores binarios, es decir, como secuencias de bits). El tiempo de ejecución de este procedimiento es proporcional a la distancia de Hamming más que al número de bits en las entradas. Calcula el bit a bit exclusivo o de las dos entradas y luego encuentra el peso Hamming del resultado (el número de bits distintos de cero) utilizando un algoritmo de Wegner (1960) que encuentra y borra repetidamente el bit distinto de cero de orden más bajo. Algunos compiladores admiten la función __builtin_popcount que puede calcular esto utilizando hardware de procesador especializado cuando esté disponible.
int hamming_distance ( x sin signo , y sin signo ) { int dist = 0 ; // Los operadores ^ establecen en 1 solo los bits que son diferentes para ( unsigned val = x ^ y ; val > 0 ; ++ dist ) { // Luego contamos el bit establecido en 1 usando la forma de Peter Wegner val = val & ( valor - 1 ); // Establecer en cero el orden más bajo de val 1 } // Devuelve el número de bits diferentes return dist ; } Una alternativa más rápida es utilizar la instrucción ensambladora de recuento de población ( popcount ). Ciertos compiladores como GCC y Clang lo hacen disponible mediante una función intrínseca:
// Distancia de Hamming para enteros de 32 bits int hamming_distance32 ( unsigned int x , unsigned int y ) { return __builtin_popcount ( x ^ y ); } // Distancia de Hamming para enteros de 64 bits int hamming_distance64 ( unsigned long long x , unsigned long long y ) { return __builtin_popcountll ( x ^ y ); } 
Este artículo incorpora material de dominio público de la Norma Federal 1037C. Administración de Servicios Generales . Archivado desde el original el 22 de enero de 2022.