Diferencia entre revisiones de «Peso de Hamming»

De Wikipedia, la enciclopedia libre
Ir a siguiente diferencia →
Contenido eliminado Contenido añadido
VisualWikitexto
Creación de «Peso de Hamming»
Etiqueta: Enlaces a desambiguaciones
(Sin diferencias)

Revisión del 19:41 6 oct 2022

Uno o varios wikipedistas están trabajando actualmente en este artículo o sección. Es posible que a causa de ello haya lagunas de contenido o deficiencias de formato.
Si quieres, puedes ayudar y editar, pero antes de realizar correcciones mayores contáctalos en sus páginas de discusión o en la del artículo para poder coordinar la redacción.
Uso de esta plantilla: {{En desarrollo|nombre de usuario|t={{sust:CURRENTTIMESTAMP}}}} o {{sust:En desarrollo}}

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,[1]​ suma lateral,[2]​ o suma de bits.[3]​

Ejemplos
Cadena de caracteres Peso de Hamming
11101 4
11101000 4
00000000 0
678012340567 10
Plantilla:Graph:Chart
A plot for the population count (Hamming weight for binary numbers) for (decimal) numbers 0 to 256.[4]​[5]​[6]​

Historia y uso

El peso de Hamming lleva el nombre de Richard Hamming aunque él no originó la noción.[7]​ 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 the number of odd binomial coefficients en una sola fila de Triángulo de Pascal.[8]​ Irving Stoy Reed introdujo un concepto, equivalente al peso de Hamming en el caso binario, en 1954.[9]​

El peso Hamming se usa en varias disciplinas, incluidas teoría de la información, teoría de códigos y criptografía. Ejemplos de aplicaciones del peso de Hamming incluyen:

  • En exponenciación binaria modular, el número de multiplicaciones modulares necesarias para un exponente e es log2 e + peso(e). 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 Hamming.[10]​
  • El peso de Hamming determina las longitudes de ruta entre nodos en Chord distributed hash tables.[11]​
  • Las búsquedas de Reconocimiento de iris en las bases de datos biométricas se implementan normalmente calculando el Distancia de Hamming de cada registro almacenado.
  • En los programas 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 calcular find first set de manera eficiente usando la identidad ffs(x) = pop(x ^ (x - 1)). 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.[12]​[1]​
  • La operación de peso de Hamming se puede interpretar como una conversión de sistema de numeración unario a sistema binario.[13]​
  • En implementación de algunos succinct data structure como bit vectors y wavelet trees.

Implementación eficiente

El conteo de población de un bitstring a menudo se necesita en criptografía y otras aplicaciones. El Distancia de Hamming de dos palabras A y B se puede calcular como el peso Hamming de A disyunción exclusiva B.[1]​

El problema de cómo implementarlo de manera eficiente ha sido ampliamente estudiado. Una sola operación para el cálculo, u operaciones paralelas sobre vectores de bits son available on some processors. 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:

Expression Binary Decimal Comment
a 01 10 11 00 10 11 10 10 The original number
b0= (a >> 0) & 01 01 01 01 01 01 01 01 01 00 01 00 00 01 00 00 1, 0, 1, 0, 0, 1, 0, 0 Every other bit from a
b1= (a >> 1) & 01 01 01 01 01 01 01 01 00 01 01 00 01 01 01 01 0, 1, 1, 0, 1, 1, 1, 1 The remaining bits from a
c= b0 + b1 01 01 10 00 01 10 01 01 1, 1, 2, 0, 1, 2, 1, 1 Count of 1s in each 2-bit slice of a
d0= (c >> 0) & 0011 0011 0011 0011 0001 0000 0010 0001 1, 0, 2, 1 Every other count from c
d2= (c >> 2) & 0011 0011 0011 0011 0001 0010 0001 0001 1, 2, 1, 1 The remaining counts from c
e= d0 + d2 0010 0010 0011 0010 2, 2, 3, 2 Count of 1s in each 4-bit slice of a
f0= (e >> 0) & 00001111 00001111 00000010 00000010 2, 2 Every other count from e
f4= (e >> 4) & 00001111 00001111 00000010 00000011 2, 3 The remaining counts from e
g= f0 + f4 00000100 00000101 4, 5 Count of 1s in each 8-bit slice of a
h0= (g >> 0) & 0000000011111111 0000000000000101 5 Every other count from g
h8= (g >> 8) & 0000000011111111 0000000000000100 4 The remaining counts from g
i= h0 + h8 0000000000001001 9 Count of 1s in entire 16-bit word

Aquí, las operaciones son como en C programming language, por lo que X >> Y 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í:[1]​ 

//types and constants used in the functions below
//uint64_t is an unsigned 64-bit integer variable type (defined in C99 version of C language)
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...

//This is a naive implementation, shown for comparison,
//and to help in understanding the better functions.
//This algorithm uses 24 arithmetic operations (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;
}

//This uses fewer arithmetic operations than any other known  
//implementation on machines with slow multiplication.
//This algorithm uses 17 arithmetic operations.
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;
}

//This uses fewer arithmetic operations than any other known  
//implementation on machines with fast multiplication.
//This algorithm uses 12 arithmetic operations, one of which is a multiply.
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 implementaciones 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,[14]​ 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 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. La siguiente implementación se basa en este principio. 

//This is better when most bits in x are 0
//This algorithm works the same for all data sizes.
//This algorithm uses 3 arithmetic operations and 1 comparison/branch per "1" bit in 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, podemos calcular el peso de Hamming más rápido que los métodos anteriores. Con memoria ilimitada, podríamos simplemente crear una gran tabla de búsqueda del peso de Hamming de cada entero de 64 bits. Si podemos almacenar una tabla de búsqueda de la función Hamming de cada entero de 16 bits, podemos 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 */ };
//This algorithm uses 3 arithmetic operations and 2 memory reads.
int popcount32e(uint32_t x)
{
    return wordbits[x & 0xFFFF] + wordbits[x >> 16];
}

//Optionally, the wordbits[] table could be filled using this function
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.[15]​ han demostrado que una versión vectorizada de popcount64b puede ejecutarse más rápido que las instrucciones dedicadas (por ejemplo, popcnt en procesadores x64).

Peso mínimo

En error-correcting coding, el peso Hamming mínimo, comúnmente denominado peso mínimowmin 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 1 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 el distancia de Hamming (dmin) y define la capacidad de corrección de errores del código. Si wmin = n, entonces dmin = n y el código corregirá hasta errores dmin/2.[16]​

Soporte de idioma

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 implementación de biblioteca eficiente en caso contrario.[17]​ LLVM-GCC ha incluido esta función desde la versión 1.5 en junio de 2005.[18]​

En 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, un nuevo encabezado <bit> se agregó, 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 BitSet tiene un método BitSet.cardinality() que cuenta el número de bits que se establecen. Además, existen funciones Integer.bitCount(int) y Long.bitCount(long) para contar bits en enteros primitivos de 32 y 64 bits, respectivamente. Además, la clase de enteros de precisión arbitraria BigInteger también tiene un método BigInteger.bitCount() 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.[19]​

En Common Lisp, la función logcount, dado un número entero no negativo, devuelve el número de 1 bits. (Para enteros negativos, devuelve el número de 0 bits 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).[20]​

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

Fortran tiene 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).[22]​

Algunas calculadoras de bolsillo científicas programables cuentan con comandos especiales para calcular el número de bits establecidos, p. #B en HP-16C[3]​[23]​ y WP 43S,[24]​[25]​ #BITS[26]​[27]​ o BITSUM[28]​[29]​ en emuladores HP-16C y nBITS en WP 34S.[30]​[31]​

Free Pascal implementa popcnt desde la versión 3.0.[32]​

Soporte de procesador

Véase también

Referencias

  1. ↑ a b c d e f g Warren Jr., Henry S. (2013). Hacker's Delight (2 edición). Addison-Wesley - Pearson Education, Inc. pp. 81-96. ISBN 978-0-321-84268-8. 0-321-84268-5.  Parámetro desconocido |orig-year= ignorado (ayuda); Parámetro desconocido |title-link= ignorado (ayuda)
  2. ↑ Knuth, Donald Ervin (2009). «Bitwise tricks & techniques; Binary Decision Diagrams». The Art of Computer Programming. 4, Fascicle 1. Addison-Wesley. ISBN 978-0-321-58050-4.  Parámetro desconocido |title-link= ignorado (ayuda) (NB. Borrador de Fascículo 1b disponible para descargar.)
  3. ↑ a b Hewlett-Packard HP-16C Computer Scientist Owner's Handbook. Hewlett-Packard. April 1982. 00016-90001. Archivado desde el original el 28 de marzo de 2017. Consultado el 28 de marzo de 2017. 
  4. ↑ [1], written in Fōrmulæ. The Fōrmulæ wiki. Retrieved 2019-09-30.
  5. ↑ A solution to the task Population count. Retrieved 2019-09-30.
  6. ↑ Rosetta Code. Retrieved 2019-09-30.
  7. ↑ Thompson, Thomas M. (1983). From Error-Correcting Codes through Sphere Packings to Simple Groups. The Carus Mathematical Monographs #21. Mathematical Association of America. p. 33. 
  8. ↑ Glaisher, James Whitbread Lee (1899). «On the residue of a binomial-theorem coefficient with respect to a prime modulus». The Quarterly Journal of Pure and Applied Mathematics 30: 150-156.  (Nota: véase en particular el último párrafo de la pág. 156.)
  9. ↑ Reed, Irving Stoy (1954). «A Class of Multiple-Error-Correcting Codes and the Decoding Scheme». Institute of Electrical and Electronics Engineers (Institute of Radio Engineers (IRE)). PGIT-4: 38-49. 
  10. ↑ Cohen, Gérard D.; Lobstein, Antoine; Naccache, David; Zémor, Gilles (1998). «How to improve an exponentiation black-box». En Nyberg, Kaisa, ed. Advances in Cryptology – EUROCRYPT '98, International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, May 31 – June 4, 1998, Proceeding. Lecture Notes in Computer Science 1403. Springer. pp. 211-220. doi:10.1007/BFb0054128. 
  11. ↑ Stoica, I.; Morris, R.; Liben-Nowell, D.; Karger, D. R.; Kaashoek, M. F.; Dabek, F.; Balakrishnan, H. (February 2003). «Chord: a scalable peer-to-peer lookup protocol for internet applications». IEEE/ACM Transactions on Networking 11 (1): 17-32. S2CID 221276912. doi:10.1109/TNET.2002.808407. «Section 6.3: "In general, the number of fingers we need to follow will be the number of ones in the binary representation of the distance from node to query."». 
  12. ↑ a b SPARC International, Inc. (1992). «A.41: Population Count. Programming Note». The SPARC architecture manual: version 8 (Version 8 edición). Englewood Cliffs, New Jersey, USA: Prentice Hall. pp. 231. ISBN 0-13-825001-4.  Parámetro desconocido |chapter-url-access= ignorado (ayuda)
  13. ↑ Blaxell, David (1978). «Record linkage by bit pattern matching». En Hogben, David; Fife, Dennis W., eds. Computer Science and Statistics--Tenth Annual Symposium on the Interface. NBS Special Publication (Departamento de Comercio de los Estados Unidos / Instituto Nacional de Estándares y Tecnología) 503: 146-156. 
  14. ↑ Wegner, Peter (May 1960). «A technique for counting ones in a binary computer». Communications of the ACM 3 (5): 322. S2CID 31683715. doi:10.1145/367236.367286. 
  15. ↑ Muła, Wojciech; Kurz, Nathan; Lemire, Daniel (January 2018). «Faster Population Counts Using AVX2 Instructions». Computer Journal 61 (1): 111-120. S2CID 540973. arXiv:1611.07612. doi:10.1093/comjnl/bxx046. 
  16. ↑ Stern & Mahmoud, Communications System Design, Prentice Hall, 2004, p 477ff.
  17. ↑ «GCC 3.4 Release Notes». GNU Project. 
  18. ↑ «LLVM 1.5 Release Notes». LLVM Project. 
  19. ↑ «What's New In Python 3.10». python.org. 
  20. ↑ «GHC 7.4.1 release notes».  Documentación de GHC.
  21. ↑ «Chapter 12.11. Bit Functions — MySQL 5.0 Reference Manual». 
  22. ↑ Metcalf, Michael; Reid, John; Cohen, Malcolm (2011). Modern Fortran Explained. Oxford University Press. p. 380. ISBN 978-0-19-960142-4. 
  23. ↑ Schwartz, Jake; Grevelle, Rick (20 de octubre de 2003). HP16C Emulator Library for the HP48S/SX. 1.20 (1 edición). Consultado el 15 de agosto de 2015.  Parámetro desconocido |orig-year= ignorado (ayuda) (Nota: esta biblioteca también funciona en HP48 (066)/GX/G+. Más allá del conjunto de funciones de HP-16C, este paquete también admite cálculos para coma flotante binarios, octales y hexadecimales en notación científica, además de los números decimales de coma flotante habituales.)
  24. ↑ Bonin, Walter (2019). WP 43S Owner's Manual. 0.12 (draft edición). p. 135. ISBN 978-1-72950098-9. Consultado el 5 de agosto de 2019.  Parámetro desconocido |orig-year= ignorado (ayuda) [2] [3] (314 páginas)
  25. ↑ Bonin, Walter (2019). WP 43S Reference Manual. 0.12 (draft edición). pp. xiii, 104, 115, 120, 188. ISBN 978-1-72950106-1. Consultado el 5 de agosto de 2019.  Parámetro desconocido |orig-year= ignorado (ayuda) [4] [5] (271 páginas)
  26. ↑ Martin, Ángel M.; McClure, Greg J. (5 de septiembre de 2015). «HP16C Emulator Module for the HP-41CX - User's Manual and QRG». Archivado desde el original el 27 de abril de 2017. Consultado el 27 de abril de 2017.  (Nota: más allá del conjunto de funciones HP-16C, esta biblioteca personalizada para HP-41 amplía la funcionalidad de la calculadora en unas 50 funciones adicionales.)
  27. ↑ (076)Martin, Ángel M. (7 de septiembre de 2015). «HP-41: New HP-16C Emulator available». Archivado desde el original el 27 de abril de 2017. Consultado el 27 de abril de 2017. 
  28. ↑ Thörngren, Håkan (10 de enero de 2017). «Ladybug Documentation» (release 0A edición). Consultado el 29 de enero de 2017.  [6]
  29. ↑ «New HP-41 module available: Ladybug». 10 de enero de 2017. Archivado desde el original el 29 de enero de 2017. Consultado el 29 de enero de 2017. 
  30. ↑ Dale, Paul; Bonin, Walter (2012). «WP 34S Owner's Manual» (3.1 edición). Consultado el 27 de abril de 2017.  Parámetro desconocido |orig-year= ignorado (ayuda))
  31. ↑ Bonin, Walter (2015). WP 34S Owner's Manual (3.3 edición). ISBN 978-1-5078-9107-0.  Parámetro desconocido |orig-year= ignorado (ayuda)
  32. ↑ «Free Pascal documentation popcnt». Consultado el 7 de diciembre de 2019. 
  33. ↑ «JDK-6378821: bitCount() should use POPC on SPARC processors and AMD+10h». Java bug database. 30 de enero de 2006. 
  34. ↑ Blackfin Instruction Set Reference (Preliminary edición). Analog Devices. 2001. pp. 8-24. Part Number 82-000410-14. 
  35. ↑ Wolf, Claire (22 de marzo de 2019). «RISC-V "B" Bit Manipulation Extension for RISC-V, Draft v0.37». Github. 

Lectura adicional

Enlaces externos

Obtenido de «https://es.wikipedia.org/w/index.php?title=Peso_de_Hamming&oldid=146420821»