请教一个CRC的问题【标题不合格将被封锁ID】 (amobbs.com 阿莫电子技术论坛) -

wind2100 发表于 2018-6-15 11:31:30

请教一个CRC的问题【标题不合格将被封锁ID】

本帖最后由 wind2100 于 2018-6-16 12:57 编辑

请教一下 CRC8 16 32 各适合做多少数据的校验, 准确率是多少?
CRC8适合做多少数据的校验?
CRC16,CRC32呢
准确率怎么计算?

有人懂这个理论的吗? 请教一下高手

wye11083 发表于 2018-6-15 12:32:31

2＾N位以内的数据进行保护。计算就是逢高位1移位异或，否则移位不异或。

dr2001 发表于 2018-6-15 14:01:48

本帖最后由 dr2001 于 2018-6-15 14:03 编辑

关键词：CRC Hamming Distance

参考网站：http://users.ece.cmu.edu/~koopman/crc/index.html

大体意思是：Hamming Distance （HD值）-1，是含CRC的bit流能检出的bit错误数。

例如：CRC-16， HD=3，65519 ，多项式0x8d95。
粗略理解就是：
对长度等于65519bit的数据流，CRC校验和固定为16bit，其余为数据。对其中的数据使用多项式为0x8D95的CRC-16计算校验和并一起传输。那么在接受端，一定可以检测出数据流中小于等于2bit的数据变化。

如果报文变短，或者变化的bit位有独特性，那么这个CRC-16可能能检测出更多位的变化，但不确保如此。
即CRC是“保证，至少”如何如何。

zhugean 发表于 2018-6-15 14:19:33

简单理解CRC8出错后不能检查出来的概率是256分之一，CRC16是65536分之一，CRC32是4294967296分之一。复杂点看根据数据通讯原理CRC校验能提高串行数据传输时错误的检出率，应该优于前面给出的数据

wind2100 发表于 2018-6-16 12:19:05

uint16_t crc16(unsigned char *addr, int num, uint16_t crc)
{
int i;
for (; num > 0; num--)          /* Step through bytes in memory */
{
   crc = crc ^ (*addr++ << 8); /* Fetch byte from memory, XOR into CRC top byte*/
   for (i = 0; i < 8; i++)          /* Prepare to rotate 8 bits */
   {
         if (crc & 0x8000)          /* b15 is set... */
            crc = (crc << 1) ^ POLY; /* rotate and XOR with polynomic */
         else                      /* b15 is clear... */
            crc <<= 1;                /* just rotate */
   }                         /* Loop for 8 bits */
   crc &= 0xFFFF;                /* Ensure CRC remains 16-bit value */
}                            /* Loop until num=0 */
return(crc);                /* Return updated CRC */
}

原理有点蒙B,肯定是有碰撞机率的(不同的数,生成了相同的校验值)CRC1 就会非常明显所以我才有这个问题, 感觉不深入理论不行,以前只知道用.
深入的人不多,大家只是用所以我才有此问题.

armok 发表于 2018-6-16 12:33:26

wind2100 发表于 2018-6-16 12:57:42

armok 发表于 2018-6-16 12:33
“请教一个CRC的问题 ”不是合格的标题。

违反版规11。请立即阅读版规(点击进入: http://www.amobbs.com/ ...

请教一下 CRC8 16 32 各适合做多少数据的校验, 准确率是多少?

wind2100 发表于 2018-6-16 12:59:26

CRC 已经很窄的问题了

jyrpxj 发表于 2018-6-16 14:40:17

楼主的意思：数据接收受干扰接收到数据（包含一起发送到CRC码）有误，但验证CRC缺通过的概率？

wind2100 发表于 2018-6-16 22:40:04

jyrpxj 发表于 2018-6-16 14:40
楼主的意思：数据接收受干扰接收到数据（包含一起发送到CRC码）有误，但验证CRC缺通过的概率？ ...

是的虽然我们在使用, 也知道多项式, 包括怎么计算, 但是我不知道为什么要这样计算,
这样计算到底有多少准确率呢?(我们知道的是越高越好)
因为是循环冗余计算, 干扰位置和干扰的数据都不确定可靠性有多高.就是这个意思
我用CRC8 做了一个简单的程序发现碰撞的机率非常大.

// CRC8.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "windows.h"

u8 tstdata={};

//===========================================================================================================
unsigned char CRC8_Func(unsigned char *ptr, unsigned int len)
{
unsigned char i;
unsigned char crc=0x00;    /* 计算的初始crc值 */

while(len--)
{
crc ^= *ptr++;    /* 每次先与需要计算的数据异或,计算完指向下一数据 */
for (i=8; i>0; --i) /* 下面这段计算过程与计算一个字节crc一样 */
{
if (crc & 0x80)
crc = (crc << 1) ^ 0x31;
else
crc = (crc << 1);
}
}

return (crc);
}

//===========================================================================================================
u8 FitParaFunc(u8 *pData, u16 length)
{
u16 i=30;          //只输出多少个数据
u16 randnum;       //随机位置
u8 randdata;       //随机数
u8 rstcrc,rstcrc2;//CRC结果

memset( pData, 0xAA, length);

rstcrc = CRC8_Func(pData, length);

//rstcrc = CRC8_Func(pData, length);//校验对否

//rstcrc = CRC8_Func(pData, length);

while(i)
{
randnum= rand()%length;
randdata = rand()%length;

memset( &pData, randdata, 1);//任意位置写一个随机数

rstcrc2 = CRC8_Func(pData, length);

if (rstcrc == rstcrc2)    //随机插入一字节随机数的结果与之前的结果对比
{
printf("===>rstcrc=0x%02X,", rstcrc);
printf("randnum=0x%02X, randdata=0x%02X\r\n", randnum, randdata);
i--;
}

}
return 0;
}

//===========================================================================================================
int _tmain(int argc, _TCHAR* argv[])
{
u16 length = sizeof(tstdata);

//memset( tstdata, 0xAA, length);

FitParaFunc(tstdata, length);

printf("===>%d\n",sizeof(tstdata));

system("pause");

return 0;
}

//===========================================================================================================

jyrpxj 发表于 2018-6-17 01:18:10

本帖最后由 jyrpxj 于 2018-6-17 01:31 编辑

假设通讯线路存在干扰, 平均每10000BIT 存在1BIT的错误.万分之一的出错率.

通讯发起方发 1Byte 数据 +1Byte 数据按位取反 , 接收方收到数据后,如果这两个字节是互补关系,就验证为通过. 以此作为一次完整的通讯.

那么这样一次通讯是正确无误的概率是 (1-0.0001)^16=0.99840119944018195632800685612869
失误的概率= 0.00159880055981804367199314387131

在前一字节某BIT出错的情况下,而后一取反字节也恰好在同样的BIT位出错的概率是1/256
即通讯发生错误, 而接收方没有检查出来,而认为没有出错的概率= 0.00159880055981804367199314387131*1/256 =6.25*10^-6 . 约百万分之六

通讯的bit出错率是万分之一的情况1字节数据1校验码时, 不能检出通讯错误的概率是约百万分之六

基于数据的任何改变,校验也必然改变的前提下:
bit出错率为aN字节数据M字节校验码时, 把错误数据当正确数据处理的概率
(1-(1-a)^((N+M)*8))/(256^M)
把正确数据误判为错误数据处理的概率是 (数据正确,但是CRC出错的情况)
(1-a)^(N*8) * (1-(1-a)^(M*8))

BIT出错率数据字节校验字节发生了错误却未检测到数据正确却校验错误
万BIT 百万次百万次
1 1 1 6.25 799.08
1 2 1 9.36 798.44
1 8 1 28.03 794.62
1 64 1 197.94 759.80
1 2 2 0.05 1596.24
1 4 2 0.07 1593.69
1 8 2 0.12 1588.60
1 64 2 0.78 1519.00
1 4 4 1.48543E-06 3184.84
1 8 4 2.22459E-06 3174.66
1 16 4 3.69583E-06 3154.41
1 64 4 1.23282E-05 3035.57
1 2 8 4.31972E-16 6369.68
1 8 8 6.89502E-16 6339.18
1 64 8 3.03442E-15 6061.44
1 64 64 7.2597E-150 47422.41

只有数据与校验等长时, 才能做到数据改变则校验必然改变.
考虑到一般情况下N比M大.平均有(N/M)*256组不同的数据对应相同的校验码.
但应该是大范围变化才会刚好使数据出错但对应的校验码相同.或者某一BIT出错, 另一特定的BIT也同时出错.
以2字节数据,1字节为校验, 校验为两数求和.
BYTE0 BYTE1 SUM
B10000001 B11000011 B01000100
如果BYTE0.BIT7出错的话, 则要求BYTE1.BIT7也出错,但是其它位却不能再出错.
如果BYTE0.BIT0出错的话, 则要求BYTE1.BIT2 1 0 同时出错,但是其它位不能再出错.
如果BYTE0.BIT2出错的话, 则要求BYTE1.BIT7 6 5 4 3 同时出错,但是其它位不能再出错.
可见以上这种数据发生变化而校验码恰好还正确的情况是极为少见的.要满足的条件也是很苛刻的.

楼主如果实在是要避免错误的数据被执行,那就把数据长度和校验长度做成等长,这样数据变化则必然校验也要求变化.这样的话执行错误数据的概率就是我上表N=M情况下的概率了.

armok 发表于 2018-6-17 02:01:36

cicnx 发表于 2018-6-17 08:56:21

armok 发表于 2018-6-17 02:01
标题不合格，不肯改正，ID被封锁。

正确的标题，内容里已经有『请教一下 CRC8 16 32 各适合做多少数据的 ...

老大，好像内容里面正确的标题就是楼主发给你修改的哦{:lol:}

bblythe2017 发表于 2018-6-17 10:58:43

本帖最后由 bblythe2017 于 2018-6-17 11:01 编辑

这个讨论很有价值。说出了CRC校验失效的概率。之前也有想过这个问题，一直没有得到答案。

简单理解CRC8出错后不能检查出来的概率是256分之一，CRC16是65536分之一，CRC32是4294967296分之一。复杂点看根据数据通讯原理CRC校验能提高串行数据传输时错误的检出率，应该优于前面给出的数据

页: [1]

amobbs.com 阿莫电子技术论坛's Archiver

请教一个CRC的问题 【标题不合格将被封锁ID】

请教一个CRC的问题【标题不合格将被封锁ID】