计算机硬件之校验码

计算机系统运行时，系统为确保数据在传输过程中不出错，一般会通过如下几种方式来提高数据的可靠性：

• 提高硬件电路的可靠性
• 提高代码的校验能力（差错和纠错）

本文主要介绍如何提高代码的校验能力，通常我们使用校验码的方法来检测传输数据的准确性。其基本原理是将数据可能出现的编码分为两类：

• 合法编码：用于传输数据
• 错误编码：不允许在数据中出现的编码

码距

是指一个编码系统中任意两个合法编码（数据编码）之间不同二级制数位数的最小值。怎么理解昵，如：我们有一个4位的数据位：8421，各位相对应的二进制位：1000、0100、0010、0001。其中任意两个二进制只有一位不同，所以8421的合法编码的码距就是1。

通过码距我们可以做什么呢？ 码距可以帮助我们检测合法编码是否发生错误，如一组有效的二进制数字0000，0011，1100，0110，1001，1010，0101,这一组的码距是2，在传输过程中如果0000被传为0001，只有一位发生错误，那么计算机就可以检测出来这个错误，而且不管是哪一个编码，只要误传的位数为1那么都可以检测出来。但如上的8421的码距是1，在传输过程中1000被误传为0100，其本身也是合法编码，就无法检测发生了错误。由此可得出：码距越大，其纠错能力越大。

奇偶校验码

奇偶校验（Parity Codes）通过在编码中增加一个校验位来使得编码中1的个数为奇数（奇校验）或为偶数（偶校验），从而使得码距变为2。为什么码距是2呢？因为对于奇偶校验码来说，任意两个校验码之间，如果想不同，最少变换两个位置的码元才可以完成。比如对于10011（奇校验）来说，如果我任意反转一个码元，1的个数肯定为偶数个，所以我至少需要反转两个码元才可以是另一个奇校验码。而反转的这个数字就是奇校验码的码距。常用的奇偶校验码如下：

• 水平奇偶校验码：水平奇偶校验又称为横向奇偶校验,它是对各个信息段的相应位横向进行编码,产生一个奇偶校验冗余位。
• 垂直奇偶校验码：垂直奇偶校验又称为纵向奇偶校验,它是将要发送的整个信息块分为定长p位的若干段(比如说q段),每段后面按”1″的个数为奇数或偶数的规律加上一位奇偶位。
• 水平垂直奇偶校验：同时进行水平奇偶校验和垂直奇偶校验就构成水平垂直奇偶校验,也称为纵横奇偶校实验。

注意：奇校验只能发现奇数个错误位；偶校验只能发现偶数个错误位；奇偶校验只能差错不能纠错。

海明码

海明码（Hamming Code） 由贝尔实验室设计，是一种利用奇偶性来检错和纠错的校验方法。海明码的构成方法是在数据位之间的特定位置上传入k个校验位，通过扩大码距来实现检错和纠错。

1、校验规则

加入有限编码数据位为n位，校验位为k位，则n和k满足如下关系：

2^k – 1 >= n + k

注意，通过该公式一般可以给定数据位的最小校验位，不设上限。

2、编码规则

设k个校验位为：Pk,Pk-1,...,P1，n个数据位为Dn-1,Dn-2,...,D1,D0,对应海明码为：Hn+k,Hn+k-1,...,H₁,那么:

① Pi在海明码的第2i-1的位置，即Hj = Pi，且j = 2i-1,数据位则依序从低到高占据海明码中剩余的位置。对于8位的数据位，进行海明码校验需要4个校验位（23-1 = 7,24-1 = 15 > 8+4）。则对应的数据位和校验位在海明码中的位置关系如下：

② 海明码中的任何一位都是由若干校验位来校验的，其对应关系：被校验的海明位的下标等于所有参与校验该位的校验位的下标之和，而校验位由自身校验。如上所示：H5海明位的下标位为5（5 = 4 + 1），寻找对应H1和H4下的校验位为：P1、P3。如上对应校验关系：

3、校验方式

采用偶校验时，各校验位的值等于含有该校验位的数据位的异或运算。如上含有P1的数据位有：

D0、D1、D3、D4、D6

则校验如下：

P1 = D0 ⨁ D1⨁ D3 ⨁ D4 ⨁ D6

异或运算的规则是：
           0 ⨁ 0 = 0            0 ⨁ 1 = 1
           1 ⨁ 1 = 0            1 ⨁ 0 = 1

若采用奇校验则将各校验位的偶校验值求反即可。

4、 检测错误

将校验位P与其相对应的数据位进行异或运行，并根据结果生成编码结果，上述示例如下：

G1 = P1 ⨁  D0 ⨁ D1 ⨁ D3 ⨁ D4 ⨁ D6
G2 = P2 ⨁  D0 ⨁ D2 ⨁ D3 ⨁ D5 ⨁ D6
G3 = P3 ⨁  D1 ⨁ D2 ⨁ D3 ⨁ D7
G4 = P4 ⨁  D4 ⨁ D5 ⨁ D6 ⨁ D7

若采用偶校验，则G1、G2、G3、G4全为0时表示数据无错误（奇校验则全为1时，数据无错误）。不全为0则说明传输出错，且G4G3G2G1的十进制值指出发生错误的位置，如G4G3G2G1=1010，说明H10(D5)出错，将其取反即可纠正错误。