现在的位置: 首页 > 综合 > 正文

循环冗余校验(CRC)算法入门引导 读后总结

2019年03月22日 ⁄ 综合 ⁄ 共 1782字 ⁄ 字号 评论关闭

建议看原文,总结是给自己看的  http://blog.csdn.net/liyuanbhu/article/details/7882789

ysmz4读后总结:

crc的思想:

用户输入数据,除数           ----begin----

数据mod除数 = 余数           ----end----    所得余数即为校验字 

                                         

crc算法过程用多项式表示:

二进制流A -> 多项式的系数 A'

二进制流B -> 多项式的系数 B'

A' · B = x^n + ...... + x^0 (正常的多项式乘除法)

合并同类项(模2运算,即异或)

多项式系数 -> 二进制流C

啧啧,写完了仍不能完全理解,深奥啊。。。

crc算法过程用简洁方法表示:除法运算与上面给出的乘法概念类似,还是遇到加减的地方都用异或运算来代替

用户提供二进制数据流,提供除数。  ----begin----

数据流末尾补n个0(即根据需要的位宽补0)

数据流 mod 除数 = 余数                       ----end----         所得余数即为校验字 

除数的选择:

为了进行CRC运算,也就是这种特殊的除法运算,必须要指定被除数,在CRC算法中,这个被除数有一个专有名称叫做“生成多项式”。生成多项式的选取是个很有难度的问题,如果选的不好,那么检出错误的概率就会低很多。好在这个问题已经被专家们研究了很长一段时间了,对于我们这些使用者来说,只要把现成的成果拿来用就行了。

最常用的几种生成多项式如下:

CRC8=X8+X5+X4+X0

CRC-CCITT=X16+X12+X5+X0

CRC16=X16+X15+X2+X0

CRC12=X12+X11+X3+X2+X0

CRC32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+X0

16进制简记式 与 生成多项式项数次幂 的关系

多项式表示和二进制表示都很繁琐,交流起来不方便,因此,文献中多用16进制简写法来表示,因为生成多项式的最高位肯定为1,最高位的位置由位宽可知,故在简记式中,将最高的1统一去掉了,如CRC32的生成多项式简记为04C11DB7实际上表示的是104C11DB7。

eg.crc16 的简记式0x8005,全称应为0x18005,如何转换到生成多项式?0x18005 -> 二进制数->bit0为1则有X0项,以此类推。

关于位宽:

有一点要特别注意,文献中提到的生成多项式经常会说到多项式的位宽(Width,简记为W),这个位宽不是多项式对应的二进制数的位数,而是位数减1(ysmz4:或者说是多项式最高项的次幂)。

ysmz4:我理解的位宽就是被除数转成多项式之后的最高项的次幂(这句话终于把被除数和多项式联系起来了)。

梳理一下,流程就是:

设置位宽n -> 得生成多项式 x^n+ ....+x^0 (用常用的生成多项式)

   -> 被除数末尾补n个0 

被除数 mod 除数 = 余数,即校验字

关于被除数末尾补0:

一说” 之所以要补零,是要在信息流后面添加校验码,而补零的位置就是校验码的位置“


关于stm32内置硬件crc,见 STM32
CRC寄存器
  http://www.cnblogs.com/hnrainll/archive/2011/01/15/1936082.html

看起来内置硬件把数据流每次以32位分包,那就改不成crc16了。。

关于crc16

提供C和汇编两种方法  http://zhangxu1018.blog.sohu.com/161752060.html

时间和空间(表)是权衡的问题。

查找表的由来(需要可下载表生成器哦)   http://bbs.21ic.com/icview-47814-1-1.html

几种CRC16算法 (时间和空间的权衡)http://blog.csdn.net/qsycn/article/details/5430886

有哪些因素决定设置多少的位宽? 跟查错检出率有关,数学问题,不鸟。

原文看不懂的地方,解决了----------------------------------------------------------------------------------------------------------------------

Q:除数怎么来的?

A:除数就是生成多项式......

抱歉!评论已关闭.