海明距离(abc和ABCD的海明距离)

二进制数据在传输、访问等过程中会出现错误(1变成0或者0变成1)，所以就存在一个如何发现和纠正错误的问题。所有这些问题的解决方案是在原始数据(数字位)中添加几个校验位。我们常用的校验码有三种:奇偶校验码、汉明校验码和循环冗余校验码(CRC)。

汉明校验码是由RichardHamming于1950年提出的，是目前广泛使用的一种非常有效的校验方法。其实现原理是在K个数据位上加R个校验位，从而形成一个k+r位的新码字，使新码字的码距变得更加均匀加宽。数据的每个二进制位被分配给偶数奇偶校验位的几种不同组合。当一个比特出错时，相关奇偶比特的值会发生变化，不仅可以找出错误，还可以指出哪个比特出错，为进一步自动纠错提供依据。然而，这种汉明校验方法只能检测和纠正一位错误。所以如果有多个错误，是查不出来的。

码距是多少？

两个代码组对应的位数中不同位数的个数称为代码组的距离，也简称为汉明距离。比如00110和00100的码距是1，12345和13344的码距是2，Caus和Daun的码距是2。

汉明校验码公式(假设为K个数据位设置了R个校验位)

公式是怎么出来的？

假设有R个校验位，一位有0或1，R位有2个R排列，可以表示2个R状态。其中一种状态用于指示它是正确的(没有发生错误)。剩余的2个r-1状态指示错误发生的位置。总共有k+r位，所以2 ^ r-1必须>:=总位置k+r。

根据不等式，可以得到k与r的对应关系。

注:汉明校验码放在2的幂上，即“1，2，4，8，16，32 …”

求实战1011的汉明码。

步骤1:找出R的值(即校验位的数量)

根据下式直接取代:

2^r-1 ≥ 4 + r

2^r-r ≥ 5

最小r为3。

所以汉明码的位数是4+3=7位。

第二步:检查奇偶校验位和信息位。

注意:信息位的位置分配是按照从高位到低位的顺序存储的。

注:汉明校验码放在2的幂上。

步骤3:确定校验位的值。

验证原理:要验证的汉明位的下标等于验证该位所涉及的所有校验位的下标之和。

然后记录由校验码校验的信息位的位置:

r1: 3，5，7

r2: 3，6，7

r3: 5，6，7

然后对相应的信息位做异或运算(异或运算规则为:0⊕0=0、1⊕0=1、0⊕1=1、1⊕1=0(均为0，不同为1))

r1: 1 xor 1 xor 1 = 1

r2: 1异或0异或1 = 0

r3: 1 xor 0 xor 1 = 0

代入表中得到

注:汉明码:1010101按照从低到高的顺序获取。