Peso de Hamming

+EjemplosCadena de caracteresPeso de Hamming11101411101000400000000067801234056710

El peso de Hamming de una cadena de caracteres es el número de símbolos que son diferentes del símbolo cero del alfabeto utilizado. Por lo tanto, es equivalente a la distancia de Hamming de la cadena de ceros de la misma longitud. Para el caso más típico, una cadena de bits, este es el número de unos en la cadena, o la suma de dígitos de la representación binaria de un número dado y la norma ℓ₁ de un vector de bits. En el caso binario, también se denomina recuento de población, suma lateral, o suma de bits.

Historia y uso La función lleva el nombre de Richard Hamming, aunque él no originó el concepto. El peso de Hamming de los números binarios ya fue utilizado en 1899 por James W. L. Glaisher para dar una fórmula para el número de coeficientes binomiales impares en una sola fila del triángulo de Pascal. Irving Stoy Reed también introdujo en 1954 un concepto equivalente en el caso binario.

El peso de Hamming se usa en varias disciplinas, incluidas la teoría de la información, la teoría de códigos y la criptografía. Ejemplos de aplicaciones del peso de Hamming incluyen: La exponenciación binaria modular; el número de multiplicaciones modulares necesarias para un exponente e es . Esta es la razón por la que el valor de la clave pública e que se utiliza en RSA normalmente se elige como un número de bajo peso de Hamming. El peso de Hamming determina las longitudes de ruta entre nodos en las tablas del algoritmo Chord. Las técnicas de reconocimiento de iris en las bases de datos biométricas se implementan normalmente calculando la distancia de Hamming de cada registro almacenado. En los programas de ajedrez por computadora que utilizan una representación bitboard, el peso de Hamming de un tablero de bits da el número de piezas de un tipo determinado que quedan en el juego, o el número de casillas del tablero controlado por las piezas de un jugador y, por lo tanto, es un término contribuyente importante al valor de una posición. El peso de Hamming se puede usar para encontrar el primer conjunto de manera eficiente usando la identidad . Esto es útil en plataformas como Sun SPARC que tienen instrucciones de peso de Hamming de hardware pero ninguna instrucción de primer conjunto de búsqueda de hardware. La operación de peso de Hamming se puede interpretar como una conversión del sistema de numeración unario al sistema binario. En el manejo de algunas estructuras de datos sucintas como los vectores de bits y los árboles de ondas.

Cálculo eficiente

El conteo de población de un flujo de datos a menudo se necesita en criptografía y otras aplicaciones. La distancia de Hamming de dos palabras A y B se puede calcular como el peso de Hamming de exclusivamente A o B.

El problema de cómo determinarlo de manera eficiente ha sido ampliamente estudiado. Una sola operación para el cálculo, u operaciones paralelas sobre vectores de bits son disponible en algunos procesadores. Para los procesadores que carecen de esas funciones, las mejores soluciones conocidas se basan en agregar cuentas en un patrón de árbol. Por ejemplo, para contar el número de 1 bits en el número binario de 16 bits a = 0110 1100 1011 1010, se pueden realizar estas operaciones:

ExpresiónBinaria Decimal Comentarioa0110110010111010style="text-align:left;" El número originalb0= (a >> 0) & 01 01 01 01 01 01 01 0101000100000100001, 0, 1, 0, 0, 1, 0, 0Cada otro bit de ab1= (a >> 1) & 01 01 01 01 01 01 01 0100010100010101010, 1, 1, 0, 1, 1, 1, 1Los bits restantes de ac= b0 + b101011000011001011, 1, 2, 0, 1, 2, 1, 1Recuento de unos en cada porción de 2 bits de ad0= (c >> 0) & 0011 0011 0011 001100010000001000011, 0, 2, 1Todos los demás contados desde cd2= (c >> 2) & 0011 0011 0011 001100010010000100011, 2, 1, 1Los restantes contados desde ce= d0 + d200100010001100102, 2, 3, 2Recuento de unos en cada porción de 4 bits de af0= (e >> 0) & 00001111 0000111100000010000000102, 2Todos los demás contados desde ef4= (e >> 4) & 00001111 0000111100000010000000112, 3El resto contados desde eg= f0 + f400000100000001014, 5Recuento de unos en cada segmento de 8 bits de ah0= (g >> 0) & 000000001111111100000000000001015Todos los demás contados desde gh8= (g >> 8) & 000000001111111100000000000001004El resto contados desde gi= h0 + h800000000000010019Recuento de unos en una palabra completa de 16 bits

Aquí, las operaciones son como en lenguaje de programación C, por lo que significa desplazar X a la derecha en Y bits, X & Y significa el AND bit a bit de X e Y, y + es una suma ordinaria. Los mejores algoritmos conocidos para este problema se basan en el concepto ilustrado anteriormente y se proporcionan aquí:

//Tipos de variables y constantes usados ​​en las siguientes funciones //uint64_t es un tipo de variable entera de 64 bits sin signo (definida en la versión C99 del lenguaje C) const uint64_t m1= 0x5555555555555555; //binary: 0101... const uint64_t m2= 0x3333333333333333; //binary: 00110011.. const uint64_t m4= 0x0f0f0f0f0f0f0f0f; //binary: 4 zeros, 4 ones ... const uint64_t m8= 0x00ff00ff00ff00ff; //binary: 8 zeros, 8 ones ... const uint64_t m16= 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ... const uint64_t m32= 0x00000000ffffffff; //binary: 32 zeros, 32 ones const uint64_t h01= 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3...

//Esto es un ejemplo simple, que se muestra a modo de comparación, //y para ayudar a comprender mejor las funciones. //El algoritmo utiliza 24 operaciones aritméticas (shift, add, and). int popcount64a(uint64_t x) { x= (x & m1 ) + ((x >> 1) & m1 ); //put count of each 2 bits into those 2 bits x= (x & m2 ) + ((x >> 2) & m2 ); //put count of each 4 bits into those 4 bits x= (x & m4 ) + ((x >> 4) & m4 ); //put count of each 8 bits into those 8 bits x= (x & m8 ) + ((x >> 8) & m8 ); //put count of each 16 bits into those 16 bits x= (x & m16) + ((x >> 16) & m16); //put count of each 32 bits into those 32 bits x= (x & m32) + ((x >> 32) & m32); //put count of each 64 bits into those 64 bits return x; }

//Este ejemplo usa menos operaciones aritméticas que cualquier otra aplicación //conocida en máquinas con multiplicación lenta. //El algoritmo utiliza 17 operaciones aritméticas. int popcount64b(uint64_t x) { x -= (x >> 1) & m1; //put count of each 2 bits into those 2 bits x= (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits x= (x + (x >> 4)) & m4; //put count of each 8 bits into those 8 bits x += x >> 8; //put count of each 16 bits into their lowest 8 bits x += x >> 16; //put count of each 32 bits into their lowest 8 bits x += x >> 32; //put count of each 64 bits into their lowest 8 bits return x & 0x7f; }

//Este ejemplo usa menos operaciones aritméticas que cualquier otra aplicación //conocida en máquinas con multiplicación rápida. //El algoritmo utiliza 12 operaciones aritméticas, una de las cuales es una multiplicación. int popcount64c(uint64_t x) { x -= (x >> 1) & m1; //put count of each 2 bits into those 2 bits x= (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits x= (x + (x >> 4)) & m4; //put count of each 8 bits into those 8 bits return (x * h01) >> 56; //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... }

Las aplicaciones anteriores tienen el mejor comportamiento en el peor de los casos de cualquier algoritmo conocido. Sin embargo, cuando se espera que un valor tenga pocos bits distintos de cero, puede ser más eficiente utilizar algoritmos que cuenten estos bits de uno en uno. Como Wegner describió en 1960, el operador a nivel de bits de x con x - 1 difiere de x solo en poner a cero el bit distinto de cero menos significativo: restar 1 cambia el bit más a la derecha de la cadena de 0s a 1s, y cambia el 1 más a la derecha a un 0. Si x originalmente tenía n bits que eran 1, entonces después de solo n iteraciones de esta operación, x se reducirá a cero. El siguiente ejemplo se basa en este principio.

//Esta aplicación es mejor cuando la mayoría de los bits en x son 0 //El algoritmo funciona igual para todos los tamaños de datos. //Usa 3 operaciones aritméticas y 1 comparación/rama por "1" bit en x. int popcount64d(uint64_t x) { int count; for (count=0; x; count++) x &= x - 1; return count; }

Si se permite un mayor uso de memoria, se puede calcular el peso de Hamming más rápidamente que con los métodos anteriores. Con memoria ilimitada, se podría simplemente crear una gran tabla de búsqueda del peso de Hamming de cada entero de 64 bits. Si se puede almacenar una tabla de búsqueda de la función de Hamming de cada entero de 16 bits, se puede hacer lo siguiente para calcular el peso de Hamming de cada entero de 32 bits. static uint8_t wordbits[65536]= {/* bitcounts of integers 0 through 65535, inclusive */ }; //Este algoritmo utiliza 3 operaciones aritméticas y 2 lecturas de memoria. int popcount32e(uint32_t x) { return wordbits[x & 0xFFFF] + wordbits[x >> 16]; }

//Opcionalmente, la tabla wordbits[] podría rellenarse usando esta función int popcount32e_init(void) { uint32_t i; uint16_t x; int count; for (i=0; i <= 0xFFFF; i++)

x= i; for (count=0; x; count++) // borrowed from popcount64d() above x &= x - 1; wordbits[i]= count;

Muła et al. demostraron que una versión vectorizada de popcount64b puede ejecutarse más rápido que las instrucciones dedicadas (por ejemplo, popcnt en los procesadores x64).

Peso mínimo En código de corrección de errores, el peso de Hamming mínimo, comúnmente denominado peso mínimo wmin de un código es el peso de la palabra de código distinta de cero de menor peso. El peso w de una palabra de código es el número de unos en la palabra. Por ejemplo, la palabra 11001010 tiene un peso de 4.

En un códigos de bloque el peso mínimo es también la distancia de Hamming (dmin) y define la capacidad de corrección de errores del código. Si wmin = n, entonces y el código corregirá hasta errores.Stern & Mahmoud, Communications System Design, Prentice Hall, 2004, p 477ff.

Lenguajes de programación que disponen de conteo de unos Algunos compiladores de C proporcionan funciones intrínsecas que brindan funciones de conteo de bits. Por ejemplo, GCC (desde la versión 3.4 en abril de 2004) incluye una función integrada __builtin_popcount que utilizará una instrucción de procesador si está disponible o una aplicación de biblioteca eficiente en caso contrario. LLVM-GCC ya incluía esta función desde la versión 1.5 en junio de 2005.

En la Standard Template Library, la estructura de datos de matriz de bits bitset tiene un método count() que cuenta el número de bits que se establecen. En C++20 se agregó un nuevo encabezado <bit> que contiene las funciones std::popcount y std::has_single_bit, tomando argumentos de tipos enteros sin signo.

En Java, la estructura de datos de matriz de bits ampliable tiene un método que cuenta el número de bits que se establecen. Además, existen funciones y para contar bits en enteros primitivos de 32 y 64 bits, respectivamente. Además, la clase de enteros de precisión arbitraria también tiene un método que cuenta bits.

En Python, el tipo int tiene un método bit_count() para contar el número de bits establecidos. Esta funcionalidad se introdujo en Python 3.10, lanzado en octubre de 2021.

En Common Lisp, la función logcount, dado un número entero no negativo, devuelve el número de bits que son 1 (para enteros negativos, devuelve el número de bits que son 0 en notación de complemento a 2). En cualquier caso, el entero puede ser BIGNUM.

A partir de GHC 7.4, el paquete base Haskell tiene una función popCount disponible en todos los tipos que son instancias de la clase Bits (disponible en el módulo Data.Bits).

La versión MySQL del lenguaje SQL proporciona BIT_COUNT() como una función estándar.

Fortran dispone de la función elemental estándar e intrínseca popcnt, que devuelve el número de bits distintos de cero dentro de un entero (o matriz de enteros).