distancia de Hamming

Cubo binario de 3 bits para calcular la distancia de Hamming

Dos ejemplos de distancias: 100→011 tiene una distancia de 3; 010→111 tiene una distancia de 2.

La distancia mínima entre dos vértices cualesquiera es la distancia de Hamming entre las dos cadenas binarias.

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 transformar una cadena en la otra, o, equivalentemente, el número mínimo de errores que podrían haberla transformado. En un contexto más general, la distancia de Hamming es una de las diversas métricas de cadenas que se utilizan para medir la distancia de edición entre dos secuencias. Recibe su nombre del matemático estadounidense Richard Hamming .

Una aplicación importante se encuentra en la teoría de la 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:

• " ka rol in " y " ka thr in " es 3.
• " k a r ol in " y " k e r s in " es 3.
• " k athr in " y " k erst in " es 4.
• 0000 y 1111 es 4.
• 2 17 3 8 96 y 2 23 3 7 96 es 3.

Para una longitud fija n , la distancia de Hamming es una métrica en el conjunto de 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 también satisface 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 lo 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 manera similar a como la diferencia entre dos números enteros puede verse como una distancia desde cero en la recta numérica.

Para cadenas binarias a y b, la distancia de Hamming es igual al número de unos ( recuento de población ) en a 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 hipercubo . También se puede ver una cadena binaria de longitud n como un vector en${\displaystyle \mathbb {R} ^{n}}$al tratar cada símbolo de la cadena como una coordenada real; con esta incrustación, las cadenas forman los vértices de un hipercubo n- dimensional , y la distancia de Hamming de las cadenas es equivalente a la distancia de Manhattan entre los vértices.

La distancia de Hamming mínima o distancia mínima (generalmente denotada por d _min ) 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 es k- detector de errores si, y solo si, la distancia de Hamming mínima entre cualesquiera dos de sus palabras clave es al menos k + 1. ^{[ 2 ]}

Por ejemplo, consideremos un código compuesto por dos palabras clave: "000" y "111". La distancia de Hamming entre estas dos palabras es 3, por lo que su detección de errores es k = 2. Esto significa que si se invierte uno o dos bits, el error puede detectarse. Si se invierten tres bits, "000" se convierte en "111" y el error no puede detectarse.

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 clave 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 cualesquiera de sus palabras clave es al menos 2k + 1. Esto también se entiende geométricamente como que cualquier bola cerrada de radio k centrada en palabras clave distintas es disjunta. ^{[ 2 ]} Estas bolas también se denominan esferas de Hamming en este contexto. ^{[ 4 ]}

Por ejemplo, consideremos el mismo código de 3 bits que consta de las dos palabras clave "000" y "111". El espacio de Hamming consta de 8 palabras: 000, 001, 010, 011, 100, 101, 110 y 111. La palabra clave "000" y las palabras con un solo bit de error "001","010","100" son todas menores o iguales a la distancia de Hamming de 1 a "000". De manera similar, la palabra clave "111" y sus palabras con un solo bit de error "110","101" y "011" están todas dentro de 1 distancia de Hamming del "111" original. En este código, un solo bit de error siempre está dentro de 1 distancia de Hamming de los códigos originales, y el código puede ser corrector de 1 error , es decir, k=1 . Dado que la distancia de Hamming entre "000" y "111" es 3, y estos comprenden el conjunto completo de palabras clave en el código, la distancia de Hamming mínima es 3, que satisface 2k+1 = 3 .

Así, un código con una distancia de Hamming mínima d entre sus palabras clave puede detectar como máximo d -1 errores y 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 códigos de Hamming , Códigos de detección y corrección de errores , en 1950. ^{[ 5 ]} El análisis de pesos de Hamming de bits se utiliza en varias disciplinas, incluyendo 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 del 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, se aplica la distancia de Hamming 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, más generalmente, para canales susceptibles a errores de sincronización porque la distancia de Lee tiene en cuenta errores de ±1. ^{[ 8 ]} Si${\displaystyle q=2}$o${\displaystyle q=3}$ambas distancias coinciden porque cualquier par de elementos de${\textstyle \mathbb {Z} /2\mathbb {Z} }$o${\textstyle \mathbb {Z} /3\mathbb {Z} }$difieren en 1, pero las distancias son diferentes para valores mayores.${\displaystyle q}$.

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 puede ser más apropiada. ^{[ 10 ] : 32}

La siguiente función, escrita en Python 3, devuelve la distancia de Hamming entre dos cadenas:

def distancia_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_distancia = 0para n en rango ( longitud ( cadena1 )):Si string1 [ n ] != string2 [ n ]:contador_distancia += 1devolver dist_counter

La siguiente función en C calcula la distancia de Hamming entre dos 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, no al número de bits de entrada. Calcula la operación OR exclusiva bit a bit de las dos entradas y, a continuación, halla el peso de Hamming del resultado (el número de bits distintos de cero) mediante un algoritmo de Wegner (1960) que busca y borra repetidamente el bit distinto de cero de menor orden. Algunos compiladores admiten la función __builtin_popcount , que puede calcular esto utilizando hardware especializado del procesador, si está disponible.

int distancia_de_hamming ( unsigned x , unsigned y ) { int dist = 0 ;// El operador ^ establece a 1 solo los bits que son diferentes for ( unsigned val = x ^ y ; val > 0 ; ++ dist ) { // Luego contamos el bit establecido a 1 usando el método de Peter Wegner val = val & ( val - 1 ); // Establece a 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 conteo de población ( popcount ). Algunos compiladores, como GCC y Clang, la ponen a disposición 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 ); }

• Cadena más cercana
• Distancia de Damerau-Levenshtein
• distancia euclidiana
• Problema de Gap-Hamming
• Código gris
• Índice de Jaccard
• distancia de Jaro-Winkler
• distancia de Levenshtein
• Distancia de Mahalanobis
• Distancia a Mannheim
• Índice de similitud de Sørensen
• Memoria distribuida dispersa
• Escalera de palabras

•  Este artículo incorpora material de dominio público de la Norma Federal 1037C . Administración de Servicios Generales . Archivado del original el 22 de enero de 2022.
• Wegner, Peter (1960). "Una técnica para contar unos en una computadora binaria" . Communications of the ACM . 3 (5): 322. doi : 10.1145/367236.367286 . S2CID 31683715 . 
• MacKay, David JC (2003). Teoría de la información, inferencia y algoritmos de aprendizaje . Cambridge: Cambridge University Press . ISBN 0-521-64298-1.