viernes, 6 de septiembre de 2019

LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS


 distancia de Hamming entre dos cadenas 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 requeridas para cambiar una cadena en la otra, o la cantidad mínima de errores que podrían haber transformado una cadena en la 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 los códigos de bloque , en los que las cadenas de igual longitud son vectores sobre un campo finito .

Cubo binario de 3 bits
Cubo binario de 3 bits para encontrar la distancia de Hamming
Ejemplos de distancia de Hamming de cubo binario de 3 bits
Dos distancias de ejemplo: 100 → 011 tiene una distancia 3; 010 → 111 tiene distancia 2
La distancia mínima entre dos vértices es la distancia de Hamming entre las dos cadenas binarias.





























































































































Tesseract binario de 4 bits
Tesseract binario de 4 bits para encontrar la distancia de Hamming.
Tesseract binario de 4 bits Ejemplos de distancia de Hamming
Dos distancias de ejemplo: 0100 → 1001 tiene distancia 3; 0110 → 1110 tiene distancia 1








Ejemplos editar ]

La distancia de Hamming entre:
  • ka rol in " y " ka thr in " son 3.
  • a r ol in " y " e r st in " es 3.
  • 10 1 1 1 01 y 10 0 1 0 01 es 2.
  • 17 3 8 96 y 23 3 7 96 es 3.

Propiedades editar ]

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, identidad de indiscernibles y simetría, y puede ser se muestra por inducción completa que también satisface la desigualdad del triángulo . [1] 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 -, tanto como la diferencia entre dos enteros puede verse como una distancia desde cero en la recta numérica.
Para las cadenas binarias a y b, la distancia de Hamming es igual al número de unidades ( conteo de población ) en un XOR b . [2] El espacio métrico de longitud n cadenas binarias, con la distancia de Hamming, se conoce como el 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 entratando cada símbolo en 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.

Detección de errores y corrección de errores editar ]

La distancia mínima de Hamming se utiliza para definir algunas nociones esenciales en la teoría de la codificación , como la detección de errores y los códigos de corrección de errores . En particular, se dice que un código C es k error al detectar si, y solo si, la distancia mínima de Hamming entre dos de sus palabras de código es al menos k +1. [1]
Se dice que un código C es k-errores que corrigen si, por cada palabra w en el espacio subyacente H de Hamming , existe a lo más 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 k -error que corrige si, y solo si, la distancia mínima de Hamming entre cualquiera de sus dos palabras de código es al menos 2 k +1. Esto se entiende más fácilmente geométricamente como cualquier bola cerrada de radio k centrada en palabras de código distintas que son disjuntas. [1]Estas bolas también se llaman esferas de Hamming en este contexto. [3]
Por lo tanto, un código con una distancia mínima de Hamming d entre sus palabras de código puede detectar a lo sumo errores d -1 y puede corregir errores ⌊ ( d -1) / 2⌋. [1] El último número también se llama radio de empaque o capacidad de corrección de errores del código. [3]

Historia y aplicaciones editar ]

La distancia de Hamming lleva el nombre de Richard Hamming , quien introdujo el concepto en su documento fundamental sobre códigos de Hamming Detección de errores y códigos de corrección de errores en 1950. [4] El análisis de peso de bits de Hamming se utiliza en varias disciplinas, incluidas la teoría de la información , la teoría de codificación y la criptografía .
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 le llama distancia de señal . [5] Para las cadenas q -ary sobre un alfabeto de tamaño q  ≥ 2, la distancia de Hamming se aplica en el caso del canal simétrico q-ary , mientras que la distancia Lee se usa para la codificación de desplazamiento de fase o, en general, canales susceptibles a errores de sincronización porque la distancia de Lee explica errores de ± 1. [6] Si o  ambas distancias coinciden porque cualquier par de elementos de  o  difieren en 1, pero las distancias son diferentes para grandes .
La distancia de Hamming también se usa en sistemática como una medida de la distancia genética. [7]
Sin embargo, para comparar cadenas de diferentes longitudes, o cadenas donde 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.
En las interconexiones del procesador, el consumo dinámico de energía depende del número de transiciones. Con el esquema de señalización de nivel, el número de transiciones depende de la distancia de Hamming entre buses transmitidos consecutivamente. [8] Por lo tanto, al reducir esta distancia de Hamming, la energía del movimiento de datos se puede reducir.

Ejemplo de algoritmo editar ]

La función hamming_distance(), implementada en Python 2.3+ , calcula la distancia de Hamming entre dos cadenas (u otros objetos iterables ) de igual longitud al crear una secuencia de valores booleanos que indican desajustes y coincidencias entre las posiciones correspondientes en las dos entradas y luego suma la secuencia con False y los valores verdaderos se interpretan como cero y uno.
def  hamming_distance ( s1 ,  s2 ): 
    "" "Devuelve la distancia de Hamming entre secuencias de igual longitud" "" 
    if  len ( s1 )  ! =  len ( s2 ): 
        raise  ValueError ( "Indefinido para secuencias de longitud desigual" ) 
    suma de retorno  ( el1 ! = el2 para el1 , el2 en zip ( s1 , s2 ))        
donde la función zip () combina dos colecciones de igual longitud en pares.
La siguiente función C calculará la distancia de Hamming de 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 en lugar de a la cantidad de bits en las entradas. Calcula la exclusiva bit a bit o de las dos entradas, y luego encuentra el peso de 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 inferior. Algunos compiladores admiten la función __builtin_popcount que puede calcular esto utilizando hardware de procesador especializado donde esté disponible.
int  hamming_distance ( unsigned  x ,  unsigned  y ) 
{ 
    int  dist  =  0 ;
    
    // Cuente el número de bits establecido 
    para  ( unsigned  val  =  x  ^  y ;  val  >  0 ;  val  / =  2 ) 
    { 
        // Si se establece un bit, incremente el recuento 
        if  ( val  &  1 ) 
            dist ++ ; 
        // Borrar (eliminar) el bit de orden más bajo de val 
    }

    // Devuelve el número de bits diferentes 
    return  dist ; 
}
O, una alternativa de hardware mucho más rápida (para compiladores que admiten builtins) es usar popcount como tal.
int  hamming_distance ( unsigned  x ,  unsigned  y ) 
{ 
    return  __builtin_popcount ( x  ^  y ); 
} 
// si su compilador admite enteros de 64 bits 
int  hamming_distance ( unsigned  long  long  x ,  unsigned  long  long  y ) 
{ 
    return  __builtin_popcountll ( x  ^  y ); 


















No hay comentarios:

Publicar un comentario