精华内容
下载资源
问答
  • CRC算法

    2016-08-17 12:56:00
    可是,我认识的嵌入式程序员中能真正掌握CRC算法的人却很少,平常在项目中见到的CRC的代码多数都是那种效率非常低下的实现方式。 其实,在网上有一篇介绍CRC 算法的非常好的文章,作者是Ross William

    前言

    CRC校验(循环冗余校验)是数据通讯中最常采用的校验方式。在嵌入式软件开发中,经常要用到CRC 算法对各种数据进行校验。因此,掌握基本的CRC算法应是嵌入式程序员的基本技能。可是,我认识的嵌入式程序员中能真正掌握CRC算法的人却很少,平常在项目中见到的CRC的代码多数都是那种效率非常低下的实现方式。

    其实,在网上有一篇介绍CRC 算法的非常好的文章,作者是Ross Williams,题目叫:“A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS”。我常将这篇文章推荐给向我询问CRC算法的朋友,但不少朋友向我抱怨原文太长了,而且是英文的。希望我能写篇短点的文章,因此就有了本文。不过,我的水平比不了Ross Williams,我的文章肯定也没Ross Williams的写的好。因此,阅读英文没有障碍的朋友还是去读Ross Williams的原文吧。

    本文的读者群设定为软件开发人员,尤其是从事嵌入式软件开发的程序员,而不是专业从事数学或通讯领域研究的学者(我也没有这个水平写的这么高深)。因此,本文的目标是介绍CRC算法的基本原理和实现方式,用到的数学尽量控制在高中生可以理解的深度。

    另外,鉴于大多数嵌入式程序员都是半路出家转行过来的,不少人只会C语言。因此,文中的示例代码全部采用C语言来实现。作为一篇入门短文,文中给出的代码更注重于示范性,尽可能的保持易读性。因此,文中的代码并不追求最高效的实现,但对于一般的应用却也足够快速了。

    从奇偶校验说起

    所谓通讯过程的校验是指在通讯数据后加上一些附加信息,通过这些附加信息来判断接收到的数据是否和发送出的数据相同。比如说RS232串行通讯可以设置奇偶校验位,所谓奇偶校验就是在发送的每一个字节后都加上一位,使得每个字节中1的个数为奇数个或偶数个。比如我们要发送的字节是0x1a,二进制表示为0001 1010。

    采用奇校验,则在数据后补上个0,数据变为0001 1010 0,数据中1的个数为奇数个(3个)

    采用偶校验,则在数据后补上个1,数据变为0001 1010 1,数据中1的个数为偶数个(4个)

    接收方通过计算数据中1个数是否满足奇偶性来确定数据是否有错。

    奇偶校验的缺点也很明显,首先,它对错误的检测概率大约只有50%。也就是只有一半的错误它能够检测出来。另外,每传输一个字节都要附加一位校验位,对传输效率的影响很大。因此,在高速数据通讯中很少采用奇偶校验。奇偶校验优点也很明显,它很简单,因此可以用硬件来实现,这样可以减少软件的负担。因此,奇偶校验也被广泛的应用着。

    奇偶校验就先介绍到这来,之所以从奇偶校验说起,是因为这种校验方式最简单,而且后面将会知道奇偶校验其实就是CRC 校验的一种(CRC-1)。

    累加和校验

    另一种常见的校验方式是累加和校验。所谓累加和校验实现方式有很多种,最常用的一种是在一次通讯数据包的最后加入一个字节的校验数据。这个字节内容为前面数据包中全部数据的忽略进位的按字节累加和。比如下面的例子:

    我们要传输的信息为: 6、23、4

    加上校验和后的数据包:6、23、4、33

    这里 33 为前三个字节的校验和。接收方收到全部数据后对前三个数据进行同样的累加计算,如果累加和与最后一个字节相同的话就认为传输的数据没有错误。

    累加和校验由于实现起来非常简单,也被广泛的采用。但是这种校验方式的检错能力也比较一般,对于单字节的校验和大概有1/256 的概率将原本是错误的通讯数据误判为正确数据。之所以这里介绍这种校验,是因为CRC校验在传输数据的形式上与累加和校验是相同的,都可以表示为:通讯数据 校验字节(也可能是多个字节)

    初识 CRC 算法

    CRC 算法的基本思想是将传输的数据当做一个位数很长的数。将这个数除以另一个数。得到的余数作为校验数据附加到原数据后面。还以上面例子中的数据为例:

    6、23、4 可以看做一个2进制数: 0000011000010111 00000010

    假如被除数选9,二进制表示为:1001

    则除法运算可以表示为:

    可以看到,最后的余数为1。如果我们将这个余数作为校验和的话,传输的数据则是:6、23、4、1

    CRC 算法和这个过程有点类似,不过采用的不是上面例子中的通常的这种除法。在CRC算法中,将二进制数据流作为多项式的系数,然后进行的是多项式的乘除法。还是举个例子吧。

    比如说我们有两个二进制数,分别为:1101 和1011。

    1101 与如下的多项式相联系:1x3+1x2+0x1+1x0=x3+x2+x0

    1011与如下的多项式相联系:1x3+0x2+1x1+1x0=x3+x1+x0

    两个多项式的乘法:(x3+x2+x0)(x3+x1+x0)=x6+x5+x4+x3+x3+x3+x2+x1+x0

    得到结果后,合并同类项时采用模2运算。也就是说乘除法采用正常的多项式乘除法,而加减法都采用模2运算。所谓模2运算就是结果除以2后取余数。比如3 mod 2 = 1。因此,上面最终得到的多项式为:x6+x5+x4+x3+x2+x1+x0,对应的二进制数:111111

    加减法采用模2运算后其实就成了一种运算了,就是我们通常所说的异或运算:

    0+0=0

    0+1=1

    1+0=1

    1+1=0

    0-0=0

    1-0=1

    0-1=1

    1-1=0

    上面说了半天多项式,其实就算是不引入多项式乘除法的概念也可以说明这些运算的特殊之处。只不过几乎所有讲解 CRC 算法的文献中都会提到多项式,因此这里也简单的写了一点基本的概念。不过总用这种多项式表示也很罗嗦,下面的讲解中将尽量采用更简洁的写法。

    除法运算与上面给出的乘法概念类似,还是遇到加减的地方都用异或运算来代替。下面是一个例子:

    要传输的数据为:1101011011

    除数设为:10011

    在计算前先将原始数据后面填上4个0:11010110110000,之所以要补0,后面再做解释。

    从这个例子可以看出,采用了模2的加减法后,不需要考虑借位的问题,所以除法变简单了。最后得到的余数就是CRC 校验字。为了进行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

    有一点要特别注意,文献中提到的生成多项式经常会说到多项式的位宽(Width,简记为W),这个位宽不是多项式对应的二进制数的位数,而是位数减1。比如CRC8中用到的位宽为8的生成多项式,其实对应得二进制数有九位:100110001。另外一点,多项式表示和二进制表示都很繁琐,交流起来不方便,因此,文献中多用16进制简写法来表示,因为生成多项式的最高位肯定为1,最高位的位置由位宽可知,故在简记式中,将最高的1统一去掉了,如CRC32的生成多项式简记为04C11DB7实际上表示的是104C11DB7。当然,这样简记除了方便外,在编程计算时也有它的用处。

    对于上面的例子,位宽为4(W=4),按照CRC算法的要求,计算前要在原始数据后填上W个0,也就是4个0。

    位宽W=1的生成多项式(CRC1)有两种,分别是X1和X1+X0,读者可以自己证明10 对应的就是奇偶校验中的奇校验,而11对应则是偶校验。因此,写到这里我们知道了奇偶校验其实就是CRC校验的一种特例,这也是我要以奇偶校验作为开篇介绍的原因了。

    CRC算法的编程实现

    说了这么多总算到了核心部分了。从前面的介绍我们知道CRC校验核心就是实现无借位的除法运算。下面还是通过一个例子来说明如何实现CRC校验。

    假设我们的生成多项式为:100110001(简记为0x31),也就是CRC-8

    则计算步骤如下:

    (1)      将CRC寄存器(8-bits,比生成多项式少1bit)赋初值0

    (2)      在待传输信息流后面加入8个0

    (3)      While (数据未处理完)

    (4)      Begin

    (5)          If (CRC寄存器首位是1)

    (6)              reg = reg XOR 0x31

    (7)          CRC寄存器左移一位,读入一个新的数据于CRC寄存器的0 bit的位置。

    (8)      End

    (9)      CRC寄存器就是我们所要求的余数。

     

    实际上,真正的CRC 计算通常与上面描述的还有些出入。这是因为这种最基本的CRC除法有个很明显的缺陷,就是数据流的开头添加一些0并不影响最后校验字的结果。这个问题很让人恼火啊,因此真正应用的CRC 算法基本都在原始的CRC算法的基础上做了些小的改动。

    所谓的改动,也就是增加了两个概念,第一个是“余数初始值”,第二个是“结果异或值”。

    所谓的“余数初始值”就是在计算CRC值的开始,给CRC寄存器一个初始值。“结果异或值”是在其余计算完成后将CRC寄存器的值在与这个值进行一下异或操作作为最后的校验值。

    常见的三种CRC 标准用到个各个参数如下表。

     

    CCITT

    CRC16

    CRC32

    校验和位宽W

    16

    16

    32

    生成多项式

    x16+x12+x5+1

    x16+x15+x2+1

    x32+x26+x23+x22+x16+

    x12+x11+x10+x8+x7+x5+

    x4+x2+x1+1

    除数(多项式)

    0x1021

    0x8005

    0x04C11DB7

    余数初始值

    0xFFFF

    0x0000

    0xFFFFFFFF

    结果异或值

    0x0000

    0x0000

    0xFFFFFFFF

     

    加入这些变形后,常见的算法描述形式就成了这个样子了:

    (1)      设置CRC寄存器,并给其赋值为“余数初始值”。

    (2)      将数据的第一个8-bit字符与CRC寄存器进行异或,并把结果存入CRC寄存器。

    (3)      CRC寄存器向右移一位,MSB补零,移出并检查LSB。

    (4)      如果LSB为0,重复第三步;若LSB为1,CRC寄存器与0x31相异或。

    (5)      重复第3与第4步直到8次移位全部完成。此时一个8-bit数据处理完毕。

    (6)      重复第2至第5步直到所有数据全部处理完成。

    (7)      最终CRC寄存器的内容与“结果异或值”进行或非操作后即为CRC值。

     

    示例性的C代码如下所示,因为效率很低,项目中如对计算时间有要求应该避免采用这样的代码。不过这个代码已经比网上常见的计算代码要好了,因为这个代码有一个crc的参数,可以将上次计算的crc结果传入函数中作为这次计算的初始值,这对大数据块的CRC计算是很有用的,不需要一次将所有数据读入内存,而是读一部分算一次,全读完后就计算完了。这对内存受限系统还是很有用的。

    [cpp] view plain copy
     在CODE上查看代码片派生到我的代码片
    1. #define POLY        0x1021  
    2. /** 
    3.  * Calculating CRC-16 in 'C' 
    4.  * @para addr, start of data 
    5.  * @para num, length of data 
    6.  * @para crc, incoming CRC 
    7.  */  
    8. uint16_t crc16(unsigned char *addr, int num, uint16_t crc)  
    9. {  
    10.     int i;  
    11.     for (; num > 0; num--)              /* Step through bytes in memory */  
    12.     {  
    13.         crc = crc ^ (*addr++ << 8);     /* Fetch byte from memory, XOR into CRC top byte*/  
    14.         for (i = 0; i < 8; i++)             /* Prepare to rotate 8 bits */  
    15.         {  
    16.             if (crc & 0x8000)            /* b15 is set... */  
    17.                 crc = (crc << 1) ^ POLY;    /* rotate and XOR with polynomic */  
    18.             else                          /* b15 is clear... */  
    19.                 crc <<= 1;                  /* just rotate */  
    20.         }                             /* Loop for 8 bits */  
    21.         crc &= 0xFFFF;                  /* Ensure CRC remains 16-bit value */  
    22.     }                               /* Loop until num=0 */  
    23.     return(crc);                    /* Return updated CRC */  
    24. }  

    上面的代码是我从http://mdfs.net/Info/Comp/Comms/CRC16.htm找到的,不过原始代码有错误,我做了些小的修改。

    下面对这个函数给出个例子片段代码:

    [cpp] view plain copy
     在CODE上查看代码片派生到我的代码片
    1. unsigned char data1[] = {'1''2''3''4''5''6''7''8''9'};  
    2. unsigned char data2[] = {'5''6''7''8''9'};  
    3. unsigned short c1, c2;  
    4. c1 = crc16(data1, 9, 0xffff);  
    5. c2 = crc16(data1, 4, 0xffff);  
    6. c2 = crc16(data2, 5, c2);  
    7. printf("%04x\n", c1);  
    8. printf("%04x\n", c2);  

    读者可以验算,c1、c2 的结果都为 29b1。上面代码中crc 的初始值之所以为0xffff,是因为CCITT标准要求的除数初始值就是0xffff。 

    上面的算法对数据流逐位进行计算,效率很低。实际上仔细分析CRC计算的数学性质后我们可以多位多位计算,最常用的是一种按字节查表的快速算法。该算法基于这样一个事实:计算本字节后的CRC码,等于上一字节余式CRC码的低8位左移8位,加上上一字节CRC右移 8位和本字节之和后所求得的CRC码。如果我们把8位二进制序列数的CRC(共256个)全部计算出来,放在一个表里,编码时只要从表中查找对应的值进行处理即可。

    按照这个方法,可以有如下的代码(这个代码也不是我写的,是我在Micbael Barr的书“Programming Embedded Systems in C and C++” 中找到的,同样,我做了点小小的改动。):

    [cpp] view plain copy
     在CODE上查看代码片派生到我的代码片
    1. /* 
    2. crc.h 
    3. */  
    4.   
    5. #ifndef CRC_H_INCLUDED  
    6. #define CRC_H_INCLUDED  
    7.   
    8. /* 
    9. * The CRC parameters. Currently configured for CCITT. 
    10. * Simply modify these to switch to another CRC Standard. 
    11. */  
    12. /* 
    13. #define POLYNOMIAL          0x8005 
    14. #define INITIAL_REMAINDER   0x0000 
    15. #define FINAL_XOR_VALUE     0x0000 
    16. */  
    17. #define POLYNOMIAL          0x1021  
    18. #define INITIAL_REMAINDER   0xFFFF  
    19. #define FINAL_XOR_VALUE     0x0000  
    20.   
    21. /* 
    22. #define POLYNOMIAL          0x1021 
    23. #define POLYNOMIAL          0xA001 
    24. #define INITIAL_REMAINDER   0xFFFF 
    25. #define FINAL_XOR_VALUE     0x0000 
    26. */  
    27.   
    28. /* 
    29. * The width of the CRC calculation and result. 
    30. * Modify the typedef for an 8 or 32-bit CRC standard. 
    31. */  
    32. typedef unsigned short width_t;  
    33. #define WIDTH (8 * sizeof(width_t))  
    34. #define TOPBIT (1 << (WIDTH - 1))  
    35.   
    36. /** 
    37.  * Initialize the CRC lookup table. 
    38.  * This table is used by crcCompute() to make CRC computation faster. 
    39.  */  
    40. void crcInit(void);  
    41.   
    42. /** 
    43.  * Compute the CRC checksum of a binary message block. 
    44.  * @para message, 用来计算的数据 
    45.  * @para nBytes, 数据的长度 
    46.  * @note This function expects that crcInit() has been called 
    47.  *       first to initialize the CRC lookup table. 
    48.  */  
    49. width_t crcCompute(unsigned char * message, unsigned int nBytes);  
    50.   
    51. #endif // CRC_H_INCLUDED  

     

    [cpp] view plain copy
     在CODE上查看代码片派生到我的代码片
    1. /* 
    2.  *crc.c 
    3.  */  
    4.   
    5. #include "crc.h"  
    6. /* 
    7. * An array containing the pre-computed intermediate result for each 
    8. * possible byte of input. This is used to speed up the computation. 
    9. */  
    10. static width_t crcTable[256];  
    11.   
    12. /** 
    13.  * Initialize the CRC lookup table. 
    14.  * This table is used by crcCompute() to make CRC computation faster. 
    15.  */  
    16. void crcInit(void)  
    17. {  
    18.     width_t remainder;  
    19.     width_t dividend;  
    20.     int bit;  
    21.     /* Perform binary long division, a bit at a time. */  
    22.     for(dividend = 0; dividend < 256; dividend++)  
    23.     {  
    24.         /* Initialize the remainder.  */  
    25.         remainder = dividend << (WIDTH - 8);  
    26.         /* Shift and XOR with the polynomial.   */  
    27.         for(bit = 0; bit < 8; bit++)  
    28.         {  
    29.             /* Try to divide the current data bit.  */  
    30.             if(remainder & TOPBIT)  
    31.             {  
    32.                 remainder = (remainder << 1) ^ POLYNOMIAL;  
    33.             }  
    34.             else  
    35.             {  
    36.                 remainder = remainder << 1;  
    37.             }  
    38.         }  
    39.         /* Save the result in the table. */  
    40.         crcTable[dividend] = remainder;  
    41.     }  
    42. /* crcInit() */  
    43.   
    44. /** 
    45.  * Compute the CRC checksum of a binary message block. 
    46.  * @para message, 用来计算的数据 
    47.  * @para nBytes, 数据的长度 
    48.  * @note This function expects that crcInit() has been called 
    49.  *       first to initialize the CRC lookup table. 
    50.  */  
    51. width_t crcCompute(unsigned char * message, unsigned int nBytes)  
    52. {  
    53.     unsigned int offset;  
    54.     unsigned char byte;  
    55.     width_t remainder = INITIAL_REMAINDER;  
    56.     /* Divide the message by the polynomial, a byte at a time. */  
    57.     for( offset = 0; offset < nBytes; offset++)  
    58.     {  
    59.         byte = (remainder >> (WIDTH - 8)) ^ message[offset];  
    60.         remainder = crcTable[byte] ^ (remainder << 8);  
    61.     }  
    62.     /* The final remainder is the CRC result. */  
    63.     return (remainder ^ FINAL_XOR_VALUE);  
    64. /* crcCompute() */  

     

    上面代码中crcInit() 函数用来计算crcTable,因此在调用 crcCompute 前必须先调用 crcInit()。不过,对于嵌入式系统,RAM是很紧张的,最好将 crcTable 提前算好,作为常量数据存到程序存储区而不占用RAM空间。CRC 计算实际上还有很多内容可以介绍,不过对于一般的程序员来说,知道这些也就差不多了。余下的部分以后有时间了我再写篇文章来介绍吧。

     

     

    展开全文
  • CRC算法原理

    2015-10-26 08:55:40
    CRC算法原理 包含详细的CRC算法原理讲解,对于做通信理解CRC算法有很大的帮助!
  • crc 算法

    2010-07-31 01:11:00
    标准 根据应用环境与习惯的不同,CRC又可分为以下几种标准: ①CRC-12码; ②CRC-16码; ③CRC-CCITT码; ④CRC-32码。 CRC-12码通常用来传送6-bit字符串。 CRC-16及CRC-CCITT码则是用来传送8-bit字符串,其中CRC-...

    标准
      根据应用环境与习惯的不同,CRC又可分为以下几种标准:
      ①CRC-12码;
      ②CRC-16码;
      ③CRC-CCITT码;
      ④CRC-32码。
      CRC-12码通常用来传送6-bit字符串。
      CRC-16及CRC-CCITT码则是用来传送8-bit字符串,其中CRC-16为美国采用,而CRC-CCITT为欧洲国家所采用。
      CRC-32码大都被采用在一种称为Point-to-Point的同步传输中。


    生成过程
      下面以最常用的CRC-16为例来说明其生成过程。
      CRC-16码由两个字节构成,在开始时CRC寄存器的每一位都预置为1,然后把CRC寄存器与8-bit的数据进行异或(异或:二进制运算 相同为0,不同为1;0^0=0;0^1=1;1^0=1;1^1=0),
      之后对CRC寄存器从高到低进行移位,在最高位(MSB)的位置补零,而最低位(LSB,移位后已经被移出CRC寄存器)如果为1,则把寄存器与预定义的多项式码进行异或,否则如果LSB为零,则无需进行异或。重复上述的由高至低的移位8次,第一个8-bit数据处理完毕,用此时CRC寄存器的值与下一个8-bit数据异或并进行如前一个数据似的8次移位。所有的字符处理完成后CRC寄存器内的值即为最终的CRC值。

    计算过程
      1.设置CRC寄存器,并给其赋值FFFF(hex)。
      2.将数据的第一个8-bit字符与16位CRC寄存器的低8位进行异或,并把结果存入CRC寄存器。
      3.CRC寄存器向右移一位,MSB补零,移出并检查LSB。
      4.如果LSB为0,重复第三步;若LSB为1,CRC寄存器与多项式码相异或。
      5.重复第3与第4步直到8次移位全部完成。此时一个8-bit数据处理完毕。
      6.重复第2至第5步直到所有数据全部处理完成。
      7.最终CRC寄存器的内容即为CRC值。
      常用的CRC循环冗余校验标准多项式如下:
      CRC(12位) =X12+X11+X3+X2+X+1
      CRC(16位) = X16+X15+X2+1
      CRC(CCITT) = X16+X12 +X5+1
      CRC(32位) = X32+X26+X23+X16+X12+X11+X10+ X8+X7+X5+X4+X2+X+1
      以CRC(16位)多项式为例,其对应校验二进制位列为1 1000 0000 0000 0101。
      注意:这儿列出的标准校验多项式都含有(X+1)的多项式因子;各多项式的系数均为二进制数,所涉及的四则运算仍遵循对二取模的运算规则。
      (注:对二取模的四则运算指参与运算的两个二进制数各位之间凡涉及加减运算时均进行XOR异或运算,即:1 XOR 1=0,0 XOR 0=0,1 XOR 0=1,0 XOR 1=1,即相同为0,不同为1)

     

    CRC检验  CRC校验实用程序库 在数据存储和数据通讯领域,为了保证数据的正确,就不得不采用检错的手段。在诸多检错手段中,CRC是最著名的一种。CRC的全称是循环冗余校验,其特点是:检错能力极强,开销小,易于用编码器及检测电路实现。从其检错能力来看,它所不能发现的错误的几率仅为0.0047%以下。从性能上和开销上考虑,均远远优于奇偶校验及算术和校验等方式。因而,在数据存储和数据通讯领域,CRC无处不在:著名的通讯协议X.25的FCS(帧检错序列)采用的是CRC-CCITT,WinRAR

      、NERO、ARJ、LHA等压缩工具软件采用的是CRC32,磁盘驱动器的读写采用了CRC16,通用的图像存储格式GIF、TIFF等也都用CRC作为检错手段。

      CRC的本质是模-2除法的余数,采用的除数不同,CRC的类型也就不一样。通常,CRC的除数用生成多项式来表示。最常用的CRC码的生成多项式如表1所示。

      @@10A08800.GIF;表1.最常用的CRC码及生成多项式@@

      由于CRC在通讯和数据处理软件中经常采用,笔者在实际工作中对其算法进行了研究和比较,总结并编写了一个具有最高效率的CRC通用程序库。该程序采用查表法计算CRC,在速度上优于一般的直接模仿硬件的算法,可以应用于通讯和数据压缩程序。

    算法

      通常的CRC算法在计算一个数据段的CRC值时,其CRC值是由求解每个数值的CRC值的和对CRC寄存器的值反复更新而得到的。这样,求解CRC的速度较慢。通过对CRC算法的研究,我们发现:一个8位数据加到16位累加器中去,只有累加器的高8位或低8位与数据相作用,其结果仅有256种可能的组合值。因而,我们可以用查表法来代替反复的运算,这也同样适用于CRC32的计算。本文所提供的程序库中,函数crchware是一般的16位CRC的算法;mk-crctbl用以在内存中建立一个CRC数值表;crcupdate用以查表并更新CRC累加器的值;crcrevhware和crcrevupdate是反序算法的两个函数;BuildCRCTable、CalculateBlockCRC32和UpdateCharac

      terCRC32用于CRC32的计算。

      /* CRC.C——CRC程序库 */

      #define CRCCCITT 0x1021

      #define CCITT-REV 0x8408

      #define CRC16 0x8005

      #define CRC16-REV 0xA001

      #define CRC32-POLYNOMIAL 0xEDB88320L

      /* 以上为CRC除数的定义 */

      #define NIL 0

      #define crcupdate(d,a,t)*(a)=(*(a)<<8)^(t)[(*(a)>>8)^(d)];

      #define crcupdate16(d,a,t)*(a)=(*(a)>>8^(t)[(*(a)^(d))&0x00ff])

      /* 以上两个宏可以代替函数crcupdate和crcrevupdate */

      #include #include #include /* 函数crchware是传统的CRC算法,其返回值即CRC值 */ unsigned short crchware(data,genpoly,accum)

      unsigned short data;/* 输入的数据 */

      unsigned short genpoly;/* CRC除数 */

      unsigned short accum;/* CRC累加器值 */

      {

      static int i;

      data<<=8;

      for(i=8;i>0;i--)

      {

      if((data^accum)&0x8000)

      accum=(accum<<1)^genpoly;

      else

      accum<<=1;

      data<<=1;

      }

      return (accum);

      }

      /* 函数mk-crctbl利用函数crchware建立内存中的CRC数值表 */

      unsigned short *mk-crctbl(poly,crcfn);

      unsigned short poly;/* CRC除数--CRC生成多项式 */

      R>unsigned short (*crcfn)();/* 指向CRC函数(例如crchware)的指针 */

      {

      /* unsigned short */malloc(); */

      unsigned short *crctp;

      int i;

      if((crctp=(unsigned short*)malloc(256*sizeof(unsigned)))==0)

      return 0;

      for(i=0;i<256;i++)

      crctp=(*crcfn)(i,poly,0);

      return crctp;

      }

      /* 函数mk-crctbl的使用范例 */

      if((crctblp=mk-crctbl(CRCCCITT,crchware))==NIL)

      {

      puts("insuff memory for CRC lookup table.\n");

      return 1; */

      /* 函数crcupdate用以用查表法计算CRC值并更新CRC累加器值 */

      void crcupdate(data,accum,crctab)

      unsigned short data;/* 输入的数据 */

      unsigned short *accum;/* 指向CRC累加器的指针 */

      unsigned short *crctab;/* 指向内存中CRC表的指针 */

      {

      static short comb-val;

      comb-val=(*accum>>8)^data;

      *accum=(*accum<<8)^crctab[comb-val];

      }

      /* 函数crcrevhware是传统的CRC算法的反序算法,其返回值即CRC值 */

      unsigned short crcrevhware(data,genpoly,accum)

      unsigned short data;

      unsigned short genpoly;

      unsigned short accum;

      {

      static int i;

      data<<=1;

      for(i=8;i>0;i--)

      {

      data>>=1;

      if((data^accum)&0x0001)

      accum=(accum>>1)^genpoly;

      else

      accum>>=1;

      }

      return accum;

      }

      /* 函数crcrevupdate用以用反序查表法计算CRC值并更新CRC累加器值 */

      void crcrevupdate(data,accum,crcrevtab)

      unsigned short data;

      unsigned short *accum;

    CRC检验方法的工作原理

      循环冗余码CRC在发送端编码和接收端校验时,都可以利用事先约定的生成多项式G(X)来得到,k位要发送的信息位可对应一个(k-1)次多项式K(X),r位冗余位对应于一个(r-1)次多项式R(X),由k位信息位后面加上r位冗余位组成的n=k+r的码字则对应于一个(n-1)次多项式T(X)X×K(X)+R(X)。也即在发送端产生一个循环冗余码,附加在信息位后面一起发送到接收端。接收端的检验过程就是将接收到的码字多项式除以G(X),若余式为零则认为传输无差错;若余式不为零则传输有差错。

    转载于:https://www.cnblogs.com/zhihaowang/archive/2010/07/31/10128648.html

    展开全文
  • CRC算法和C语言实现CRC
  • CRC算法计算器

    2014-09-18 19:33:33
    CRC算法计算器,C#实现CRC8、CRC16、CRC32算法; 使用此工具需要安装Framework 4.0; 如果需要详细的代码实现,可以参考本人博客里的代码。
  • CRC算法代码

    2014-04-19 17:07:22
    总结CRC算法,内含源代码(8CRC和16CRC),已经测试过。
  • crc算法程序

    2012-07-25 17:59:41
    crc 算法程序
  • crc算法 路由算法

    2010-05-11 11:22:59
    计算机网络课程设计,包括crc算法 路由算法,以及实验报告。
  • CRC算法简介,带有MODBUS的CRC16查表法实现(Gx=A001),CDT的CRC8算法(Gx=07)
  • crc算法模拟

    2011-12-31 21:04:41
    crc算法模拟
  • CRC算法原理.doc

    2019-07-15 15:58:22
    CRC算法原理,详细介绍分析CRC原理以及计算方法,方便读者理解
  • CRC算法 (Java版)

    2019-10-12 01:24:15
    CRC算法,包含8/16/32/64位 CRC校验算法,Java语言实现。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,290
精华内容 1,316
关键字:

crc算法