每日一个软考知识点之【CRC校验】

发布时间 2023-08-11 14:30:41作者: little天

CRC校验的原理

(此图引用自知乎)

发送方可以通过一定的算法生成校验位,然后接收方通过相同的算法验证一边,确保数据的真实性完整性。

 

几个重要的概念

POLY:可以多项式表达,也可以用2进制或者16进制来表达,比如说多项式为G(x) = x^5 + x^3 + x + 1,用二进制显示就是101011,用十六进制显示就是0x2B,

这里有一个要求,就是二进制的第一位和最后一位必须为1。

校验值:经过计算,最后求得的校验值的位数比这个POLY的二进制位数肯定少一位。

原始数据:就是传输的原始数据。注意在计算校验值之时,原始数据需要向左移动校验值的位数。

REFIN:true或false,在进行计算之前,原始数据是否翻转,假如这个值为true,说明原始数据需要翻转,比如说原始数据时111000110,

那么反转后为:011000111。

REFOUT:true或false,运算完成之后,得到的CRC值是否进行翻转,假如这个值为true,说明得到的CRC校验值需要反转,

假如得到的CRC校验值为:11001,那么反转后为:10011.

 

计算CRC值的详细步骤

1.确定原始数据,如果REFIN为true时,还需要对原始数据进行翻转操作。

2.确定POLY,把多项式或者16进制,转化为二进制。

3.验证最终得到的校验值的二进制位数,等于POLY二进制的位数减1,如果不等于,说明在转化POLY的时候出错了。

3.把原始数据进行左移,移动的位数为最终得到的校验值的位数。

4.对原始数据和POLY二进制的值,使用模2除法,获得余数,就是校验值。核对位数是否等于第三步中确定的位数,如果对不上,就是算错了。

 

模2除法如何计算

1.被除数第一位为1时,商为1,把除数作为结果,进行异或运算。

2.去掉结果的第一位,把原始被除数的后一位移下来补上。

3.这个时候去看新的被除数的第一位是否是1,如果是1,再记商为1,把除数作为结果,进行异或运算;如果不是1,记商为0,把新的被除数的第一位再划掉。

4.重复第二步和第三步,直到余数的位数等于预定的位数,或者直到把商写满,(这两者其实是一定一起发生的)。

例子:

 

 

注意:得到了CRC检验值后,验证一下位数是否正确。然后看下REFOUT的值,需要翻转的话,再翻转一下。

 

本文参考:

https://zhuanlan.zhihu.com/p/256487370