wuyage

你真的搞明白CRC的计算过程了吗?

1
阅读(18626)

百度上介绍CRC计算原理和方法的文章一大推,也许是我太愚笨,花了几个小时的时间也没有完全看明白。最终经过我不断的尝试和研究,终于把整个计算过程搞清楚了。做个记录总结一下。。。


下面直奔主题,网上找了两个计算CRC的软件,输入同样的数据,选择同样的算法,得到的结果一样,

1.jpg


2.jpg


这两个软件的对应关系如下:

3.jpg

把CRC Calculator Info 中的这几个参数弄明白,CRC的过程你也就清楚了

Name:就是算法的名称,比如对于16bit的CRC来说就有好多个名字,也就是虽然都是16 bit CRC,但是计算方式也有好多种

4.jpg

Width:指的CRC校验值的长度,通常有8bit,16bit,24bit,32bit等。


Poly:是多项式的值,以上面图中的CRC-8:x8+x2+x+1为例,它表示二进制为100000111,

去掉最高位的1,十六进制表示就是0x07


Init: Init 的位数和Poly的位数相同,它的值为全0或者全F,当全为0时,在算法开始前对数据(这个数据是根据RefIn的值得到的)后面补上CRC位数个0后就可以进行后续计算了。当全为1时,表示在算法开始前对数据的前CRC位数(高位)先和对应位数个1进行异或(即:前CRC位数的值按位取反),再在后面补上CRC位数个0,才进行后续计算。


RefIn和Refout:它们要么全为False,要么全为True,

RefIn为False表示,输入的原始数据的每个字节的第7位作为最高有效位,第0为作为最低有效位,即正常计算即可

当RefIn为True时,输入的原始数据的每个字节需要做个逆序的处理,注意:针对的每个字节,而不是整个数据,以一个4字节的原始数据为例:

5.jpg


当Refout为False时,输出不做处理,当Refout为True,需要对输出数据做一次整个数据的逆序处理,注意:这里做的逆序和RefIn不同,它不是按字节逆序,而是整个逆序,以CRC-32为例来说明,最后的数据为32位,当Refout为True时,翻转如下:

6.jpg

XorOut:表示根据上面参数计算完后,和这个数再进行一次异或。


下面分析一下上面的结果0x79的由来:

1) 0x13 对应二进制为00010011

2) 由于RefIn为False,所以0x13不做处理还是00010011

3) 因为Init为0x00,00010011后面加8个0即可,输入数据变为0001001100000000

4) 多项式为x8+x2+x+1 对应二进制100000111,将上述0001001100000000 除以该多项式对应的100000111

整个计算过程如下:

10011 QUOTIENT


_________________

100000111 ) 0001001100000000 DIVIDEND

DIVISOR ) 100000111

-------------

110111000

100000111

--------- 异或运算

101111110

100000111

---------

01111001 REMAINDER


说明:上述的计算没有使用通常除法运算中用到的减法,这里用异或代替了减法

最后得到余数:01111001

7)由于RefOuT为False,所以余数不变,还为01111001

8)由于Xorout为0,表示不用再取反,所以最终的结果就是01111001,即十六进制0x79


算一个不过瘾,我们再来计算一个

7.jpg

这一次和上面唯一的不同是将初始值由原来的0x00换为了0xFF,没错这个例子就是给大家演示初始值到底什么意思.

下面分析一下上面的结果0x79的由来:

1) 0x13 对应二进制为00010011

2) 由于RefIn为False,所以0x13不做处理还是00010011

3)因为Init为0xFF,00010011的高8位要先与0xFF异或,输入数据变为11101100,后面再加入8个0,变为 1110110000000000

4) 多项式为x8+x2+x+1 对应二进制100000111,将上述1110110000000000 除以该多项式对应的100000111

整个计算过程如下:

11101110 QUOTIENT

_________________

100000111 ) 1110110000000000 DIVIDEND

DIVISOR ) 100000111

-------------

110111110

100000111

--------- 异或运算

101110010

100000111

---------

111010100

100000111

---------

110100110

100000111

---------

101000010

100000111

---------

10001010

00000000

---------

10001010 REMAINDER

最后得到余数:10001010

7)由于RefOuT为False,所以余数不变,还为10001010

8)由于Xorout为0,表示不用再取反,所以最终的结果就是10001010,即十六进制0x8A


这个例子演示了初始值的含义,我们再看最后一个例子,这个例子演示了RefIn和RefOut为True的具体含义

8.jpg

1) 0x13 对应二进制为00010011

2) 由于RefIn为True,所以0x13需要逆序一下得到11001000

3) 因为Init为0x00,所以2)的到11001000后面直接添加4个0即可,得到110010000000

4) 多项式为x4+x+1 对应二进制10011,将上述110010000000 除以10011

整个计算过程如下:

11011110 QUOTIENT

______________

10011 ) 110010000000 DIVIDEND

DIVISOR ) 10011

-------------

10100

10011

---------

11100

10011

---------

11110

10011

---------

11010

10011

---------

10010

10011

---------

00010

00000

---------

0010 REMAINDER


最后得到余数:0010

7)由于RefOuT为True,所以余数要逆序变为0100

8)由于Xorout为0,表示不用再取反,所以最终的结果就是0100


相信大家把上述那个计算过程弄明白,CRC的计算原理也就清楚了。至于软件代码上如何具体实现,以后再探讨。对于Kinetis MCU来说,很多MCU本身集成了硬件CRC模块,你只需要配置配置寄存器,就可以算出CRC结果了。但是不管对于软件实现还是硬件实现,理论基础永远是第一位的。


附件用到的CRC计算软件:

CRC计算软件.rar


参考资料:

1)http://www.ross.net/crc/download/crc_v3.txt

2)https://xcore.github.io/doc_tips_and_tricks/crc.html

3)http://www.amobbs.com/thread-4306317-1-1.html

4)https://www.ghsi.de/CRC/indexDetails.php?Polynom=11000000000000101&Message=FF

5)http://www.xz7.com/company/10511.htm





Baidu
map