汉明距离和汉明重量
汉明距离是以理查德·卫斯里·汉明的名字命名的。在信息论中,两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说,它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。
例如:
1011101 与 1001001 之间的汉明距离是 2。
2143896 与 2233796 之间的汉明距离是 3。
"toned" 与 "roses" 之间的汉明距离是 3。
汉明重量是字符串相对于同样长度的零字符串的汉明距离,也就是说,它是字符串中非零的元素个数:对于二进制字符串来说,就是 1 的个数,所以 11101 的汉明重量是 4。
如果把a和b两个单词看作是向量空间中的元素,则它们之间的汉明距离等于它们汉明重量的差a-b。如果是二进制字符串a和b,汉明距离等于它们汉明重量的和a+b或者a和b汉明重量的异或a XOR b。汉明距离也等于一个n维的超立方体上两个顶点间的曼哈顿距离,n指的是单词的长度。
20140615142552343.png 20140615032538812.png
例如S(0110)到D(1101)的汉明距离为3,可以数一下这个超立方体,曼哈顿距离同样为3.
XOR(异或)的计算公式:
a | b | a⊕b |
---|---|---|
1 | 0 | 1 |
1 | 1 | 0 |
0 | 0 | 0 |
0 | 1 | 1 |
只有在两个比较的位不同时其结果是1,否则结果为0
即“两个输入相同时为0,不同则为1”!
超立方体路由计算公式:http://www.dongcoder.com/detail-547250.html或者https://blog.csdn.net/pandora_madara/article/details/30901299
网友评论