网站备案 异地,可以做视频的网站,wap网站和app开发,wordpress 4 导航CRC校验(循环冗余校验)是数据通讯中最常采用的校验方式。在嵌入式软件开发中#xff0c;经常要用到CRC 算法对各种数据进行校验。因此#xff0c;掌握基本的CRC算法应是嵌入式程序员的基本技能。可是#xff0c;我认识的嵌入式程序员中能真正掌握CRC算法的人却很少#xff…CRC校验(循环冗余校验)是数据通讯中最常采用的校验方式。在嵌入式软件开发中经常要用到CRC 算法对各种数据进行校验。因此掌握基本的CRC算法应是嵌入式程序员的基本技能。可是我认识的嵌入式程序员中能真正掌握CRC算法的人却很少平常在项目中见到的CRC的代码多数都是那种效率非常低下的实现方式。从奇偶校验说起所谓通讯过程的校验是指在通讯数据后加上一些附加信息通过这些附加信息来判断接收到的数据是否和发送出的数据相同。比如说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、1CRC 算法和这个过程有点类似不过采用的不是上面例子中的通常的这种除法。在CRC算法中将二进制数据流作为多项式的系数然后进行的是多项式的乘除法。还是举个例子吧。比如说我们有两个二进制数分别为1101 和1011。1101 与如下的多项式相联系1x31x20x11x0x3x2x01011与如下的多项式相联系1x30x21x11x0x3x1x0两个多项式的乘法(x3x2x0)(x3x1x0)x6x5x4x3x3x3x2x1x0得到结果后合并同类项时采用模2运算。也就是说乘除法采用正常的多项式乘除法而加减法都采用模2运算。所谓模2运算就是结果除以2后取余数。比如3 mod 2 1。因此上面最终得到的多项式为x6x5x4x3x2x1x0对应的二进制数:111111加减法采用模2运算后其实就成了一种运算了就是我们通常所说的异或运算0000111011100-001-010-111-10上面说了半天多项式其实就算是不引入多项式乘除法的概念也可以说明这些运算的特殊之处。只不过几乎所有讲解 CRC 算法的文献中都会提到多项式因此这里也简单的写了一点基本的概念。不过总用这种多项式表示也很罗嗦下面的讲解中将尽量采用更简洁的写法。除法运算与上面给出的乘法概念类似还是遇到加减的地方都用异或运算来代替。下面是一个例子要传输的数据为1101011011除数设为10011在计算前先将原始数据后面填上4个011010110110000之所以要补0后面再做解释。从这个例子可以看出采用了模2的加减法后不需要考虑借位的问题所以除法变简单了。最后得到的余数就是CRC 校验字。为了进行CRC运算也就是这种特殊的除法运算必须要指定个被除数在CRC算法中这个被除数有一个专有名称叫做“生成多项式”。生成多项式的选取是个很有难度的问题如果选的不好那么检出错误的概率就会低很多。好在这个问题已经被专家们研究了很长一段时间了对于我们这些使用者来说只要把现成的成果拿来用就行了。最常用的几种生成多项式如下CRC8X8X5X4X0CRC-CCITTX16X12X5X0CRC16X16X15X2X0CRC12X12X11X3X2X0CRC32X32X26X23X22X16X12X11X10X8X7X5X4X2X1X0有一点要特别注意文献中提到的生成多项式经常会说到多项式的位宽(Width简记为W)这个位宽不是多项式对应的二进制数的位数而是位数减1。比如CRC8中用到的位宽为8的生成多项式其实对应得二进制数有九位100110001。另外一点多项式表示和二进制表示都很繁琐交流起来不方便因此文献中多用16进制简写法来表示因为生成多项式的最高位肯定为1最高位的位置由位宽可知故在简记式中将最高的1统一去掉了如CRC32的生成多项式简记为04C11DB7实际上表示的是104C11DB7。当然这样简记除了方便外在编程计算时也有它的用处。对于上面的例子位宽为4(W4)按照CRC算法的要求计算前要在原始数据后填上W个0也就是4个0。位宽W1的生成多项式(CRC1)有两种分别是X1和X1X0读者可以自己证明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寄存器的值在与这个值进行一下异或操作作为最后的校验值。加入这些变形后常见的算法描述形式就成了这个样子了(1) 设置CRC寄存器并给其赋值为“余数初始值”。(2) 将数据的第一个8-bit字符与CRC寄存器进行异或并把结果存入CRC寄存器。(3) CRC寄存器向右移一位MSB补零移出并检查LSB。(4) 如果LSB为0重复第三步若LSB为1CRC寄存器与0x31相异或。(5) 重复第3与第4步直到8次移位全部完成。此时一个8-bit数据处理完毕。(6) 重复第2至第5步直到所有数据全部处理完成。(7) 最终CRC寄存器的内容与“结果异或值”进行或非操作后即为CRC值。而网上的代码.h.c文件很多可以试一下。
