Pes de Hamming
El pes Hamming d'una cadena és el nombre de símbols que són diferents del símbol zero de l'alfabet utilitzat. Per tant, és equivalent a la distància de Hamming des de la corda totalment zero de la mateixa longitud. Per al cas més típic, una cadena de bits, aquest és el nombre d'1 a la cadena, o la suma de dígits de la representació binària d'un nombre donat i la norma ℓ₁ d'un vector de bits. En aquest cas binari, també s'anomena recompte de població, popcount, suma lateral, o suma de bits.
Història i ús
[modifica]El pes de Hamming rep el nom de Richard Hamming encara que ell no va originar la noció. El pes de Hamming dels nombres binaris ja va ser utilitzat el 1899 per James WL Glaisher per donar una fórmula per al nombre de coeficients binomials senars en una sola fila del triangle de Pascal. Irving S. Reed va introduir un concepte, equivalent al pes de Hamming en el cas binari, el 1954.
El pes de Hamming s'utilitza en diverses disciplines, com ara la teoria de la informació, la teoria de la codificació i la criptografia. Alguns exemples d'aplicacions del pes Hamming inclouen:
| Corda | Pes de Hamming |
|---|---|
| 111 0 1 | 4 |
| 111 0 1 000 | 4 |
| 00000000 | 0 |
| 678 0 1234 0 567 | 10 |
- En l'exponenciació modular per quadrat, el nombre de multiplicacions modulars necessàries per a un exponent e és log₂ e + pes(e). Aquesta és la raó per la qual el valor de clau pública e utilitzat a RSA normalment s'escull per ser un nombre de baix pes de Hamming.
- El pes de Hamming determina les longituds del camí entre nodes a les taules hash distribuïdes de Chord.
- Les cerques d'IrisCode a les bases de dades biomètriques s'implementen normalment calculant la distància de Hamming a cada registre emmagatzemat.
- En els programes d'escacs informàtics que utilitzen una representació de tauler de bits, el pes Hamming d'un tauler de bits dona el nombre de peces d'un tipus determinat que queden en el joc, o el nombre de caselles del tauler controlades per les peces d'un jugador, i per tant és un terme important que contribueix. al valor d'una posició.
- El pes de Hamming es pot utilitzar per calcular de manera eficient el primer conjunt utilitzant la identitat ffs(x) = pop(x ^ (x - 1)). Això és útil en plataformes com SPARC que tenen instruccions de pes Hamming de maquinari però que cap maquinari troba la primera instrucció establerta.
- L'operació de pes de Hamming es pot interpretar com una conversió del sistema numeral unari a nombres binaris.
- En la implementació d'algunes estructures de dades succintes com ara vectors de bits i arbres wavelets.
Implementació eficient
[modifica]El recompte de població d'una cadena de bits sovint es necessita en criptografia i altres aplicacions. La distància de Hamming de dues paraules A i B es pot calcular com el pes de Hamming de A xor B .
El problema de com implementar-lo de manera eficient ha estat àmpliament estudiat. En alguns processadors hi ha disponible una única operació per al càlcul o operacions paral·leles sobre vectors de bits. Per als processadors que no tenen aquestes funcions, les millors solucions conegudes es basen en afegir recomptes en un patró d'arbre.