概念

数据在计算机内部进行计算、存取和传送过程中，由于元器件故障或噪音干扰等原因会出现差错。

冗余校验思想：除原数据信息外，还增加若干位编码，这些新增的代码称为校验位。

两个合法代码对应位上编码不同的位数称为码距，又称海明距离。

任意两个码字的海明距离的最小值称为该编码集的海明距离。

检查纠错位数 码距
检e位 d>=e+1
纠e位 d>=2e+1
纠e1位、检e2位 d>=2*e1+e2+1

奇偶校验码

通过增加冗余位使得码字中1的个数恒为奇数或偶数的编码方法，是一种检错码。

码距=2

海明校验码

将有效信息按某种规律分成若干组，每组安排一个校验位，做奇偶测试，就能提供多位检错信息，以指出最大可能是哪位出错，从而将其纠正。实质上，海明校验是一种多重校验。

规则：

  1. 如果故障字各位都是0，无故障。
  2. 如果故障字有且仅有一位1，校验位有一位错了，不用纠正。
  3. 如果故障字有多位1，数据位出错，由故障字数值确定出错位，然后取反就可以纠错。

下图为校验位数的确定

下图为分组方式（n=8、k=4）

由表可知，每个数据位至少要参与两组奇偶校验码的生成。如M5与第一组（P1）和第四组（P4）有关。

循环冗余校验码（CRC码）

M(x)为n位二进制数据，将M(x)左移k位，用约定的生成多项式G(x)相除（G(x)是一个k+1位的二进制数），相除得到的k位余数就是校验位。

检验：如果接收到的数据和校验码位用同样的生成多项式G(x)相除，若正好除尽，没有错误；除不尽，有错误。

二进制的计算

求CRC码

CRC码检错例题

CRC码出错模式（n=11,k=4为例）余数右加0再除多项式二进制取余数