胖蔡说技术
随便扯扯

计算机硬件之校验码

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

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

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

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

码距

是指一个编码系统中任意两个合法编码(数据编码)之间不同二级制数位数的最小值。怎么理解昵,如:我们有一个4位的数据位:8421,各位相对应的二进制位:1000010000100001。其中任意两个二进制只有一位不同,所以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位,则nk满足如下关系:

2k – 1 >= n + k

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

2、编码规则

k校验位为:Pk,Pk-1,...,P1n数据位Dn-1,Dn-2,...,D1,D0,对应海明码为:Hn+k,Hn+k-1,...,H1,那么:

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

H12H11H10H9H8H7H6H5H4H3H2H1
D7D6D5D4P4D3D2D1P3D0P2P1

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

海明位H12H11H10H9H8H7H6H5H4H3H2H1
数据位/校验位D7D6D5D4P4D3D2D1P3D0P2P1
校验位组P3
P4
P1
P2
P4
P2
P4
P1
P4
P4P1
P2
P3
P2
P3
P1
P3
P3P1
P2
P2P1

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)出错,将其取反即可纠正错误。

赞(0) 打赏
转载请附上原文出处链接:胖蔡叨叨叨 » 计算机硬件之校验码
分享到: 更多 (0)

推荐文章

  • 暂无文章

请小编喝杯咖啡~

支付宝扫一扫打赏

微信扫一扫打赏