|
|
|
计算机系统运行时，各个部件之间要进行频繁的数据交换，为了确保数据在传送过程中正确无误，一是提高硬件电路的可靠性；二是提高代码的校验能力，以进行查错和纠错。通常使用校验码的方法来检测所存储和传送的数据是否出错，即对数据可能出现的编码分为合法编码和错误编码两类。合法编码用于存储和传送数据，错误编码是不允许在数据中出现的编码。合理地设计错误编码以及编码规则，使得数据在传送中出现某种错误时就会变成错误编码，这样就可以检测出接收到的数据是否有错。
|
|
|
|
码距是校验码中的一个重要概念。所谓码距，是指一个编码系统中任意两个合法编码之间至少有多少个二进制位不同。例如，4位8421码的码距为1，在传输过程中，该代码的一位或多位发生错误，都将变成另外一个合法编码，因此这种代码无差错检验能力。
|
|
|
|
下面简单介绍常用的三种校验码：奇偶校验码（Parity Codes）、海明码（Hamming Code）和循环冗余校验（Cyclic Redundancy Check，CRC）码。
|
|
|
|
|
|
奇偶校验是一种简单有效的校验方法。这种方法通过在编码中增加一个校验位来使编码中1的个数为奇数（奇校验）或者偶数（偶校验），从而使码距变为2。对于奇偶校验，它可以检测代码中奇数位出错的编码，但不能发现偶数位出错的情况，即当合法编码中奇数位发生了错误，也就是编码中的1变成0或0变成1，则该编码中1的个数的奇偶性就发生了变化，从而可以发现错误。8421码的奇偶校验码如下表所示。
|
|
|
|
|
|
|
|
从上表可知，带奇偶校验位的8421码由4位信息位和1位校验位组成，码距为2，能检查出代码信息中奇数位出错的情况，而错在哪些位是检查不出来的。也就是说，它只能发现错误，而不能校正错误。
|
|
|
|
常用的奇偶校验码有三种：水平奇偶校验码、垂直奇偶校验码和水平垂直校验码。
|
|
|
|
（1）水平奇偶校验码。对每一个数据的编码添加校验位，使信息位与校验位处于同一行。
|
|
|
|
（2）垂直奇偶校验码。这种校验码把数据分成若干组，一组数据占一行，排列整齐，再加一行校验码，针对每一列采用奇校验或偶校验。
|
|
|
|
（3）水平垂直校验码。在垂直校验码的基础上，对每个数据再增加一位水平校验位，便构成水平垂直校验码。
|
|
|
|
|
|
海明码（Hamming Code）是由贝尔实验室的Richard Hamming设计的，是一种利用奇偶性来检错和纠错的校验方法。海明码的构成方法是在数据位之间的特定位置上插入k个校验位，通过扩大码距来实现检错和纠错。
|
|
|
|
设数据位是n位，校验位是k位，则n和k必须满足以下关系：
|
|
|
|
|
|
|
|
设k个校验位为Pk，Pk-1，…，P1，n个数据位为Dn-1，Dn-2，…，D1，D0，对应的海明码为Hn+k，Hn+k-1，…，H1，那么：
|
|
|
|
（1）Pi在海明码的第2i-1位置，即Hj=Pi，且j=2i-1，数据位则依序从低到高占据海明码中剩下的位置。
|
|
|
|
（2）海明码中的任何一位都是由若干个校验位来校验的。其对应关系如下：被校验的海明位的下标等于所有参与校验该位的校验位的下标之和，而校验位由自身校验。
|
|
|
|
对于8位的数据位，进行海明校验需要4个校验位（23-1=7，24-1=15>8+4）。令数据位为D7，D6，D5，D4，D3，D2，D1，D0，校验位为P4，P3，P2，P1，形成的海明码为H12，H11，…，H3，H2，H1，则编码过程如下。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
（3）检测错误。对使用海明编码的数据进行差错检测很简单，只需做以下计算：
|
|
|
|
|
|
若采用偶校验，则G4G3G2G1全为0时表示接收到的数据无错误（奇校验应全为1）。当G4G3G2G1不全为0时说明发生了差错，而且G4G3G2G1的十进制值指出了发生错误的位置，例如G4G3G2G1=1010，说明H10（D5）出错了，将其取反即可纠正错误。
|
|
|
|
|
|
循环冗余校验码广泛应用于数据通信领域和磁介质存储系统中。它利用生成多项式为k个数据位产生r个校验位来进行编码，其编码长度为k+r。CRC的代码格式为：
|
|
|
|
|
|
由此可知，循环冗余校验码是由两部分组成的，左边为信息码（数据），右边为校验码。若信息码占k位，则校验码就占n-k位。其中，n为CRC码的字长，所以又称为（n，k）码。校验码是由信息码产生的，校验码位数越长，该代码的校验能力就越强。在求CRC编码时，采用的是模2运算。
|
|
|
|
模2加减运算的规则是：按位运算，不发生借位和进位，如下所示：
|
|
|
|
|
|
|
