计算机组成原理—校验码

2.4 校验码

为减少和避免数据传输错误，一方面从电路、电源和布线等方面采取措施，提高抗干扰能力。另一方面，在数据编码上采用一些具有特征的编码法，附加少量电路，能够发现某些错误，甚至能确定错误的性质和出错的位置，进而实现自动改错。前者称为检错，后者称为纠错。

纠错的关键：如何快速、准确地发现错误。

常用技术：校验码技术。

常用校验码有三种：奇偶校验码、海明码和循环冗余码。

奇偶校验码

奇偶校验码：是在若干有效信息位上，增加一个校验位，如果校验位的取值使得整个校验码中“1”的个数是奇数，称为奇校验码；如果校验位的取值使得整个校验码中 “1”的个数是偶数，则称为偶校验码。

形成校验位、进行校验的电路实现简单。

以8位有效信息D(7)D(6)…D(1)D(0)为例，其奇偶校验位的形成和校验电路如下图所示。其中：A输出端为1，表明偶校验码出错；B输出端为1，表明奇校验码出错。

注意：奇偶校验位本身也可能出错。

• 特点：

• 奇偶校验方法简单，电路容易实现，而且只需要一位额外的存储空间，因此应用较多。

• 单向奇偶校验只能检测出校验码中有奇数个位出错，不能发现偶数个错误，也不能确定哪位出错。

• 交叉奇偶校验：

• 大量字节的数据块传送时，经常将数据块中的多个字节排列成矩阵，进行横向和纵向同时进行校验。

• 交叉校验可以发现两位同时出错的情况。在一定程度上对单向的奇偶校验是一种弥补。例如：

  
  假设第3个字节中的D(5)和D(2)位出错，其横向校验码中仍有奇数个1，单从横向看不出错误。但是D(5)列和D(2)列的各有一个错误，从D(5)列和D(2)列的纵向奇校验码会发现该列出错。

**合法代码集合——**检0位错，纠0位错

编码的最小距离

海明校验码的组成

1. 汉明码采用奇偶校验

2. 汉明码采用分组校验

   

3. 汉明码分组采用非划分方式

   

海明校验码的组成

海明校验码的组成三要素

• 汉明码的组成需增添？位检测位
• 检测位的位置？
• 检测位的取值？

海明校验码

引言

奇偶校验无法检测出偶数个位出现错误，即使测出了错误，也不能指出哪一位出现了错误。

如果一条信息中包含多个用于纠错的位，通过妥善安排这些纠错位，使得不同位出错产生不同的错误结果，这样就可以找出出错位了。

例如，在一个7位的信息中，单个数据位出错有7种可能，用3个错误控制位可以确定是否出错及哪一位出错。

海明码就是这种思想。其本质是多重奇偶校验，可以用来自动纠正一位差错。至今仍在广泛使用。

编码基本思想

若增加校验位，也即增加了监督关系式和校正因子，就可以用来区分更多的情况。例如：有两个校正因子S(1)、S(2)，其取值有4种情况00、01、10和11，就可以表达4种不同的情况。比如，00表示无差错，01、10和11可以用来指出3种不同情况的差错，从而可以进一步区分是哪一位出错。

假设为k个数据位设置r个校验位，则r个校验位能表示2(r)个状态，用其中的一个状态表示整个k+r位的海明码“没有发生错误”，其余的2(r) -1个状态指出有错误且不同的状态值指明相应的位发生错误，包括k个数据位和r个校验位。因此校验位的位数应满足如下关系：

循环冗余校验码

循环冗余校验码CRC（Cyclic Redundancy Check）是最著名的一种检错方式。

特点：检错能力极强，开销小，易于用编码器及检测电路实现。其漏检率低于0.0047%，在性能上和开销上也远远优于奇偶校验等方式。

在数据存储和数据通讯领域，CRC无处不在，著名的通讯协议X.25的FCS(帧检错序列) 和磁盘驱动器的读写都采用了CRC作为检错手段。

循环冗余校验码CRC把任何一个二进制编码都与一个系数为0或1的多项一一对应，因此循环冗余校验码CRC又称为多项式码。

模2除法：多位二进制模2除法与普通意义上多位二进制除法类似，只是每次的求余数时，采用的是模2减法，每一位的运算不影响其他位，即不向上一位借位，实际上就是异或。

模2除法

1. 余数的首位为1，且位数与除数相同，商就为1
2. 两个数不比较大小，做异或运算得到结果