El peso de Hamming de una cadena 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 desde 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 1 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 este caso binario, también se denomina recuento de población , [1] popcount , suma lateral , [2] osuma de bits . [3]
El peso de Hamming lleva el nombre de Richard Hamming , aunque él no originó la noción. [7] El peso de Hamming de números binarios ya fue utilizado en 1899 por James WL Glaisher para dar una fórmula para el número de coeficientes binomiales impares en una sola fila del triángulo de Pascal . [8] Irving S. Reed introdujo un concepto, equivalente al peso de Hamming en el caso binario, en 1954. [9]
El peso de Hamming se utiliza en varias disciplinas, incluida la teoría de la información, la teoría de la codificación y la criptografía . Ejemplos de aplicaciones del peso de Hamming incluyen:
El conteo de población de una cadena de bits 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 A xor B . [1]
El problema de cómo implementarlo de manera eficiente ha sido ampliamente estudiado. En algunos procesadores se dispone de una sola operación para el cálculo, u operaciones paralelas sobre vectores de bits . 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:
Aquí, las operaciones son como en el lenguaje de programación C , por lo X >> Yque 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 arriba y se dan aquí: [1]