《计算机组成原理》
——《数据的表示和运算（下）》
2.6 数据校验码
减少和避免元器件故或噪音干扰等出现的差错： • 一方面可以通过硬件本身的可靠性入手，在电路、电源、布线提高抗干扰能力； • 另一方面可以采取相应的数据检错和校正措施，自动发现并纠正错误 常用的数据校验码： • 奇偶校验码 • 海明校验码 • 循环冗余校验码
位置，不具有纠错能力。但该方法所用的开销小，常用于存储器读写检查或按 字节传输过程中的数据校验。
2.6 数据校验码
2.6.2 海明校验
• 海明校验码由Richard Hamming于1950年提出，其主要思想是： 将数据按某种规律分成若干组，对每组进行相应的奇偶检测，以提供多位校验信 息，从而可对错误位置进行定位，并将其纠正。 • 海明校验码实质：一种多重奇偶校验码。
2.6 数据校验码
2.6.1 奇偶校验 假设将数据B=bn-1bn-2…b1b0从源部件传送至终部件。在终部件接收到的数据为 B'=b n-1'b n-2'...b 1'b0'。为了判断数据B在传送中是否发生了错误，可以按照如下 步骤来判断: 1) 在源部件求出奇(偶)校验位P.若采用奇校验方式，则P= bn-1⊕bn-2⊕…b1⊕b0⊕1,
2.6 数据校验码
2.6.2 海明校验 最终比较时按位进行异或操作，即P‘和P”按位异或，根据异或操作的结果，确 定是否发生了差错。这种异或操作所得到的结果被称为故障字。显然，校验位和 故障字的位数是相同的。海明校验过程如下：
2.6 数据校验码
2.6.2 海明校验 1.校验位的位数的确定 假定被校验数据M的位数为n，校验位P为k位，则故障字的位数也为k位。那么k 位的故障字所能表示的状态最多是2k种，每种状态可用来说明一种出错情况。对 于最多只有一位错的情况，其结果可能是无错、或n位数据中某一位出错、或k位 校验码中某一位出错。因此，共有1+n+k种情况，所以，要能对一位错的所有结 果进行正确表示，则n和k必须满足下列关系: 2k >=1+n+k, 即 2k-1 >=n+k
即当B中有奇数个1时P取0,否则，P取1。若采用偶校验方式，则P= bn-1⊕bn2⊕…b1⊕b0，即当B中有偶数个1时P取0,否则，P取1.
如下：若传送的是字符A,其ASCII码为1000001，因为编码中有两个1，即有 偶数个1，所以，奇校验位P=1，也即，前面增加奇校验位后的编码为1100 0001。若采用偶校验方式，则P=0,前面加上偶校验位后的编码为0100 0001.
2.6 数据校验码
2.6.2 海明校验 2.分组方式的确定 数据位和校验位是一起被存储的，通过将它们中的各位按某种方式排列为一个 (n+k)位的码字，将该码字中每一位的出错位置与故障字的数值建立关系，这样 就可通过故障字的值很快确定是该码字中的哪一位发生了错误，从而将其取反来 进行纠正。
Hale Waihona Puke 2.6 数据校验码检错、纠错能力的校验码，常用于外存储器的数据校验。 • 在数据传输中，奇偶校验码是在每个字符信息中增加一位奇偶校验位来进行数
据校验的，但是在网络通信中，传输的数据信息都是二进制比特流，因而没有 必要将数据再分解成一个个字符，故无法采用奇偶校验码，因此，通常采用 CRC码进行校验。 • 循环冗余校验码是通过某种数学运算来建立数据和校验位之间的约定关系。
2.6 数据校验码
2.6.2 海明校验 1.校验位的位数的确定 例如，对于单个位纠错的情况，当数据有8位时，校验位和故障字都应有4位。因 为4位的故障字最多可以表示16(24)种状态，而单个位出错情况最多只有12种可 能(8个数据位和4个校验位中的某二位出错)，再加上无错的情况，一共有13种情 况。所以，用16种状态表不13种情况应是足够了。
2.6 数据校验码
2.6.1 奇偶校验
⊕异或运算符：如果a、b两个值不相同，则异或结果为1。如果a、b两个值 相同，异或结果为0 2 ） 在 终 部 件 求 出 奇 ( 偶 ) 校 验 位 P' 。 若 采 用 奇 校 验 方 式 ， 则 P' =bn-1' ⊕ bn2'⊕…b1'⊕b0'⊕1。若采用偶校验方式，则P' =bn-1' ⊕bn-2'⊕…b1'⊕b0'
对于上述例子，假定传送的ASCII码100 0001被送到终部件后，变成了100 0011，则得到奇校验位P'=0。若采用偶校验方式，则得到偶校验位P'=1.
2.6 数据校验码
2.6.1 奇偶校验
3）计算最终的校验位P'，并根据其值判断有无奇偶错。P与B是一起从源部件传 到终部件的，假定P在终部件接受到的值为P”。则P*=P’⊕P”。若P*=1，则表 示有奇数位错，若 P*=0，则表示正确或有偶数个错。
2.6.2 海明校验 2.分组方式的确定 根据上述基本思想，我们按以下规则来解释各故障字的值： (1)如果故障字各位全部是0,则表示没有发生错误。 (2)如果故障字中有且仅有一位为1，则表示校验位中有一位出错，不需要纠正。 (3)如果故障字中多位为1，则表示有一个数据位出错，其在码字中的出错位置由 故障宇的数值来确定。纠正时只要将出错位取反即可。
海明校验有单纠错码(SEC)和单纠错/双检错码(SEC-DED)。前者只能对单个 位出错进行定位和纠错，因此被称为单纠错码；后者同时具有发现两位错和纠正 一位错的能力，简称“纠一检二” 码。
2.6 数据校验码
2.6.5 循环冗余校验 2.6.3循环冗余校验 • 循环冗余校验码(Cyclic Redundancy Check)，简称CRC码，是一种具有较强
对于上述例子，假定P被传送到终部件后没有发生变化，也即，奇校验方式 下 P”=P=1 ， 或 者 偶 校 验 方 式 下 P”=P=0 ， 那 么 ， 奇 校 验 方 式 下 ， P*=P’⊕P”=0⊕1=1，偶校验方式下，P*=P’⊕P”=1⊕0=1，
2.6 数据校验码
2.6.1 奇偶校验
• 上述例子中，不管奇校验还是偶检验，最终的P*都为1，说明有奇数位错。 • 在奇偶校验中，只能发现奇数位出错，不能发现偶数位出错，也无法确定出错