图片来源：南京大学软件学院COA课程PPT

©author:zzb

4 数据校验码

差错error

以存储为例：

• 硬故障：永久性物理故障

• 软故障：随机非破坏性事件，改变了某些内容，但没有损坏机器

纠错error correction

注意，C’'不是和C去比较，因为既然D有可能出现差错变成D’，那么与之相应的校验码C也可能差错，因此，取出来的不是C，而是C‘，是将用D’生成的C‘’去和取出来的C‘比较

一旦D存进存储器/网络，那么原来的D就消失了，取出来的就是D’。（如果能保证存进去和取出来的是一样的，那么也就不存在纠错，事实上，这是无法保证的）

奇偶校验码

奇校验码：如果有奇数个1，那么C=0，否则为1

偶校验码：如果有偶数个1，那么C=0，否则为1

（理解：把原来的数据和这个校验码拼在一起时应当还是和校验码名字中的奇偶一致，所以奇校验码当1为奇数，C=0，那么拼在一起还是奇数个）

当数据D中出错的位数为偶数时，那么1的个数的奇偶性仍然是不变的，因此校验码不变

因此奇偶校验码适用于较短的数据进行检错，这样出现多位错的概率相对较小，检错的效果较好（当然还是会有可能出现多位错误，但概率很小）

代价很低，只需要1位即可

发现错误比发现后纠正更难，因为如果发现了，那么纠正也就是把0变成1，1变成0就好了，相对找到错误更为简单

##　海明码

分组的时候要求任何两位所属的组的情况都是不一样的，同时一位数据可能会属于若干个小组（至少两个组，与下面的故障字规则一致，否则如果只一个组的话，会和校验码出错冲突）

前提假设：最多一位发生错误

奇偶校验码是海明码的基础

利用的原理就是校验码出错的几个所在小组中公共的那一位就是出错的位，这样就能够定位到错误

因为K位校验码可以表示2^K种情形，而出错的情形为M+K+1，因此可以求出K的最小值

由表格可见，随着数据位的增加，最小校验码的位数增加较少，所占比例较小

但是不能通过把M的位数设成很大，来使得校验码的的位数相对少，因为如果数据位数很大，则只发生一位错误的假设就不成立了

因此要实现一个平衡：海明码有效且所占比例较少

先把故障字分配给每一位数据位故障，然后再进行分组，把这一个Dn放到故障字中数值为1的那一位所对应的组中，如上，D8对应故障字1100，那么D8应当分到C1和C2组中去

故障字从0001开始分配，因为0000已经用于表示没有发生故障

这里C的计算用的是偶校验（当然奇校验也行）

注意：存储时是按上面表格的顺序来存储的，而不是D8D7……D1C4……C1（上图蓝色的表示校验码，黑色表示数据）

将计算出的C‘’与C‘异或，那么就可以得到故障字，从而定位到出错的是哪一位

主存的实际容量比用户可以使用的容量要大，因为对于存储的数据，也是可能会发生错误的，因此需要去添加纠错码，如磁盘中就有纠错区，之后的区域才是数据区等

加强版的海明码

---

循环冗余校验

• 当余数位数与除数位数相同时，才进行异或运算（模二除法），即与除数对齐的第一位为1时才异或并上商为1，否则不进行异或直把除数右移并上商为0了，直到被除数最后一位

如果这两个 CRC结果不一致，则说明发送中出现了差错，接收方计算机可要求发送方计算机重新发送该数据

CRC 算法检验的检错能力极强，且检测成本较低

因而，CRC 成为计算机信息通信领域最为普遍的校验方式

---