为了正常的体验网站,请在浏览器设置里面开启Javascript功能!

CRC校验算法

2017-09-01 11页 doc 27KB 91阅读

用户头像

is_496339

暂无简介

举报
CRC校验算法CRC校验算法 CRC(Cyclic Redundancy Check)循环冗余校验是常用的数据校验方法,讲CRC算法的文章很多,之所以还要写这篇,是想换一个方法介绍CRC算法,希望能让大家更容易理解CRC算法。 先说说什么是数据校验。数据在传输过程(比如通过网线在两台计算机 间传文件)中,由于传输信道的原因,可能会有误码现象(比如说发送数字5但接收方收到的却是6),如何发现误码呢?方法是发送额外的数据让接收方校 验是否正确,这就是数据校验。最容易想到的校验方法是和校验,就是将传送的 数据(按字节方式)加起来计算出数据的总...
CRC校验算法
CRC校验算法 CRC(Cyclic Redundancy Check)循环冗余校验是常用的数据校验方法,讲CRC算法的文章很多,之所以还要写这篇,是想换一个方法介绍CRC算法,希望能让大家更容易理解CRC算法。 先说说什么是数据校验。数据在传输过程(比如通过网线在两台计算机 间传文件)中,由于传输信道的原因,可能会有误码现象(比如说发送数字5但接收方收到的却是6),如何发现误码呢?方法是发送额外的数据让接收方校 验是否正确,这就是数据校验。最容易想到的校验方法是和校验,就是将传送的 数据(按字节方式)加起来计算出数据的总和,并将总和传给接收方,接收方收到 数据后也计算总和,并与收到的总和比较看是否相同。如果传输中出现误码,那 么总和一般不会相同,从而知道有误码产生,可以让发送方再发送一遍数据。 CRC校验也是添加额外数据做为校验码,这就是CRC校验码,那么CRC校验码是如何得到的呢? 非常简单,CRC校验码就是将数据除以某个固定的数(比如ANSI-CRC16中,这个数是0x18005),所得到的余数就是CRC校验码。 那这里就有一个问题,我们传送的是一串字节数据,而不是一个数据, 怎么将一串数字变成一个数据呢?这也很简单,比如说2个字节B1,B2,那么对应的数就是(B1<<8)+B2;如果是3个字节B1,B2,B3,那么对应的数就是 ((B1<<16)+(B2<<8)+B3),比如数字是0x01,0x02,0x03,那么对应的数字就是 0x10203;依次类推。如果字节数很多,那么对应的数就非常非常大,不过幸好 CRC只需要得到余数,而不需要得到商。 从上面介绍的原理我们可以大致知道CRC校验的准确率,在CRC8中出现了误码但没发现的概率是1/256,CRC16的概率是1/65536,而CRC32的概率则是1/2^32,那已经是非常小了,所以一般在数据不多的情况下用CRC16校验就可以了,而在整个文件的校验中一般用CRC32校验。 这里还有个问题,如果被除数比除数小,那么余数就是被除数本身,比 如说只要传一个字节,那么它的CRC就是它自己,为避免这种情况,在做除法之 前先将它移位,使它大于除数,那么移多少位呢?这就与所选的固定除数有关了, 左移位数比除数的位数少1,下面是常用标准中的除数: CRC8:多项式是X8+X5+X4+1,对应的数字是0x131,左移8位 CRC12:多项式是X12+X11+X3+X2+1,对应的数字是0x180D,左移12位 CCITT CRC16:多项式是X16+X12+X5+1,对应的数字是0x11021,左移16位 ANSI CRC16:多项式是X16+X15+X2+1,对应的数字是0x18005,左移16位 CRC32:多项式是 X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1,对应数字是 0x104C11DB7,左移32 因此,在得到字节串对应的数字后,再将数字左移M位(比如ANSI-CRC16是左移16位),就得到了被除数。 好了,现在被除数和除数都有了,那么就要开始做除法求CRC校验码了。CRC除法的计算过程与我们笔算除法类似,首先是被除数与除数高位对齐后,被 除数减去除数,得到了差,除数再与差的最高位对齐,进行减法,然后再对齐再 减,直到差比除数小,这个差就是余数。不过和普通减法有差别的是,CRC的加(减) 法是不进(借)位的,比如10减01,它的结果是11,而不是借位减法得到的01,因此,实际上CRC的加法和减法所得的结果是一样的,比如10加01的结果是11,10减01的结果也是11,这其实就是异或操作。虽然说了这么多也不一定能 说清楚,我们还是看一段CRC除法求余程序吧: /* 这段程序是求数据0x880000除以0x11021的余数 */ /* 这段程序其实也就是求字节0x88的CRC16校验码,因为0x88左移16位是0x880000 */ unsigned short crc16_div() { unsigned long data = 0x880000; unsigned long ccitt16 = 0x11021; /* 这是比较值,被除数与它比较看是否需要减去除数 注意,这里只需要与0x10000比较就可以了,而不需要与除数0x18005比较,这样可以少很多计算 而且余数的范围就在0-0xFFFF之间,而不是0-0x18004之间了 */ unsigned long cmp_value = 0x10000; int i; ccitt16 <<= 7; /* 左移7位,与被除数最高位对齐 */ cmp_value <<= 7; /* 左移7位,与被除数最高位对齐 */ while (cmp_value >= 0x10000) /* 循环直到差数比cmp_value小 */ { if ((data & cmp_value) != 0) /* 最高位为1,则减去除数 */ { data ^= ccitt16; /* 做CRC的减法,就是异或操作 */ } else /* 最高位为0,不够减 */ { /* 不作任何操作,只执行后面的移位操作 */ } /* 得到了差,右移一位,与被除数下一位对齐 */ ccitt16 >>= 1; cmp_value >>= 1; } /* 现在data的最低两个字节就是余数,也就是CRC校验码 */ return (data & 0xFFFF); } 好了,现在我们已经会计算0x88的CRC校验码了,它只是对0x880000做除法运算求余数而已,不过这只是求单字节的CRC校验码,那如果有十多个字 节怎么办?我们的计算机也存不下那么大的数呀,看来我们还要对程序进行些改 进,使它能对大数求除法了。 unsigned short crc16_div_2() { /* 这段程序也是求数据0x88的CRC校验码,与上一个程序crc16_div所得结果相同 */ /* 这里只需要直接传数据就可以,而不需要再事先移位 */ unsigned short data = 0x88; /* 这里只需要2个字节0x1021,而不是0x11021,为什么不再需要最高位的1,看看代码就清楚了 */ unsigned short ccitt16 = 0x1021; int i; data <<= 8; for (i=0; i<8; i++) { if (data & 0x8000) /* 最高位为1,减去除数 */ { data <<= 1; /* 将最高位的1移出,剩下的数与0x1021(而不是0x11021)异或,这是因为最高位的1与0x11021的最高位1异或后为0 */ data ^= ccitt16; } else /* 最高位为0,不需要减去除数 */ { data <<= 1; /* 直接移位 */ } } return data; } 现在对单字节0x88求CRC16,我们只需要两字节short型的整数就行了,而不需要象以前必须用long型0x880000,其实不管多少字节,只用short型就能够计算它的CRC16。下面说说怎么求多字节的样验码: 当我们求得一个字节(比如0x88)的CRC校验码后,如果这时又有一个字节(比如0x23)加入,需要求校验码,该怎么办呢?以前得到的是0x880000除以0x11021 的余数,但现在需要得到的是0x88230000除以0x11021的余数,以前求得的校验码是不是白费了?不是的,因为当我们得到0x880000除以0x11021的余数(这 里余数是0x1080)后,需要求0x88230000除以0x11021的余数,只要将原来的余数0x1080左移8位除以0x11021就得到了0x98000000除以0x11021的余数(想 一想为什么),再加上0x230000除以0x11021的余数。这其实就是求0x108000+0x230000除以0x11021的余数.。因此根据这个方法,我们就可以写 出求多个字节的CRC算法: /* 这段代码是求ccitt-crc16的算法 参数: data:字节数据 crc:原来数据求得的crc校验码 返回值: 数据的ccitt-crc16校验码 */ unsigned short crc16_ccitt(unsigned char data, unsigned short crc) { unsigned short ccitt16 = 0x1021; int i; crc ^= (data<<8); /* 新的数据与将原来的余数(就是crc)相加(加法就是异或操作) */ /* 求数据的CRC校验码 */ for (i=0; i<8; i++) { if (crc & 0x8000) /* 最高位为1,减去除数 */ { crc <<= 1; crc ^= ccitt16; } else /* 最高位为0,不需要减去除数 */ { crc <<= 1; /* 直接移位 */ } } return crc; } /* 这是个主程序,表示如何计算5个字节的CRC */ void main() { int i; unsigned short crc; char data[5] = { 0x71, 0x88, 0x93, 0xa5, 0x13 }; /* 计算这5 个数据的CRC校验码 */ crc = 0; for (i=0; i<5; i++) { crc = crc16_ccitt(data[i], crc); } printf("crc is %x", crc); } 好了,讲到这里CRC算法已经全部介绍完了。什么,讲完了?不对呀, 我怎么记得CRC程序都有个数组叫CRC表什么的,你这里怎么没有? 呵呵,其实使用CRC表是为了节省一些运算时间,事先将算好的CRC 保存在数组里,省得临时再计算,它保存的是0到0xff的CRC码,下面我们来 自己生成一个CRC表: unsigned short CRC16_CCITT_TABLE[256]; void init_crc16_ccitt_table() { int i; for (i=0; i<256; i++) { CRC16_CCITT_TABLE[i] = crc16_ccitt(i, 0); } } 上面只是一个字节的CRC表,那多个字节的CRC如何计算呢?与前面求多字节的CRC方法差不多,它的代码如下: /* 这段代码是查表求ccitt-crc16的算法,它与前面的程序crc16_ccitt所得 到的结果一样 参数: data:字节数据 crc:原来数据求得的crc校验码 返回值: 数据的ccitt-crc16校验码 */ unsigned short crc16_ccitt_2(unsigned char data, unsigned short crc) { unsigned char c; c = crc >> 8; /* c的值为crc的高8位 */ crc <<= 8; /* crc现在的值变为低8位左移8位 */ crc ^= CRC16_CCITT_TABLE[data ^ c]; return crc; } 最后要说的是CRC的正序和反转问题,比如前面ccitt-crc16的正序是0x1021,如果是反转就是0x8408(就是将0x1021倒过来低位变高位)为什么要反转?这是因为数据传输可能是先传低位再传高位(比如串口就是低位在前高位 在后)。反转的CRC算法与正序类似,只是需要注意移位的方向相反。 /* 这段代码是求ccitt-crc16的反转算法 参数: data:字节数据 crc:原来数据求得的crc反转校验码 返回值: 数据的ccitt-crc16反转校验码 */ unsigned short crc16_ccitt_r(unsigned char data, unsigned short crc) { unsigned short ccitt16 = 0x8408; int i; crc ^= data; /* 新的数据与将原来的余数(就是crc)相加(加法就是异或操作) */ for (i=0; i<8; i++) { if (crc & 1) /* 最低位为1,减去除数 */ { crc >>= 1; crc ^= ccitt16; } else /* 最低位为0,不需要减去除数 */ { crc >>= 1; /* 直接移位 */ } } return crc; } /* 这段代码是查表求反转ccitt-crc16的算法,它与前面的程序crc16_ccitt_r所得到的结果一样 参数: data:字节数据 crc:原来数据求得的crc校验码 返回值: 数据的ccitt-crc16校验码 */ unsigned short crc16_ccitt_r2(unsigned char data, unsigned short crc) { unsigned char c; c = crc & 0xff; crc >>= 8; crc ^= CRC16_CCITT_R_TABLE[data ^ c]; return crc; } 本来随这篇Blog我写了两个C程序,一个是这篇文章的全部源程序的例子,一个是crc16的CRC表及查表程序,程序在TC 2.0下测试通过。不过我 不知道怎么添加附件,所以就没附程序了。
/
本文档为【CRC校验算法】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索