[转贴]悟空，CRC原来是这么回事！

只看该作者 · 2007-4-5 23:29

悟空：师傅，最近我被CRC搞的头晕脑涨？
~~~：那是何方神圣？
悟空：CRC通用数据传送的校验编码。
~~~：555，
悟空：？？？？
~~~：加快追赶青春的脚步，飞速与世界接吻咯。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
几天后，

悟空：师傅你怎满脸青一块紫一块？
~~~：FANS太多，还真让人伤脑筋啊~~~~~~~~~~~
悟空：知道自己是近视眼，就别盯着别人的MM，被暴打了把。
~~~：多年不出山，没想到还怎么受欢迎！
悟空：观音姐姐，救救我~~~~~~
……—￥%……￥……￥%##￥%#%￥#%#%%%￥
悟空：让你没事就长篇大论，我T~~~~
~~~：我招了

======================================================================

CRC远没有网上所说那么简单。

  首先我们有一个数据流，也就是你需要校验的数据，可以是N BIT，一般我们常用的4，8，16，32，128 BIT，这里我取几个8的倍数，是因为我们的硬件以二进制为基础，所以在存取数据比较容易，无须充填位数来满足寄存器的要求。你用13，17，29 BIT也可以。

  有一点你要记住的是，你选用几个BIT，那么在CRC编码就需要移位几次，8就是移位8次，13就是移位13次，128就是移位128次。

我们看看目前为止的CRC的标准或者行规有：
CRC8  = X8+X5+X4+1
CRC16 = X16+X15+X5+1
CRC12 = X12+X11+X3+X2+1
CRC32 = X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1

CRC-CCITT=X16+X12+X5+1

需要说明的：CRC后所带的数字就是CRC的位数，它与你的数据流是无关的。

CRC8，8位CRC校验。
CRC16，16位CRC校验。
CRC12，12位CRC校验。
CRC32，32位CRC校验。
CRC-CCITT，16位CRC校验。

我们看到5个多项式，它的意义其实就是给出一个与数据流进行异或运算的初始值，
当然你可以更改这个值。比如：

CRC8  = X8+X5+X4+1 》》》 CRC8  = X7+X3+X2+1

CRC16 = X16+X15+X5+1 》》》CRC16 = X15+X5+1

只要你做出的东西是相互连接，不用与其他的机器对接，推荐保密部门使用该方法。
如果修改上述的多项式，那么别人在分析你传送来的数据时，该全部是错码。

补一下课：
异或操作：
              RESULT
  0    0       0
  0    1       1
  1    0       1
  1    1       0

只看该作者 · 2007-4-5 23:38

CRC8 = X8+X5+X4+1

X8 表示第7位需要异或运算
X5 表示第4位需要异或运算
X4 表示第3位需要异或运算
1 表示第0位需要异或运算

如图，首先将CRC所有位清0。
假设我们的数据流为8位，数据流 == 00000011，并且从0位（LSB）开始送入CRC中，则有：

1）1000 1 100
1）1100 1 010
0）0110 0 101
0）1011 1 110
0）0101 1 111
0）1010 0 011
0）1101 1 101
0）1110 0 010

我们看看这个数：
1110 0010 == 0XE2 --- 结果是错的
0100 0111 == 0X47 --- CRC

只看该作者 · 2007-4-5 23:44

CRC16 = X16+X15+X5+1

X16 表示第15位需要异或运算
X15 表示第14位需要异或运算
X5 表示第4位需要异或运算
1 表示第0位需要异或运算

如图，首先将CRC所有位清0。
假设我们的数据流为8位，数据流 == 00000011，并且从0位（LSB）开始送入CRC中，则有：

1）10000 1000000000 1
1）01000 0100000000 0
0）00100 0010000000 0
0）00010 0001000000 0
0）00001 0000100000 0
0）00000 1000010000 0
0）00000 0100001000 0
0）00000 0010000100 0

CRC
0001 0000 1000 0000 == 0X1080

只看该作者 · 2007-4-5 23:44

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

以上述两个例子，自行推倒。

2万 · 2007-4-5 23:46

为什么和十进制、十六进制的除法算出来的模是不同的呢？？？

呵呵，上次别人发贴偶仔细一算，确实越算越糊涂了:-)

只看该作者 · 2007-4-5 23:48

CRC-CCITT=X16+X12+X5+1

比较特殊，所以再说说

CRC-CCITT 不同于 CRC-16在于它是个反相的CRC-16，所谓反相的意义指从第7位（MSB）开始移入CRC移位寄存器，

如图，首先将CRC所有位清0。
假设我们的数据流为8位，数据流 == 00000011，并且从7位（MSB）开始送入CRC中，则有：

0）00000  0000000  0000
0）00000  0000000  0000
0）00000  0000000  0000
0）00000  0000000  0000
0）00000  0000000  0000
0）00000  0000000  0000
1）10000  1000000  1000
1）11000  1100000  1100

CRC
0011 0000 0110 0011 == 0X3063

只看该作者 · 2007-4-5 23:48

请教高手：

全字节和半字节查表CRC的工作原理的不同在那里？谢谢！

只看该作者 · 2007-4-5 23:57

   我觉得没有任何问题哦！

   十进制数除数/ 16 == 十进制的商，将除数和商换成二进制，比对结果

   你要问的是不是左右移位的问题？

   右移1位的结果：11001010 》》1100101，原来的数/2

   左移1位的结果：11001010 》》110010100，原来的数*2

只看该作者 · 2007-4-6 00:02

    如果原来的数不能被2整除的话，好像不能适用移位的方法。

    如果涉及好二进制小数的话，有一个误区：

    （二进制数）11.11
    （十进制数）3.75
     这里0.1 == 0.5 ，0.01 == 0.25

     希望对你有帮助！我下了，明天见

2万 · 2007-4-6 00:13

比如按这个多项式：CRC-CCITT=X16+X12+X5+1
0x0001 的CRC＝0x1021
0x0003 的CRC＝0x3063

用什么杨的数学公式能得到这个值呢？？？

2万 · 2007-4-6 08:30

只看该作者 · 2007-4-6 09:30

unsigned int cal_crc(unsigned char *pt, unsigned char len)
{
    unsigned char i;
    unsigned int crc=0;
    unsigned char *ptr = pt;
    while(len--!=0)
    {
        for(i=0x80; i!=0; i/=2)
        {
            if((crc&0x8000)!=0)
            {
                crc*=2; crc^=0x1021;
            } /* 余式CRC 乘以2 再求CRC */
            else
                crc*=2;
            if((*ptr&i)!=0)
                crc^=0x1021; /* 再加上本位的CRC */
        }
        ptr++;
    }

    return(crc);
}

只看该作者 · 2007-4-7 11:44

让我研究研究答复你~~~~~~~~~

你的签名太大了,严重影响视觉效果!

只看该作者 · 2007-4-7 13:35

相关链接:https://bbs.21ic.com/upfiles/img/20074/20074713353824.pdf

2万 · 2007-4-7 14:24

汽车电子失踪了~~~

给我的网站被黑了~~~赶紧备份,因为我自己都没保留~~~
还好,这黑客还有良心~~~

这个程序是我研究CRC多年的总结笔记吧,实际内含加密和解密.
把CRC应用引伸了一节~~~
"计算"实际是加密过程.
"还原"实际是解密过程.

相关链接:http://www.hotpower.net.cn/UploadFiles/200612222511409.htm

2万 · 2007-4-7 14:46

2万 · 2007-4-8 23:34

对于但字节，CRC结果不是模，而是0x11021－左移16位的模

既：

CRC(n)=0x11021-(n<<16)%0x11021;
或
CRC(n)=0x11021-(n*0x10000)%0x11021;

这样，对于有乘加指令的DSP就可以不用查表而一步算出答案了

对于多字节的结果不对，还得继续研究下合并规律的简化...

2万 · 2007-4-8 23:40

呵呵

2万 · 2007-4-9 00:11

研究这个主要是因为看到（找到）的程序大家不管是用什么CPU：电脑、单片机、DSP，写的CRC程序都是用的循环移位异或的方式，也就是模2除法。

这个模2除法是针对没有除法器的CPU搞出来的用加减异或指令完成的除法算法啊，只有没有除法器的CPU才会这样算啊！那个效率有多么的低是可想而知的！
而我们实际使用的CPU大多数是有乘法器和除法器的，就算没有用查表也会快很多很多倍，而我看到所有的CRC算法大家都是循环移位异或的方式来算，甚至于电脑上的程序都这样算！
这。。。真是食而不化了...

呵呵，偶以后看到这样写CRC程序的一律BS之!
:-)

资料上说CRC的算法是：
16 位的CRC 码产生的规则是先将要发送的二进制序列数左移16 位（既乘以216 ）后，
再除以一个多项式，最后所得到的余数既是CRC 码，如式（2-1）式所示，其中B(X)表
示n 位的二进制序列数，G(X)为多项式，Q(X)为整数，R(X)是余数（既CRC 码）。

     (X)·2^16               R(X)
    ----------   =  Q(X) + ----------
       G(X)                  G(X)

那CRC的结果应该就是：

CRC(X) = R(X) = ((X)<<16) % G(X);

而实际测试的结果却是：
CRC(X) = R(X) = G(X) － ((X)<<16) % G(X);

应该是：R(X)是余数（CRC 码为 G(X)－R(X)，这样整个位串再合并上CRC 码就刚好能被多项式G(X)整除）。

对于CRC-CCITT的多项式：X16+X12+X5+1
就是
CRC(n)=0x11021-(n<<16)%0x11021;
或
CRC(n)=0x11021-(n*0x10000)%0x11021;

唉，CRC的资料只说“R(X)是余数（既CRC 码）”，自己没去仔细看E文资料，就信以为真了，结果全然不对啊，最好竟然去由运算结果反推算法，真是晕死了...

:-(

2万 · 2007-4-9 08:35

[转贴]悟空，CRC原来是这么回事！

相关帖子

可靠棵

AAA

DDDD

呵呵，楼上先给我讲讲用^移位8(16)次模2除法是怎么回事好吗

DDDDD

JJJ

别急5楼，我来了

see you later

不是的，比如0x0001的CRC是1021,但用计算器什么算都不是这个数

呵呵，LZ只是负责转贴

如下,

dddd

这里讲的很清楚,不清楚的可以看下高等代数

倒塌了~~~不会CRC算法,只知道结果~~~~

楼主给的我真算不出来,只会算xwj给出的结果

研究出来了：

PS: hotpower的程序可以简化了，不用一步步移位了

呵呵，都怪资料不准确,害我去由运算结果反推算法,真是晕死

你继续研究，俺来吃白食……

涓涓之细流

以坛为家

终身成就奖章

坚毅之洋流

技术领袖奖章

十世金身

精华达人奖章

湍急之河流

技术奇才奖章

倒塌了~不会CRC算法,只知道结果~~