2.1 制与编码

2.1.5 校验码

　　校验码是指那些能够发现错误或能够自动纠正错误的数据编码，它的实现原理是加进一些冗余码，使合法数据编码出现某些错误时，就成为非法编码。这样就可以通过检测编码的合法性来达到发现错误的目的。
　　任何一种编码都由许多码字构成，任意两个码字之间最少变化的二进制位数就称为数据校验码的码距。例如，用4位二进制表示16种状态，则有16个不同的码字，此时码距为1，即两个码字之间最少仅有一个二进制位不同（如0000与0001之间）。这种编码没有检错能力，因为当某个合法码字中有一位或几位出错，就变成另一个合法码字了。这就需要我们合理地安排非法码字的数量和编码规则，才能达到纠错的目的。例如，若用4位二进制表示8个状态，其中只有8个码字是合法码字，而另8个码字为非法码字，此时码距为2。对于码距大于等于2的数据校验码，开始具有检错的能力。码距越大，检、纠错能力就越强，而且检错能力总是大于或等于纠错能力。
　　常见的校验码主要有奇偶校验码、海明校验码和循环冗余校验码等。
　　1．奇偶校验码
　　奇偶校验码是一种最简单的数据校验码，它的码距等于2，可以检测出一位错误（或奇数位错误），但不能确定出错的位置，也不能检测出偶数位错误。事实上一位出错的概率比多位同时出现的概率要高得多，所以虽然奇偶校验码的检错能力很低，但还是一种应用最广泛的校验方法。
　　奇偶校验码的编码方法是：由若干位有效信息（如一个字节），再加上一个二进制位（校验位）组成校验码，如图2-1所示。校验位的取值（0或1）将使整个校验码中“1”的个数为奇数或偶数，所以有两种可供选择的校验规律。

　　奇校验：整个校验码（有效信息位和校验位）中“1”的个数为奇数。
　　偶校验：整个校验码中“1”的个数为偶数。
　　奇偶校验码校验是检测全部检验码（包括有效信息位和校验位）中“1”的个数。奇校验时校验码中“1”的个数应该为奇数个，偶校验时校验码中“1”的个数应该为偶数个，如果符合这一情况则说明没有出错，反之则说明校验出错。
　　计算机在进行大量字节（数据块）传送时，不仅每一个字节都有一个奇偶校验位做横向校验，而且全部字节的同一位也设置一个奇偶校验位做纵向校验，这种横向、纵向同时校验的方法称为交叉校验。例如，4个字节组成的一个信息块，纵向、横向均约定为偶校验，各校验位取值如下：

　　交叉校验可以发现两位同时出错的情况，假设第二个字节的A₆、A₄两位均出错，第二个字节的横向校验位无法检出错误，但是第A6、A4位所在列的纵向校验位会显示出错，这与前述的简单奇偶校验相比要保险多了。
　　2．海明校验码
　　海明码是由Richard Hamming于1950年提出的，是目前仍广泛采用的一种有效的校验码，主存的ECC（Error Correcting Code）采用的就是与此类似的校验码。海明码实际上是一种多重奇偶校验，其实现原理是：在有效信息位中加入几个校验位形成海明码，使码距比较均匀地拉大，并把海明码的每个二进制位分配到几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现错误，还能指出错误的位置，为自动纠错提供了依据。
　　海明码有很多种，下面仅介绍能检测和自动校正一位错，并能发现两位错的海明码的编码原理。此时校验位的位数k和信息位的位数m应满足下列关系：2^k≥m+k+1。按上述不等式，信息位m值和校验位k值的对应关系如表2-3所示。

表2-3 信息位m值与校验位k值的关系

　　（1）海明码的编码。例如，一个数据由12位二进制位组成，m=8，按表2-3查出k=4，可表示为H₁₂ … H₂ H₁，4个校验位P₄～P₁对应的海明码位号应分别为：H₈、H₄、H₂、H₁，都满足P_i的位号等于2^i-1的关系。因此，有如下排列关系：

D₈D₇ 　D₆ D₅ 　P₄ 　D₄ D₃D₂P₃D₁ 　P₂ 　P₁

　　校验位P_i（i=1～4）的偶校验的结果为：

　　　　　　　　　　　　P₁=D₁⊕D₂⊕D₄⊕D₅⊕D₇
　　　　　　　　　　　　P₂=D₁⊕D₃⊕D₄⊕D₆⊕D₇
　　　　　　　　　　　　P₃=D₂⊕D₃⊕D₄⊕D₈
　　　　　　　　　　　　P₄=D₅⊕D₆⊕D₇⊕D₈

　　（2）海明码的校验。将接收到的海明码按如下关系进行偶校验，即：

　　　　　　　　　　　　S₁=P₁⊕D₁⊕D₂⊕D₄⊕D₅⊕D₇
　　　　　　　　　　　　S₂=P₂⊕D₁⊕D₃⊕D₄⊕D₆⊕D₇
　　　　　　　　　　　　S₃=P₃⊕D₂⊕D₃⊕D₄⊕D₈
　　　　　　　　　　　　S₄=P₄⊕D₅⊕D₆⊕D₇⊕D₈