CRC16算法分析资料Word文档格式.docx
- 文档编号:7718860
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:20
- 大小:160.78KB
CRC16算法分析资料Word文档格式.docx
《CRC16算法分析资料Word文档格式.docx》由会员分享,可在线阅读,更多相关《CRC16算法分析资料Word文档格式.docx(20页珍藏版)》请在冰点文库上搜索。
是接受方和发送方的一个约定,也就是一个二进制数,在整个传输过程中,这个数始终保持不变。
在发送方,利用生成多项式对信息多项式做模2除生成校验码,而在接受方利用生成多项式对收到的编码多项式做模2除检测和确定错误位置。
生成多项式的选取应满足以下条件:
a、生成多项式的最高位和最低位必须为1。
b、当被传送信息(CRC码)任何一位发生错误时,被生成多项式做模2除后应该使余数不为0。
c、不同位发生错误时,应该使余数不同。
d、对余数继续做模2除,应使余数循环。
将这些要求反映为数学关系是比较复杂的,国际标准中常用的生成多项式有:
CRC-12:
G(x)=x12+x11+x3+x2+x+1
CRC-16:
G(x)=x16+x15+x2+1
CRC-CCITT:
G(x)=x16+x12+x5+1
CRC-32:
G(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x+1
(3)模2除(按位异或)
模2除做法与算术除法类似,但每一位除(减)的结果不影响其它位,即不向上一位借位,实际上就是异或,然后再移位做下一位的模2减。
步骤如下:
a、用除数对被除数最高几位做模2减,没有借位。
b、除数右移一位,若余数最高位为1,商为1,并对余数做模2减。
若余数最高位为0,商为0,除数继续右移一位。
c、一直做到余数的位数小于除数时,该余数就是最终余数。
2、校验原理
循环冗余校验码(CRC)的基本原理是:
发送端在K位信息码后再拼接R位的校验码,整个编码长度为N位,故又称(N,K)码,如图1所示。
对于一个给定的(N,K)码,可以证明存在一个最高次幂为N-K=R的多项式G(x),根据G(x)可以生成K位信息的校验码,而G(x)叫做这个CRC码的生成多项式。
接收端将接收到的N位报文与G(x)进行运算,如果余数为0,则表示数据有效,再将报文右移R位得到原始报文,如果余数不为0,则数据无效,再做相应的处理。
图1(N,K)码
计算CRC校验码采用模2加减运算法则,既是不带进位和借位的按位加减,这种加减运算实际上就是逻辑上的异或运算。
校验码的具体生成过程为:
假设发送信息用信息多项式C(X)表示,将C(x)左移R位,则可表示成C(x)*2R,这样C(x)的右边就会空出R位,这就是校验码的位置,通过C(x)*2R模2除以生成多项式G(x)得到的余数就是校验码。
CRC码的生成步骤:
a、将x的最高幂次为R的生成多项式G(x)转换成对应的R+1位二进制数。
b、将信息码左移R位,相当于对应的信息多项式C(x)*2R。
c、用生成多项式(二进制数)对信息码做模2除,得到R位的余数。
d、将余数拼到信息码左移后空出的位置,得到编码后的报文。
例:
假设使用的生成多项式是G(x)=x16+x12+x5+1,单字节的原始报文为0x12,求编码后的报文。
解:
a、将生成多项式G(x)转换成对应的二进制数:
1,0001,0000,0010,0001,即0x11021。
b、把原始报文左移R=16位变成:
0001,0010,0000,0000,0000,0000。
c、用生成多项式对应的二进制数对移位后的原始报文进行模2除:
d、编码后的报文:
即编码后发送的报文为0x123273,经验证报文0x123273与0x11021异或后余数为0。
3、误码率分析
一般情况下,R位生成多项式产生的CRC码可检测出所有的双错、奇数位错和突发长度小于等于R的突发错以及(1-2-(R-1))的突发长度为R+1的突发错和(1-2-R)的突发长度大于R+1的突发错。
例如,对上述R=16的情况,就能检测出100%的突发长度小于等于16的突发错以及99.997%的突发长度为17的突发错和99.998%的突发长度大于17的突发错。
这里,突发错误是指几乎是连续发生的一串错,突发长度就是指从出错的第一位到出错的最后一位的长度(中间并不一定每一位都错)。
(“16位循环冗余校验码CRC的原理和性能分析”)
三、CRC校验码计算
不同的应用系统,拥有的硬件资源不一样,要求的数据传输速度也不一样。
因此可将应用系统分为3类:
一是程序存储空间有限,但对CRC计算速度要求不高的微控制系统;
二是程序存储空间较大且对CRC计算速度要求较高的计算机或微控制系统;
三是程序存储空间不太大,且对CRC计算速度又有一定要求的微控制系统。
根据不同的应用系统采取相应的CRC算法,CRC校验码的生成有按位计算、按字节计算和按半字节计算等方法,具体原理如下所述。
(“用查表法实现微处理器的快速CRC计算”)
1、按位计算CRC校验码
对于一个二进制序列数可以表示为式(1-1):
(1-1)
求此二进制序列数的CRC码时,先乘以216后(既左移16位),再除以多项式G(X),所得的余数既是所要求的CRC码。
如式(1-2)所示:
(1-2)
可以设:
(1-3)
其中
为整数,
为16位二进制余数。
将式(1-3)代入式(1-2)得:
(1-4)
再设:
(1-5)
为16位二进制余数,将式(1-5)代入式(1-4),如上类推,最后得到:
(1-6)
根据CRC的定义,很显然,十六位二进制数
即是我们要求的CRC码。
式(1-5)是编程计算CRC的关键,它说明计算本位后的CRC码等于上一位CRC码乘以2后除以多项式,所得的余数再加上本位值除以多项式所得的余数。
按位计算CRC虽然代码简单,所占用的内存比较少,但其最大的缺点就是一位一位地计算会占用很多的处理器处理时间,在高速通讯的场合还是得慎重考虑。
2、按字节计算CRC校验码(“循环冗余校验码的查表生成算法及其实现”)
不难理解,对于一个二进制序列数可以按字节表示为式(2-1),其中
为一个字节(共8位)。
(2-1)
如式(2-2)所示:
(2-2)
(2-3)
将式(2-3)代入式(2-2)得:
(2-4)
因为:
(2-5)
是
的高八位,
的低八位。
将式(2-5)代入式(2-4),经整理后得:
(2-6)
(2-7)
将式(2-7)代入式(2-6),如上类推,最后得:
(2-8)
很显然,十六位二进制数
式(2-7)是编写按字节计算CRC程序的关键,它说明计算本字节后的CRC码等于上一字节余式CRC码的低8位左移8位后,再加上上一字节CRC右移8位(也既取高8位)和本字节之和后所求得的CRC码,如果将8位二进制序列数的CRC全部计算出来,放在一个表里,采用查表法,可以大大提高计算速度。
但对于广泛运用的8位微处理器,代码空间有限,对于要求256个CRC-16余式表(共512字节的内存)已占用相当大的内存空间,但CRC的计算速度又不可以太慢,因此考虑下面一种按半字节求CRC的算法。
3、按半字节计算CRC校验码
同样道理,对于一个二进制序列数可以按字节表示为式(3-1),其中
为半个字节(共4位)。
(3-1)
如式(3-2)所示:
(3-2)
(3-3)
将式(3-3)代入式(3-2)得:
(3-4)
(3-5)
的高4位,
的低12位。
将式(3-5)代入式(3-4),经整理后得:
(3-6)
(3-7)
将式(3-7)代入式(3-6),如上类推,最后得:
(3-8)
式(3-7)是编写按字节计算CRC程序的关键,它说明计算本字节后的CRC码等于上一字节CRC码的低12位左移4位后,再加上上一字节余式CRC右移4位(也既取高4位)和本字节之和后所求得的CRC码,如果把4位二进制序列数的CRC全部计算出来,放在一个表里,采用查表法,每个字节算两次(半字节算一次),可以在速度和内存空间取得均衡。
四、运算代码及运算速度分析
1、前提条件
8位单片机编译环境KeiluVision2,在主程序中给发送缓冲区赋初值,然后调用CRC校验码生成子程序即可。
2、程序代码
buffer[]指向发送缓冲区的字节,len为发送的字节总数,0x1021为生成多项式对应的二进制数(最高位肯定为1,故略去),crc_table[16]是32个字节的CRC余式表。
按位计算CRC码的C语言程序代码:
unsignedintcal_crc16(unsignedcharbuffer[],unsignedcharlen)
{
unsignedchari,j=0;
unsignedintcrc_register=0;
while(len--!
=0)//总字节数
{
for(i=0x80;
i!
=0;
i=i>
>
1)//一个字节8位,故循环8次
if((crc_register&
0x8000)!
=0)//高位为1则进行位或运算
crc_register<
<
=1;
//高位肯定为1,无需运算
crc_register^=0x1021;
//与生成多项式异或
}
else
//高位不为1,则乘2
if((buffer[j]&
i)!
=0)
//加上本位的CRC码
j++;
//指向下一字节
return(crc_register);
//返回CRC-16校验码
}
按半字节计算CRC码的C语言程序代码:
unsignedintcrc_table[16]={0x0000,0x1021,0x2042,0x3063,0x4084,0x50a5,0x60c6,
0x70e7,0x8108,0x9129,0xa14a,0xb16b,0xc18c,0xd1ad,0xe1ce,0xf1ef};
unsignedcharcrc_upper,i=0;
crc_upper=((unsignedchar)(crc_register/256))/16;
//暂存高4位
=4;
//CRC右移4位,取CRC的低12位
crc_register^=crc_table[crc_upper^(buffer[i]/16)];
//CRC的高4位和本字节的前半字节相加后查表得CRC,再加上上一次CRC的余数
crc_register^=crc_table[crc_upper^(buffer[i]&
0x0F)];
//CRC的高4位和本字节的后半字节相加后查表得CRC,再加上上一次CRC的余数
i++;
//指向下一字节
//返回校验码
3、比较分析
在KeiluVision2的调试模式下将C语言程序转换成汇编语言,通过调试命令,逐步地观测程序的执行步骤,算出每条执行过的汇编语句的指令周期,进而总结出计算CRC校验码所需要的时间。
(“适用于单片机的循环冗余校验码的快速算法”)对按位和按字节计算CRC校验码的子程序unsignedintcal_crc16(unsignedcharbuffer[],unsignedcharlen)进行分析,总结如表1所示。
表1按位和按半字节计算CRC校验码的比较
按位计算
按半字节计算
备注
占用内存情况
几乎不占
32字节
半字节共16个CRC-16余氏码,故32个字节
发送单个字节
平均指令执行条数
5+32×
8+8=269
84
按位计算一个字节要循环8次
平均指令执行周期数
7+47×
8+12=395(指令周期)
98
(指令周期)
不包括初始化的12个指令周期和CRC校验码返回的6个指令周期
发送13个字节
395×
13=5135
98×
13=1274
循环13次的总指令周期数
对于半字节计算CRC校验码,在12MHz系统晶振下,完成13个字节数据校验的时间为108us,而对于8位单片机在以38400bps进行串口通信时,传送13个字节数据的时间约为3ms,因此可以边传送边校验,利用串行发送的时间完成校验的工作,可以提高单片机通信系统的工作效率。
(“基于MCS_51单片机的CRC_16的实现方法”)
考虑到计算CRC校验码的处理速度和内存空间:
按位计算,速度较慢,但占用最小的内存空间;
按字节查表计算,速度较快,但占用较大的内存,一个字节占256个内存空间,对CRC-16来说就是512个字节;
按半字节查表计算,是前两者的均衡,即不会占用太多的内存,对CRC-16来说就是32个字节,同时速度又不至于太慢,比较适合8位小内存的单片机的应用场合。
附录:
汇编语言指令周期分析记录
按位计算CRC校验码(发送单字节0xFF)
crc_bit_len_FF:
C:
0x0003MOV0x0D,R3//2
0x0005MOV0x0E,R2//2
0x0007MOV0x0F,R1//2
0x0009MOV0x10,R5//2
0x000BCLRA//1
0x000CMOVR5,A//1
0x000DMOV0x11,A//1
0x000FMOV0x12,A//1
0x0011MOVR7,0x10//2
0x0013DEC0x10//1
0x0015MOVA,R7//1
0x0016JZC:
0060//2
0x0018MOVR4,#P0//1
.....8......
0x001AMOVA,R4//1
0x001BJZC:
005D//2
0x001DMOVA,0x11//1
0x001FJNB0xE0.7,C:
0035//2
0x0035MOVA,0x12//1
0x0037ADDA,ACC//1
0x0039MOV0x12,A//1
0x003BMOVA,0x11//1
0x003DRLCA//1
0x003EMOV0x11,A//1
0x0040MOVR3,0x0D//2
0x0042MOVR2,0x0E//2
0x0044MOVR1,0x0F//2
0x0046MOVDPL,R5//2
0x0048MOVDPH,#0x00//2
0x004BLCALLC?
CLDOPTR(C:
0x0065)//2
0x0065CJNER3,#0x01,C:
0x0074//2
0x0074JNCC:
0x007C//2
0x0076MOVA,R1//1
0x0077ADDA,DPL//1
0x0079MOVR0,A//1
0x007AMOVA,@R0//1
0x007BRET//2
0x004EANLA,R4//1
0x004FJZC:
0x0057//2
0x0051XRL0x12,#0x21//2
0x0054XRL0x11,#0x10//2
0x0057MOVA,R4//1
0x0058CLRC//1
0x0059RRCA//1
0x005AMOVR4,A//1
0x005BSJMPC:
0x001A//2
0x005DINC0x10//1
0x005ESJMPC:
0x0015//2
0x0060MOVR6,0x11//2
0x0062MOVR7,0x12//2
0x0064RET//2
指令周期数:
12+(7+47×
8+12)+6=413
按半字节计算CRC校验码(发送单字节0xFF)
crc_half_byte_len_FF:
0x008FMOV0x2E,R3//2
0x0091MOV0x2F,R2//2
0x0093MOV0x30,R1//2
0x0095MOV0x31,R5//2
0x0097CLRA//1
0x0098MOVR5,A//1
0x0099MOV0x32,A//1
0x009BMOV0x33,A//1
…………………
0x009DMOVR7,0x31//2
0x009FDEC0x31//1
0x00A1MOVA,R7//1
0x00A2JZC:
010C//2
0x00A4MOVA,0x32//1
0x00A6MOVR7,A//1
0x00A7SWAPA//1
0x00A8ANLA,#0x0F//1
0x00AAMOVR4,A//1
0x00ABMOVA,0x33//1
0x00ADSWAPA//1
0x00AEMOVR0,A//1
0x00AFANLA,#0x0F//1
0x00B1XCHA,R0//1
0x00B2XRLA,R0//1
0x00B3MOV0x33,A//1
0x00B5MOVA,0x32//1
0x00B7SWAPA//1
0x00B8ANLA,#B//1
0x00BAORLA,R0//1
0x00BBMOV0x32,A//1
0x00BDMOVR3,0x2E//2
0x00BFMOVR2,0x2F//2
0x00C1MOVR1,0x30//2
0x00C3MOVDPL,R5//2
0x00C5MOVDPH,#0x00//2
0x00C8LCALLC?
0111)//2
0x0
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- CRC16 算法 分析 资料