wangshaosh123 发表于 2012-5-23 10:51:04

请教一个关于CRC校验的碰撞概率，以及其可靠性的分析

现有一帧数据前8个字节是信息 第9个字节是CRC8的校验码
如下：
byte0 byte1 byte2 byte3 byte4 byte5 byte6 byte7    byte8（CRC8校验码）

最理想的情况下 CRC8 有0~255这256种结果，去校验8个字节*一个字节8位=64位数据，则数据有2^64 = 18446744073709551616种可能
那出现错误 而CRC8校验出来的概率 = 1.3877787807814456755295395851135e-17   
这个数据看似合理其实每个CRC8校验码对应的数据不是18446744073709551616 - 256，所以这样分析是不对的

倘若每个CRC校验码对应的原始数据的个数是一样的，那么一个CRC8校验码对应的原始数据个数 = 18446744073709551616 / 256 = 72057594037927936
这样看的话碰撞的概率貌似也不少~~~~~~~~


现在我在做一个协议，准备把一帧数据由原来的9个自己 改成16个字节
如下：
byte0 byte1 byte2 byte3 byte4 byte5 byte6 byte7   byte8 byte9 byte10 byte11 byte12 byte13 byte14      byte15 （CRC8校验码）

CRC8 校验显然不能无限个字节的使用，那么使用起来比较可靠的范围应该是 多少个字节以内呢？


本人上面的分析显然很浅薄，不知道哪位高手来分析一下CRC校验的碰撞概率，以及使用的可靠性。



NJ8888 发表于 2012-5-23 12:10:19

用16位 32位校验

wangshaosh123 发表于 2012-5-23 14:01:47

本帖最后由 wangshaosh123 于 2012-5-23 14:58 编辑

因为CRC8的查表速度比较快而且只占一个字节
所以如果16个字节可以使用CRC8的情况下   就不考虑CRC16和CRC32了

NJ8888 发表于 2012-5-23 16:29:36

那你不如传送数据+数据的异或+CRC,这样通过CRC后再看数据是否符合异或.其实根据数据传输特性决定CRC验证可靠性.如果是以太网,本身协议加过CRC了,不用再算,如果是串口,通常是字节丢了,那很难通过CRC的.你希望一个包数据对应一个CRC值没有必要

wangshaosh123 发表于 2012-5-23 16:49:41

NJ8888 发表于 2012-5-23 16:29 static/image/common/back.gif
那你不如传送数据+数据的异或+CRC,这样通过CRC后再看数据是否符合异或.其实根据数据传输特性决定CRC验证可 ...

你说的数据异或实际上是奇偶校验吧
我现在是用的一个10M的高速串口本身就有奇偶校验了
你说串口一次丢一个字节   不过工控现场，环境比较恶劣，是很有可能出现一位错误的

现在主要是怕16个字节时CRC8校验实际上不起作用了。。。。

NJ8888 发表于 2012-5-23 16:52:02

我说的异或是说你的数据正传一次,各位取反传一次,加倍,在算总CRC.10M高速串口是同步串口吧

wangshaosh123 发表于 2012-5-23 20:29:50

NJ8888 发表于 2012-5-23 16:52 static/image/common/back.gif
我说的异或是说你的数据正传一次,各位取反传一次,加倍,在算总CRC.10M高速串口是同步串口吧 ...

我用的是异步串口

你说的这种方法是什么原理呢？

而且你说的这个数据量要差不多翻倍了

huayuliang 发表于 2012-5-23 21:05:49

按照 2^(n-1)-1 选择，n 为要校验的数据长度（bit 数）。
对于CRC-8，按式子计算，再换成byte数，适合2^6=64及以下的数据长度。超过这个长度会产生相同的校验和。

wikipedia 上有～～

cjr82123 发表于 2012-5-23 21:49:26

持续关注...

huayuliang 发表于 2012-5-24 11:45:58

贴上相关地址吧，想必很多人都不清楚：
http://en.wikipedia.org/wiki/Cyclic_redundancy_check
中的
Designing CRC polynomials

wangshaosh123 发表于 2012-5-24 13:27:06

设计 CRC 多项式
生成多项式的选择是 CRC 算法实现中最重要的部分，所选择的多项式必须有最大的错误检测能力，同时保证总体的碰撞概率最小。多项式最重要的属性是它的长度，也就是最高非零系数的数值，因为它直接影响着计算的校验和的长度。

最常用的多项式长度有

9 位 (CRC-8)
17 位 (CRC-16)
33 位 (CRC-32)
65 位 (CRC-64)
在构建一个新的 CRC 多项式或者改进现有的 CRC 时，一个通用的数学原则是使用满足所有模运算不可分解多项式约束条件的多项式。

这种情况下的不可分解是指多项式除了 1 与它自身之外不能被任何其它的多项式整除。
生成多项式的特性可以从算法的定义中推导出来：

如果 CRC 有多于一个的非零系数，那么 CRC 能够检查出输入消息中的所有单数据位错误。
CRC 可以用于检测短于 2k 的输入消息中的所有双位错误，其中 k 是多项式的最长的不可分解部分的长度。
如果多项式可以被 x+1 整除，那么不存在可以被它整除的有奇数个非零系数的多项式。因此，它可以用来检测输入消息中的奇数个错误，就像奇偶校验函数那样。


{:dizzy:}   我没看出来他是怎么算的。。。。。

wangshaosh123 发表于 2012-5-24 14:09:16

本帖最后由 wangshaosh123 于 2012-5-24 14:13 编辑

没找到具体原因但是应该算是找到结果

另外上传俩文档

cjr82123 发表于 2012-5-24 15:27:59

wangshaosh123 发表于 2012-5-24 14:09 static/image/common/back.gif
没找到具体原因但是应该算是找到结果

另外上传俩文档

楼主,你截图中的
<64 Bytes:8-bit CRC
<16K Bytes:16-bit CRC
<512M Bytes:32-bit CRC
是在那个文档啊,我怎么找不到的呢?

wangshaosh123 发表于 2012-5-24 16:03:12

cjr82123 发表于 2012-5-24 15:27 static/image/common/back.gif
楼主,你截图中的


如果是CRC8   则2**(8 + 1) - 1 = 511bit也就是64byte

如果是CRC16   则2**(16 + 1) - 1 = 131071bit也就是16Kbyte

wulaia 发表于 2012-9-19 13:59:36

支持！顶起！支持！顶起！支持！顶起！支持！顶起！

yixinyiyi 发表于 2013-7-6 09:27:53

好帖，标记一下

youpeng 发表于 2013-7-14 23:47:24

长知识了，真没仔细考虑过呢。

majialou 发表于 2014-3-31 15:34:40

wangshaosh123 发表于 2012-5-24 16:03
如果是CRC8   则2**(8 + 1) - 1 = 511bit也就是64byte

如果是CRC16   则2**(16 + 1) - 1 = 131071bit ...

请问一下，你的计算公式在那篇文章中可以找到，谢谢

wangshaosh123 发表于 2014-5-13 18:23:51

是在一篇文章里面说的   没有计算过程
页: [1]
查看完整版本: 请教一个关于CRC校验的碰撞概率，以及其可靠性的分析