俩种常见的校验码（奇偶校验码 and 海明码）

清疚 2022-05-28 11:28 568阅读 0赞

原件故障，噪声干扰等各种因素常常导致计算机在处理信息的过程中出现错误。为了防止这种错误，可将信号采用专门的逻辑电路进行编码以检查错误。

1：奇偶校验码

奇偶校验码是 \[1\]  一种增加二进制传输系统最小距离的简单和广泛采用的方法。是一种通过增加[冗余位][Link 1]使得码字中"1"的个数恒为奇数或偶数的编码方法，它是一种检错码。在实际使用时又可分为垂直奇偶校验、水平奇偶校验和水平垂直奇偶校验等几种。

最简单且应用广泛的检验码就是采用一位校验位的奇校验或者偶校验。在实际中出现一位错误的几率是最高的。

一个二进制码字，如果它的码元有奇数个1，就称为具有奇性。例如，码字“10110101”有五个1，因此，这个码字具有奇性。同样，偶性码字具有偶数个1。注意奇性检测等效于所有码元的模二加，并能够由所有码元的异或运算来确定。对于一个n位字，奇性由下式给出：奇性=a0⊕a1⊕a2⊕…⊕an

我们只需要记住奇校验码要保证码字必须是奇性的，如果原码字就是奇性的，那么奇校验码就是0，反之为1

偶校验码相反，保证码字非奇性，有偶数个1，如果原码字就是奇性的，那么奇校验码就是1，反之为0

举个例子:

数据:                                                      偶校验编码                                             奇校验编码

1 0 1 0 1 0 1 0                                   1 0 1 0 1 0 1 0  0                                  1 0 1 0 1 0 1 0 1

接受数据的那端只需要判断一下就好了，如果奇校验中出现了偶数个1，那么出错了，偶校验类比。

但是奇偶校验只能提供是否出现一个错误，2个错误就不行了，还有出错的地方也不可能知道的，弊端比较明显。

2：海明码（汉明码也是它）

汉明码（Hamming Code），是在电信领域的一种线性调试码，以发明者理查德·卫斯里·汉明的名字命名。汉明码在传输的消息流中插入验证码，当计算机存储或移动数据时，可能会产生数据位错误，以侦测并更正单一比特错误。由于汉明编码简单，它们被广泛应用于内存（RAM）。

在此介绍海明码之前，先做俩道二年级智力题目。

问题一：我们有四个罐子，里面分别装有一些药品，正版药品重1g，盗版重0.9g，四罐中有一罐是盗版，我们有一台天秤，问怎样称一次能辨别那个罐子是盗版。

想一下。

告诉你答案吧！我们取第一罐一颗药，取第二罐俩颗药，取第三罐三颗药，取第四罐四颗药。然后称一下重量。

都是正品则重10g。如果差0.1g，那么第一罐假的，如果差0.2g，那么第二罐假的，如果差0.3g，那么第三罐假的，如果差0.4g，那么第四罐假的。问题解决了。

问题二：我们有四个罐子，里面分别装有一些药品，正版药品重1g，盗版重0.9g，不知道有几罐是假的，我们有一台天秤，问怎样称一次能辨别那些罐子是盗版。

想一下。

有了刚刚的提示，可能有人会说，依然那样弄不行吗？很明显不行，如果差0.3g，那么是第一罐和第二罐有问题还是第三罐有问题。敏锐的你应该注意到了，关键在取药品的数量上。

我们取第一罐一颗药(0001)，取第二罐俩颗药(0010)，取第三罐四颗药(0100)，取第四罐八颗药(1000)。然后称一下重量。

重量差值(g)                                 盗版药品

0.1(0001)                                    第一罐

0.2(0010)                                    第二罐

0.3(0011)                                    第一罐与第二罐

0.4(0100)                                    第三罐

0.5(0101)                                   第三罐与第一罐

。。。。                                    。。。。

1.5(1111)                                   第一罐 第二罐  第三罐 第四罐

正好巧妙的利用二进制的特点，表示出了所有差值情况和对应的盗版药品（最关键一点：没有出现“一对多”）

下面来正式介绍海明码

对于一个长度为x位的数据，我们至少需要多少位的数据来保存它每一位可能会出错的信息了？

我们知道一个长度为n位的字可以保存2^n的信息，

则2^n>=x吗？不是的呀，它自己也需要保存咯，那么2^n>=x+n吗？不是的呀，那么如果2^n==x+n怎么办，那不也就是每一种情况都是错的，正确的情况怎么办了？则：

2^n>=x+n+1

我们以保存8位数据为例，代入得n=4,共构成12位数据(r表示海明码，x表示数据)，排列如下:

r1 r2 x3 r4 x5 x6 x7 r8 x9 x10 x11 x12

我们来表示一下:

3= 1+2                  5= 1 + 4                  6= 2 + 4                  7= 1 + 2 + 4                  9=1 + 8                                             10=2 + 8                11=1 + 2 + 8                  12=4 + 8

含有海明码的数据元素：

r1: x3  x5  x7  x9  x11

r2: x3  x6  x7  x10  x11

r4: x5  x6  x7  x12

r8: x9  x10  x11  x12

r1 r2 r4 r8 存储什么了？这个得与奇偶校验码相结合。

以奇校验为例:

r1 r2 x3 r4 x5 x6 x7 r8 x9 x10 x11 x12

1       0   1  0       1    0    1     1（随便写的数据）

那么r1就是x3  x5  x7  x9  x11（1,0,0,1,1)的奇校验码  r1=0

那么r2就是x3  x6  x7  x10  x11(1,1,0,0,1)的奇校验码 r2=0

那么r4就是x5  x6  x7  x12 (0,1,0,1)的奇校验码 r4=1