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 en otra, o equivalentemente, 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 cadenas para medir la distancia de edición entre dos secuencias. Recibe su nombre en honor al matemático estadounidense Richard Hamming .
Una aplicación importante es en la teoría de codificación , más específicamente en los códigos de bloques , 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 en el conjunto de las palabras de longitud n (también conocido 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 solo si las dos palabras son idénticas, y satisface también la desigualdad triangular : [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 apropiada del operador −, de la misma manera que la diferencia entre dos números enteros puede verse como una distancia desde cero en la línea numérica. [ aclaración necesaria ]
Para las cadenas binarias a y b, la distancia de Hamming es igual al número de unos ( número 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 grafo de hipercubo . También se puede ver una cadena binaria de longitud n como un vector en al tratar cada símbolo en la cadena como una coordenada real; con esta incrustación, las cadenas forman los vértices de un hipercubo de n dimensiones , y la distancia de Hamming de las cadenas es equivalente a la distancia de Manhattan entre los vértices.
La distancia mínima de Hamming o distancia mínima (usualmente denotada por d min ) se utiliza para definir algunas nociones esenciales en la teoría de codificación , como los códigos de detección de errores y de corrección de errores . En particular, se dice que un código C es k detector de errores si, y solo si, la distancia mínima de Hamming entre dos de sus palabras de código 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, detecta errores con 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 es corrector de k errores 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 es como máximo k . En otras palabras, un código es corrector de k errores si la distancia de Hamming mínima 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 palabras de código distintas que son disjuntas. [2] Estas bolas también se denominan esferas de Hamming en este contexto. [4]
Por ejemplo, considere el mismo código de 3 bits que consta de las dos palabras de código "000" y "111". El espacio de Hamming consta de 8 palabras 000, 001, 010, 011, 100, 101, 110 y 111. La palabra de código "000" y las palabras de error de un solo bit "001", "010", "100" son todas menores o iguales a la distancia de Hamming de 1 a "000". Del mismo modo, la palabra de código "111" y sus palabras de error de un solo bit "110", "101" y "011" están todas dentro de una distancia de Hamming de 1 del "111" original. En este código, un error de un solo bit siempre está dentro de una 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 estas comprenden el conjunto completo de palabras de código, la distancia de Hamming mínima es 3, lo que satisface 2k+1 = 3 .
Por lo tanto, un código con una distancia de Hamming mínima d entre sus palabras de código puede detectar como máximo d -1 errores y puede corregir ⌊( d -1)/2⌋ errores. [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 recibe su nombre de Richard Hamming , quien introdujo el concepto en su artículo fundamental sobre los códigos de Hamming , Códigos de detección y corrección de errores , en 1950. [5] El análisis del peso de Hamming de los bits se utiliza en varias disciplinas, incluidas la teoría de la información , la teoría de la codificación y la criptografía . [6]
Se utiliza en telecomunicaciones para contar el número de bits invertidos en una palabra binaria de longitud fija como una estimación de error y, por lo tanto, a veces se denomina distancia de 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 modulación por desplazamiento de fase o, de forma más general, para canales susceptibles a errores de sincronización porque la distancia de Lee explica errores de ±1. [8] Si o ambas distancias coinciden porque cualquier par de elementos de o difieren en 1, pero las distancias son diferentes para .
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 esperan 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_de_hamming ( cadena1 : str , cadena2 : str ) -> int : """Devuelve la distancia de Hamming entre dos cuerdas.""" si len ( cadena1 ) != len ( cadena2 ): generar ValueError ( "Las cadenas deben tener la misma longitud." ) contador_dist = 0 para n en el rango ( len ( string1 )): si cadena1 [ n ] != cadena2 [ n ]: contador_dist += 1 devolver dist_counterO, en una expresión más corta:
suma ( char1 != char2 para char1 , char2 en zip ( string1 , string2 , estricto = True ))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 desajustes y coincidencias entre posiciones correspondientes en las dos entradas, y luego sumando la secuencia con valores Verdadero y Falso, 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 ): raise ValueError ( "No definido para secuencias de longitud desigual." ) return sum ( char1 != char2 for char1 , char2 in zip ( s1 , s2 )) donde la función zip() fusiona dos colecciones de igual longitud en pares.
La siguiente función 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 en lugar de a la cantidad de bits en las entradas. Calcula la distancia de Hamming exclusiva bit a bit de las dos entradas y luego encuentra el peso de Hamming del resultado (la cantidad 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 ( sin signo x , sin signo y ) { 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 utilizando el método de Peter Wegner val = val & ( val - 1 ); // Establece en cero el 1 de orden más bajo de val } // Devuelve el número de bits diferentes return dist ; } Una alternativa más rápida es utilizar la instrucción de ensamblaje de recuento de población ( popcount ). Algunos compiladores, como GCC y Clang, la ponen a disposición a través de una función intrínseca:
// Distancia de Hamming para números enteros de 32 bits int hamming_distance32 ( unsigned int x , unsigned int y ) { return __builtin_popcount ( x ^ y ); } // Distancia de Hamming para números 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.