CRC循环冗余校验码

什么是CRC校验?CRC即循环冗余校验码:是数据通信领域中最常用的一种查错校验码,其特征是信息字段和校验字段的长度可以任意选定。循环冗余检查(CRC)是一种数据传输检错功能,对数据进行多项式计算,并将得到的结果附在帧的后面,接收设备也执行类似的算法,以保证数据传输的正确性和完整性。
CRC校验原理:其根本思想就是先在要发送的帧后面附加一个数(这个就是用来校验的校验码,但要注意,这里的数也是二进制序列的,下同),生成一个新帧发送给接收端。当然,这个附加的数不是随意的,它要使所生成的新帧能与发送端和接收端共同选定的某个特定数整除(注意,这里不是直接采用二进制除法,而是采用一种称之为“ 2除法”)。到达接收端后,再把接收到的新帧除以(同样采用“ 2除法”)这个选定的除数。因为在发送端发送数据帧之前就已通过附加一个数,做了“去余”处理(也就已经能整除了),所以结果应该是没有余数。如果有余数,则表明该帧在传输过程中出现了差错。模2除法:模2除法与算术除法类似,但每一位除的结果不影响其它位,即不向上一位借位,所以实际上就是异或。在循环冗余校验码(CRC)的计算中有应用到模2除法。例:

CRC校验步骤:CRC校验中有两个关键点,一是预先确定一个发送送端和接收端都用来作为除数的二进制比特串(或多项式),可以随机选择,也可以使用国际标准,但是最高位和最低位必须为1;二是把原始帧与上面计算出的除数进行模2除法运算,计算出CRC码。
具体步骤:1. 选择合适的除数2. 看选定除数的二进制位数,然后再要发送的数据帧上面加上这个位数-1位的0,然后用新生成的帧以模2除法的方式除上面的除数,得到的余数就是该帧的CRC校验码。注意,余数的位数一定只比除数位数少一位,也就是CRC校验码位数比除数位数少一位,如果前面位是0也不能省略。3. 将计算出来的CRC校验码附加在原数据帧后面,构建成一个新的数据帧进行发送;最后接收端在以模2除法方式除以前面选择的除数,如果没有余数,则说明数据帧在传输的过程中没有出错。
CRC校验码计算示例:现假设选择的 CRC生成多项式为 G( X) = X4 + X3 + 1,要求出二进制序列 10110011的 CRC校验码。下面是具体的计算过程 :①将多项式转化为二进制序列,由 G( X) = X4 + X3 + 1可知二进制一种有五位,第4位、第三位和第零位分别为1,则序列为11001②多项式的位数位5,则在数据帧的后面加上5-1位0,数据帧变为 101100110000,然后使用模2除法除以除数 11001,得到余数。

③将计算出来的CRC校验码添加在原始帧的后面,真正的数据帧为101100110100,再把这个数据帧发送到接收端。④接收端收到数据帧后,用上面选定的除数,用模2除法除去,验证余数是否为0,如果为0,则说明数据帧没有出错。

海明码的编码和校验方法

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

  编码

  确定校验码的位数x

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

2x≥n+x+1   

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

  确定校验码的位置

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

位置1234567891011
内容x1x21x3010x4110

  求出校验位的值

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

位置00010010001101000101011001111000100110101011
内容x1x21x3010x4110

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

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

位置00010010001101000101011001111000100110101011
内容01110100110

  因此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。