软件设计师之效验码

计算机系统运行时,为了保证数据在传输过程中正确无误,提高硬件电路的可靠性和代码的效验能力(查错和纠错),通常使用效验码的方法来检测传输的数据是否出错。

1、奇偶效验码

奇偶效验通过在编码中增加一位效验位来使编码中的1的个数为奇数(奇效验)或者偶数(偶效验),从而使码距变成2。

1)水平奇效验

      原码          奇效验          偶效验

     0000         0000|1         0000|0

     0010         0010|0         0010|1

     1100         1100|1         1100|0

     1010         1010|1         1010|0

2)垂直奇偶效验

     垂直奇效验    垂直偶效验
     10100101    10100101
     00110110    00110110
     11001100    11001100
     10101011    10101011
     -------------------------
     00001011    11110100   效验码

3)缺点

只能检测奇数位出错,如果发生偶数位错误就无法检测,如:原码0000,传输过程中变成1001,奇效验后,原编码是00001,传输过后会变成100111仍是奇数个,无法检测。

奇偶效验码无法检测出哪位出错,属于无法矫正错误的验证码。

 

2、海明码

数据位是n位,效验码是k位,且n、k满足:2^k - 1 ≥ n + k,效验码放在2的幂次方位上,即“1,2,4,8……”

计算机原信息101101100的海明效验码:

P1、P2、1、P3、0、1、1、P4、0、1、1、0、0

效验位置:

P1:3、5、7、9、11、13    P1 = 1⊕0⊕1⊕0⊕1⊕0 = 1

P2:3、6、7、10、11          P2 =1⊕1⊕1⊕1⊕1 = 1

P3:5、6、7、12、13          P3 = 0⊕1⊕1⊕0⊕0 = 0

P4:9、10、11、12、13      P4 = 0⊕1⊕1⊕0⊕0 = 0

将P1~P4的结果代入海明效验码,即最后结果:

1、1、1、0、0、1、1、0、0、1、1、0、0

 

3、循环冗余效验码(CRC效验)

利用生成多项式为k个数据位产生r个效验位来进行编码,其编码长度为k+r

根据双方约定的R次多项式g(x),生成CRC码

CRC码特点:

  • 位数要少于原编码
  • 收尾为1
  • 自行决定

如:原编码为:1010001101

其CRC码可以为10011,也可以为11001等,但是10010这种不可以,因为它的尾巴不是11001101011也不行,因为它的位数与原编码的一致。

要注意的是:CRC码并非是校验码,但需要通过CRC码来获得校验码。具体校验码的话要先让原编码加上CRC码位数个0(即CRC码有的多少位,就要加上多少位0在原编码的后面)然后用新原编码除CRC码,得到的余数就是校验码

设原编码为:1010001101

CRC码设为:110101

校验码有5位,因此

新原编码:101000110100000

然后用新原编码除以CRC码(采用模2运算,过程省略),得到余数01110,效验码就是01110

因为效验码是由原编码产生的,效验码位数越多,该代码的效验能力就越强。

  • 用支付宝打我
  • 用微信打我

Long may the sunshine

发表评论

电子邮件地址不会被公开。 必填项已用*标注

召唤蕾姆