海明码 CRC冗余校验码

  海明码(也叫汉明码)具有一位纠错能力。本文以1010110这个二进制数为例解释海明码的编码和校验方法

确定校验码的位数x

  设数据有n位,校验码有x位。则校验码一共有2x种取值方式。其中需要一种取值方式表示数据正确,剩下2x-1种取值方式表示有一位数据出错。因为编码后的二进制串有n+x位,因此x应该满足

2x-1 ≥ n+x   

  使不等式成立的x的最小值就是校验码的位数。在本例中,n=7,解得x=4。

确定校验码的位置

  校验码在二进制串中的位置为2的整数幂。剩下的位置为数据。如图所示。

位置
内容 x1 x2 x3 x4

确认校验位数据位关系

  将每个位置,都拆成校验位位置值相加,可知道一个校验位跟哪些数据位有关系

  海明码 CRC冗余校验码

求出校验位的值

  以求x2的值为例。为了直观,将表格中的位置用二进制表示。

位置
内容 x1 x2 1 x3 1 0 x4 1 0

  

  为了求出x2,要使所有位置的第二位是1的数据(即形如**1*的位置的数据)的异或值为0。即x2^1^1^0^1^0 = 0。因此x2 = 1。

  同理可得x1 = 0, x3 = 1, x4 = 0。

位置
内容

  因此1010110的海明码为01110100110。

  校验

  假设位置为1011的数据由0变成了1,校验过程为:

  将所有位置形如***1, **1*, *1**, 1***的数据分别异或。

  ***1: 0^1^0^0^1^1 = 1

  **1*: 1^1^1^0^1^1 = 1

  *1**: 1^0^1^0 = 0

  1***: 0^1^1^1 = 1

  以上四组中,如果一组异或值为1,说明该组中有数据出错了。***1 **1* 1***的异或都为1,说明出错数据的位置为1011。

CRC冗余校验

 

CRC的实现原理十分易于硬件实现,因此被广泛的应用于计算机网络上的差错控制。CRC校验码需根据CRC生成多项式进行。

关于软考中涉及到的海明码和CRC校验码,主要是两种的验证方式。海明码的校验过程比较复杂,在计算机中不经常用,而CRC校验码比较容易,先确定校验码的位数,以及除数是什么?所以个人感觉想要掌握这两种情况,就需要分析的方式。

实例:原始报文为11001010101,其多项式为X4+X3+X+1。在原始报文的后面若干个0(等于校验码的位数,而生成多项式的最高幂次就是校验位数,即使用该生成多项式产生的校验码为4位)作为被除数,除以生成多项式所对应的二进制数。

X4+X3+X+1对应的二进制为11011,则除数作为11011

运算时可借位,但被借的位数值不变,如01减10=11

海明码 CRC冗余校验码

然后把添加到原始报文的后面就是结果110010101010011

参考:

海明码的编码和校验方法

【软考】——海明码和CRC码

上一篇:Andriod使用webview控件往APP里内嵌网页


下一篇:8.9 正睿暑期集训营 Day6 C 风花雪月(DP)