|
|
|
数据在形成、存取和传送的过程中可能产生错误，为减少和避免这类错误，一方面提高计算机硬件本身的可靠性，另一方面在数据编码上找出路，设计出可靠性编码，比如前面说的格雷码。而数据校验码是一种常用的带有发现某些错误或带有自动改错能力的数据编码方法。常用的有奇偶校验码、海明校验码、循环冗余码。一个编码系统中任意两个合法编码（码字）之间不同的二进制数位（bit）数叫这两个码字的码距，而整个编码系统中任意两个码字的最小距离就是该编码系统的码距。为了使一个系统能检查和纠正一个差错，码间最小距离必须至少是3。下表概括了最小距离为1~7的码的纠错和检错能力。
|
|
|
|
|
|
|
|
|
|
|
|
奇偶校验码就是将要传输的数据加一位校验位，下一次读取时验证其合法性。这种方案只能发现一位错或奇数个位错，但不能确定是哪一位错。
|
|
|
奇偶校验分为奇校验和偶校验两种，假设一个二进制数为a0,a1,a2, …， an-1，则偶校验位an=a0⊕a1⊕a2⊕…⊕an-1，奇校验位 。
|
|
|
|
在实际工作中，还经常采用纵横都加奇偶校验位的编码系统——分组奇偶校验码。
|
|
|
|
现在考虑一个系统，它传输若干个长度为m位的信息。如果把这些信息都编成每组n个信息的分组，则在这些不同的信息间，也如对单个信息一样，能够作奇偶校验，n个信息的一个分组排列成矩形式样，并以横向奇偶（HP）及纵向奇偶（VP）的形式编出奇偶校验位。分组奇偶校验码不仅能检测许多形式的错误，并且在给定的行或列中产生孤立的错误时还可对该错误进行纠正。
|
|
|
|
|
|
在数据中多加入几个校验位，把数据的每一个二进制位分配在几个奇偶校验组中，当某一位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现错误，还能指出哪一位出错。
|
|
|
|
首先要确定校验位的个数。假设校验位个数为r，则它能表示2r个信息，用其中一个信息表示没有错误，其余2r-1个信息指出哪一位错，而错误也可能发生在校验位，因此只有k=2r-1-r个信息能用于纠正被传送数据的位数。也就是说要满足关系
|
|
|
|
|
|
注意：如要能检测与自动校正一位错，并发现两位错，那么还要加一位总校验位，则码距为4，此时应满足
|
|
|
|
|
|
按上述不等式计算，可计算出数据位k与校验位r的对应关系，如下表所示。
|
|
|
 k与r的对应关系
|
|
|
|
设海明编码为HmHm-1…H2H1，则此海明码的编码规则是：校验位与数据位之和为m，每个校验位Pi在海明码中被分配在位号为2i-1的位置，其余各位为数据位依次排列；海明码的每一位码Hi由多个校验位校验，其关系是被校验的每一位的位号等于校验它的各校验位之和。
|
|
|
|
可以看一个例子。现在要传送一个字节的数据，则k=8，那么r=4，所以海明码的总位数为12，可表示为
|
|
|
|
|
|
4个校验位P4~P1对应的编号是H8、H4、H2、H1。其余为数据位Di，则有以下排列：
|
|
|
|
|
|
那么可以知道，D8处在H12的位置，12=4+8，所以由处在H4的P3和处在H8的P4检测，这样依次类推，可以得到由P1检测的数值位有D1、D2、D4、D5和D7，若用偶校验，其结果为
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
则校验得到的结果值S4~S1能反映海明码出错情况。按S4S3S2S1的顺序排列形成一个二进制数，转换为十进制数为j，表示Hj出错。
|
|
|
|
|
|
在串行传送（磁盘、通信）中，广泛采用循环冗余校验码（CRC码）。
|
|
|
|
循环冗余校验码的基本原理是：在K位信息码后再拼接R位的校验码，整个编码长度为N位，因此，这种编码又叫（N,K）码。对于一个给定的（N,K）码，可以证明存在一个最高次幂为N-K=R的多项式G（x）。根据G(x）可以生成K位信息的校验码，而G（x）叫作这个CRC码的生成多项式。
|
|
|
|
|
|
|
|
|
|
|
|
校验码的具体生成过程为：假设发送信息用信息多项式C（x）表示，将C（x）左移R位，则可表示成C（x）×2R，这样C（x）的右边就会空出R位，这就是校验码的位置。通过对多项式C（x）×2R用模2除法除以生成多项式G（x）得到的余数就是校验码。
|
|
|
|
模2除法是指在进行除法运算的过程中进行减法运算时不考虑借位的问题，也就是0-0=0，0-1=1, 1-0=1, 1-1=0。
|
|
|
|
|
|
|
|
|
|
如果循环码有一位出错，用G（x）做模2除将得到一个不为0的余数。如果对余数补0继续除下去，将发现一个有趣的结果：各次余数将按顺序循环。例如，第7位出错，余数将为001，补0后再除（补0后若最高位为1，则用除数做模2除取余；若最高位为0，则其最低3位就是余数），得到第二次余数为010。以后继续补0作模2除，依次得到余数为100，011，反复循环，这就是"循环码"名称的由来。这是一个有价值的特点。如果在求出余数不为0后，一边对余数补0继续做模2除，同时让被检测的校验码字循环左移，当出现余数101时，出错位也移到A1位置，可通过异或门将它纠正后在下一次移位时送回A7。这样就不必像海明校验那样用译码电路对每一位提供纠正条件。当位数增多时，循环码校验能有效地降低硬件代价，这是它得以广泛应用的主要原因。
|
|
|
