采用奇校验,则在数据后补上个0,数据变为0001 1010 0,数据中1的个数为奇数个(3个) 采用偶校验,则在数据后补上个1,数据变为0001 1010 1,数据中1的个数为偶数个(4个) 另一种常见的校验方式是累加和校验。所谓累加和校验实现方式有很多种,最常用的一种是在一次通讯数据包的最后加入一个字节的校验数据。这个字节内容为前面数据包中全部数据的忽略进位的按字节累加和。比如下面的例子: 我们要传输的信息为: 6、23、4 加上校验和后的数据包:6、23、4、33 6、23、4 可以看做一个2进制数: 0000011000010111 00000010 假如被除数选9,二进制表示为:1001 则除法运算可以表示为: 可以看到,最后的余数为1。如果我们将这个余数作为校验和的话,传输的数据则是:6、23、4、1 两个多项式的乘法:(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运算后其实就成了一种运算了,就是我们通常所说的异或运算: 上面说了半天多项式,其实就算是不引入多项式乘除法的概念也可以说明这些运算的特殊之处。只不过几乎所有讲解 CRC 算法的文献中都会提到多项式,因此这里也简单的写了一点基本的概念。不过总用这种多项式表示也很罗嗦,下面的讲解中将尽量采用更简洁的写法。 除法运算与上面给出的乘法概念类似,还是遇到加减的地方都用异或运算来代替。下面是一个例子: 要传输的数据为:1101011011 除数设为:10011 在计算前先将原始数据后面填上4个0:11010110110000,之所以要补0,后面再做解释。 从这个例子可以看出,采用了模2的加减法后,不需要考虑借位的问题,所以除法变简单了。最后得到的余数就是CRC 校验字。为了进行CRC运算,也就是这种特殊的除法运算,必须要指定个被除数,在CRC算法中,这个被除数有一个专有名称叫做“生成多项式”。生成多项式的选取是个很有难度的问题,如果选的不好,那么检出错误的概率就会低很多。好在这个问题已经被专家们研究了很长一段时间了,对于我们这些使用者来说,只要把现成的成果拿来用就行了。 有一点要特别注意,文献中提到的生成多项式经常会说到多项式的位宽(Width,简记为W),这个位宽不是多项式对应的二进制数的位数,而是位数减1。比如CRC8中用到的位宽为8的生成多项式,其实对应得二进制数有九位: 位宽W=1的生成多项式(CRC1)有两种,分别是X1和X1+X0,读者可以自己证明10 对应的就是奇偶校验中的奇校验,而11对应则是偶校验。 说了这么多总算到了核心部分了。从前面的介绍我们知道CRC校验核心就是实现无借位的除法运算。下面还是通过一个例子来说明如何实现CRC校验。 则计算步骤如下: 实际上,真正的CRC 计算通常与上面描述的还有些出入。这是因为这种最基本的CRC除法有个很明显的缺陷,就是数据流的开头添加一些0并不影响最后校验字的结果。这个问题很让人恼火啊,因此真正应用的CRC 算法基本都在原始的CRC算法的基础上做了些小的改动。 所谓的改动,也就是增加了两个概念,第一个是“余数初始值”,第二个是“结果异或值”。 所谓的“余数初始值”就是在计算CRC值的开始,给CRC寄存器一个初始值。“结果异或值”是在其余计算完成后将CRC寄存器的值在与这个值进行一下异或操作作为最后的校验值。
上面的代码是我从http:///Info/Comp/Comms/CRC16.htm找到的,不过原始代码有错误,我做了些小的修改。 读者可以验算,c1、c2 的结果都为 29b1。上面代码中crc 的初始值之所以为0xffff,是因为CCITT标准要求的除数初始值就是0xffff。 上面的算法对数据流逐位进行计算,效率很低。实际上仔细分析CRC计算的数学性质后我们可以多位多位计算,最常用的是一种按字节查表的快速算法。该算法基于这样一个事实:计算本字节后的CRC码,等于上一字节余式CRC码的低8位左移8位,加上上一字节CRC右移 8位和本字节之和后所求得的CRC码。如果我们把8位二进制序列数的CRC(共256个)全部计算出来,放在一个表里,编码时只要从表中查找对应的值进行处理即可。 |
|
来自: Ricky_图书馆 > 《软件编程/MCU》