简介

奖项

汉明距离

汉明重量(高效实现)

简介

理查德·卫斯里·汉明（英语：Richard Wesley Hamming，1915年2月11日－1998年1月7日），美国数学家，主要贡献在计算机科学和电讯。

1937年芝加哥大学学士学位毕业，1939年内布拉斯加大学硕士学位毕业，1942年伊利诺伊大学香槟分校博士学位毕业，博士论文为《一些线性微分方程边界值理论上的问题》（Some Problems in the Boundary Value Theory of Linear Differential Equations）。二战期间在路易斯维尔大学当教授，1945年参加曼克顿计划，负责编写电脑程式，计算物理学家所提供方程的解。该程式是判断引爆核弹会否燃烧大气层，结果是不会，于是核弹便开始试验。

1946至76年在贝尔实验室工作。他曾和约翰·怀尔德·杜奇、克劳德·艾尔伍德·香农合作。1956年他参与了IBM 650的编程语言发展工作。

1976年7月23日起在海军研究院当兼任教授，1997年成为名誉教授。

他是美国电脑协会（ACM）的创立人之一，曾任该组织的主席。

奖项

1968年ACM图灵奖1968年IEEE院士1979年Emanuel R. Piore奖1980年美国国家工程学院院士1981年宾夕法尼亚大学Harold Pender奖1988年IEEE理查·卫斯里·汉明奖

汉明距离

在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。 例如：

1011101与 1001001之间的汉明距离是 2。2143896与 2233796之间的汉明距离是 3。"toned" 与 "roses" 之间的汉明距离是 3。 汉明重量是字符串相对于同样长度的零字符串的汉明距离，也就是说，它是字符串中非零的元素个数：对于二进制字符串来说，就是 1 的个数，所以 11101 的汉明重量是 4。

汉明重量

汉明重量是一串符号中非零符号的个数。因此它等同于同样长度的全零符号串的汉明距离。在最为常见的数据位符号串中，它是 1 的个数。

高效实现

在密码学以及其它应用中经常需要计算数据位中 1 的个数，针对如何高效地实现人们已经广泛地进行了研究。一些处理器使用单个的命令进行计算，另外一些根据数据位向量使用并行运算进行处理。对于没有这些特性的处理器来说，已知的最好解决办法是按照树状进行相加。例如，要计算二进制数 A=0110110010111010 中 1 的个数，这些运算可以表示为：

符号　二进制　十进制　注释

A　0110110010111010　　原始数据

B = A & 01 01 01 01 01 01 01 01　01 00 01 00 00 01 00 00　1,0,1,0,0,1,0,0　A 隔一位检验

C = (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　A 中剩余的数据位

D = B + C　01 01 10 00 01 10 01 01　1,1,2,0,1,2,1,1　A 中每个双位段中 1 的个数列表

E = D & 0011 0011 0011 0011　0001 0000 0010 0001　1,0,2,1　D 中数据隔一位检验

F = (D >> 2) & 0011 0011 0011 0011　0001 0010 0001 0001　1,2,1,1　D 中剩余数据的计算

G = E + F　0010 0010 0011 0010　2,2,3,2　A 中 4 位数据段中 1 的个数列表

H = G & 00001111 00001111　00000010 00000010　2,2　G 中数据隔一位检验

I = (G >> 4) & 00001111 00001111　00000010 00000011　2,3　G 中剩余数据的计算

J = H + I　00000100 00000101　4,5　A 中 8 位数据段中 1 的个数列表

K = J & 0000000011111111　0000000000000101　5　J 中隔一位检验

L = (J >> 8) & 0000000011111111　0000000000000100　4　J 中剩余数据的检验

M = K + L　0000000000001001　9　最终答案