当前位置:文档之家› CRC算法详解与c源码

CRC算法详解与c源码

CRC算法详解与c源码
CRC算法详解与c源码

循环冗余码(CRC ,cyclic redundancy code )校验技术是一种十分有效的数据传输错误检测技术,能检验一位错、双位错、所有的奇数错、所有长度小于或等于所用的生成多项式长度的错误,在通信系统、控制系统中得到广泛运用。 计算CRC 校验码和验证报文是否有误,总是由计算机实时地完成的,手工计算仅仅用于说明CRC 校验码的生成原理。由于实时性的要求,必须使用快捷的计算机计算方法。

CRC 校验原理

在k 位信息码后再拼接r 位的校验码,报文编码长度为n 位,因此,这种编码又叫(n ,k )码。对于一个给定的(n ,k )码,可以证明,存在一个最高次幂为n=k+r 的多项式G(x),存在且仅存在一个R 次多项式G(x),使得

R V(x)A(x)G(x)x m(x)r(x)==+。其中:m(x)为k 次信息多项式,r(x)为r-1次校验多项式,g(x)称为生成多项式:1

2

10121()

R R R ()R

G (x)g g x g x ...g x

g x --=+++++。发送方通过指定的G(x)产生r 位的CRC 校验码,接收方则通过该G(x)来验证

收到的报文码的CRC 校验码是否为0。

假设发送信息用信息多项式C(X)表示,将C(x)左移r 位,则可表示成C(x)*2r ,这样C(x)的右边就会空出r 位校验码

的位置,做除法(模2除)2r ())C x G (x ?,得到的余数R 就是校验码。发送的CRC 编码是()2r C x R ?+,验证接收到的报文编

码是否至正确,依然是做(x )模2除:

2r (x )x C )

R

G (?+。

CRC 的生成多项式

生成多项式的选取应满足以下条件: a 、生成多项式的最高位和最低位必须为1。

b 、当被传送信息(CRC 码)任何一位发生错误时,被生成多项式做模2除后,应该使余数不为0。

c 、不同位发生错误时,应该使余数不同。

d 、对余数继续做模2除,应使余数循环。 主要的生成多项式G(x)有以下几种:

名称 生成多项式 数值式 简记式 标准引用

CRC-16

x 16+x 15+x 2+1

0x1’8005

8005

IBM SDLC

CRC-CCITT x16+x12+x5+1 0X1’10210x1021

ISO HDLC,ITU X.25,V.34/V.41/V.42,PPP-FCS

CRC-32

注* 0X1’04C11DB70x04C11DB7

ZIP,RAR,IEEE 802 LAN/FDDI,IEEE1394,PPP-FCS

注* x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1

下表中的生成多项式G(x)也常见的:

名称生成多项式数值式简记式标准引用

CRC-4 x4+x+1 0x1’3 0x3 ITU G.704

CRC-8 x8+x5+x4+1 0x1’31 0x31

CRC-8 x8+x2+x1+1 0x1’07 0x07

CRC-8 x8+x6+x4+x3+x2+x10x1’5E 0x5E

CRC-12x12+x11+x3+x2+x+1 0x1’80F0x80F

CRC-32c

注**

0X1’1EDC6F41 0x1EDC6F41 SCTP

注** x32+x28+x27+x26+x25+x23+x22+x20+x19+x18+x14+x13+x11+x10+x9+x8+x6+1

CRC校验码的手工计算

CRC的手工计算,就是按普通的二进制竖式除法的格式做模2除法。由于我们需要的是余数,不必关心商的大小,所以,可以不用写出商,而直接进行一次次移位和模2减。具体计算过程是:

a. 在信息码后面加上r(即CRC校验码的位数)个0,作为被除数,让除数(即生成多项式)的最高位1,对齐被除数的最高位1。

b. 做模二减:如果被除数最高位为1,减生成多项式,余数作为中间余数,否则,不减。

c. 生成多项式右移1位。

e. 反复进行步骤b,c,直到余数与a中添加的r个0在位置上对齐,该余数就是最终余数,即信息码的CRC校验码。

16位CRC校验码的计算机

本节使用的生成多项式为G16= x16+x12+x5+1=0x11021。在计算机程序中,因为16位rcr校验码的生成多项式总宽度为17,而最高位为1,故多占用一个8位寄存器。然而,在模2除的过程中,多项式的最高位1总是与被除数(或中间余数)的最左边的1对齐,而相异或的结果总是为0。这样,在程序中可以把生成多项式的最高位1去掉,而只包含后面的16位,例如,将0x11021简化为0x1021,称做生成多项式简化式。

用左移位模2除求余数时,在异或前,检查被除数(或中间余数)的最高位否为1,如果为1,被除数(或中间余数)左移1位,与生成多项式简化式异或;如果为0,被除数(或中间余数)左移1位,不做其它操作。总的移位次数为“被除数的位数-除数(生成多项式简化式)的位数”。 1 模拟手工移位计算相

设n 个字节信息数据B n-1,B n-2,...,B 1,B 0,用生成多项式CRC16-CCITT 计算crc 。

1.设置一个32bit 的变量,例如crc0。B n-1,B n-2,B n-3,B n-4依次放入crc0。如果n<4,后面的字节为0。

2.Crc0左移1位,检查移出位,如果为1,crc 与生成多项式简化式异或,结果存入crc 。如果不为1,则不做异或。 3.上一步重复8次后,右端空出1个字节的位置,将下一个信息字节补入。

4.重复2,3两步,直到信息数据全部取完。crc 右移16位,crc 中的内容即为CRC 校验杩。 //f1 仿手工,逐位移位

unsigned short f1(unsigned char *mess,unsigned int len) { unsigned int crc0=0;

unsigned int div=0x1021*0x10000; unsigned int i,j;

for(j=0;j<4;j++) //crc0中至少填入4个信息字节 { crc0=crc0<<8; //信息字节数少于4时,用0补齐 if(j

{ crc0=crc0^*mess; mess++; } }

for(j=0;j

else crc0=crc0<<1; }

if(j+4

crc0=crc0>>16;

return crc0; //将32位数变为16位数 }

2 根据前k 位信息码的CRC 校验码移位计算前k+1位信息码的CRC 校验码 计算前k 位信息码m k 的crc 校验码:

16k k m X r k q G 16G 16?=+

。式中,r k 即为前k 位信息码m k 的crc 校验码。 若在前k 位信息码之后的一位为b i ,计算m k+1的crc 校验码:

116

116

16k i k i (m X m )X m X X b X G 16

G 16

G 16?+????=

+

116

k i k r X b X q G 16

G 16

??=+

+

按位移位计算m k+1的crc 校验码的方法可表述为:(k r 2?的余数)+(16

i b 2?的余数)。求k r 2?的余数,只需要进行1次左移位除,求16

i b 2?的余数,采用查表的方法,默认0的余数为0,1的余数为0x1021。 //f2 根据前n 位的crc 码计算前n+1位的crc 码,逐位移位 unsigned short f2(unsigned char *mess,unsigned len) { unsigned int crc0=0; unsigned char i;

while(len--!=0)

{ for(i=0x80;i!=0;i>>=1) //0的余数为0,1的余数为1021 { if((crc0&0x8000)!=0) //先求k r 2?的余数 { crc0<<=1; crc0^=0x1021; }

else crc0<<=1;

if((*mess&i)!=0) crc0^=0x1021; //再加上16

i b 2?的余数

} mess++; }

return crc0; }

3 根据前k 字节信息码的CRC 校验码移位计算前k+1字节信息码的CRC 校验码 计算前k 字节信息码的crc 校验码:

16k k k M x R Q G 16

G 16

?=+

。式中,R k 即为前k 字节信息码M k 的crc 校验码。

若在前k 字节信息码之后的一字节为M i ,计算M k+1的crc 校验码:

816

168

16k i k i (M X M )X M X X M X G 16

G 16G 16?+????=

+

8

8

8

k

i k R M X Q x X G 16G 16?=+?+? 88

k i k (R M X )X Q G 16

+??=+

按字节移位计算M k+1的crc 校验码的方法表述为:8

()k i R M 2+?,左移位除8次。 //f3 根据前n 字节的crc 码计算前n+1字节的crc 码,逐位移位 unsigned short f3(unsigned char *mess,unsigned len) { unsigned short crc0=0; unsigned short i;

while(len--)

{ crc0=crc0^*mess<<8; //信息字节左移8位与与前次crc 校验码异或 for(i=0x8000;i!=0x80;i=i>>1) //8次移位除 { if((crc0&0x8000)!=0) { crc0=crc0<<1; crc0=crc0^0x1021; }

else crc0=crc0<<1; } mess++; }

return crc0; }

4 根据前k 字节信息码的CRC 校验码查表计算前k+1字节信息码的CRC 校验码 计算前k 字节信息码的crc 校验码:

161616k k k M x R Q G G ?=+

R k 即为前k 字节信息码M k 的crc 校验码。

888

16k h k l k R x R Q G ?+=+。 将R k 分解为高字节(高8位)和低字节(低8位)两部分

如果在M k 之后增加一个字节M i ,则k+1个字节的数据序列可以表示为:8

1k k i M M x M +=?+,计算M k+1的CRC 校验码: 16816

11616k k i M x (M x m )x G G ++??=

16

16

8

1616k i M x m x x G G ??=

+

?

16

8

81616

k i k M m x Q x x G G ?=?+

+?

816

8

8

88

1616k h k l i k R x R m x Q x G G x

?+?=?+

+

?

168

8

881616)k h i k l k (R m x R x Q x G G +??=?++

1688

81616)k h i k k (R m x R x Q x G G +??=?++

。 //88

8kl k R x R x =??

按查字节表计算m k+1的crc 校验码的语言表述为:(R kh8+m i )查字节表+R k <<8 //f4 根据前n 字节的crc 码计算前n+1字节的crc 码,按字节查表 unsigned short f4(unsigned char *mess,unsigned len) { unsigned short crc0=0; unsigned short crc; unsigned short i;

for(i=0;i

{ crc=remB[(crc0>>8)^*mess]; //对异或结果从表中查余数,得本次中间余数 crc0=crc^(crc0<<8); //与本次中间余数异或,得本次余数 mess++; }

return crc0; }

5 根据前k 字节信息码的CRC 校验码按高低半字节查表计算前k+1字节信息码的CRC 校验码

已求得16816816

8122161616

16

k h i k l k k i k (R M )R M x (M x m )x Q G G G G +++????==+

+

对上式继续变换:

16

8168811616

16

k h i k l k (

R M )X R X M x Q x k G G G ++???=?+

+

4168

8

4481616)h l k l k (S x S x R x Q x G G ?+??=?++

4161688

44161616)h l k k (S x x S x R x Q x G G G ????=?+++

。 88

8kl k R x R x =?? 查高低半字节表计算m k+1的crc 校验码的语言表述为:kh i h4(R M )+查h 表+kh i l4(R M )+查l 表+8k R <<。 //f5 根据前n 字节的crc 码计算前n+1字节的crc 码,分别按高低半字节查表 unsigned short f5(unsigned char *mess,unsigned len) { unsigned short crc0=0; unsigned short crc; unsigned short i;

for(i=0;i

{ crc=(crc0>>8)^*mess; //前次余数高字节与本次数据异或

crc0=remBh4[(crc&0xf0)>>4]^remBl4[crc&0x0f]^(crc0<<8); //2个余数与前次余数低字节异或 mess++; }

return crc0; }

6 根据前k 半字节信息码的CRC 校验码查表计算前k+1半字节信息码的CRC 校验码 计算前k 半字节信息码的crc 校验码:

168161616k k k h k l

k k M x R R x R Q Q G G G ??+=+=+

。 R k 为16bit 余数,即为CRC 校验码。

如果在M k 之后增加一个半字节M i ,则k+1个半字节的数据序列可以表示为:4

1k k i M M x M +=?+,计算M k+1的CRC 校验码: 16416

11616k k i M x (M x m )x G G ++??=

16

16

4

1616k i M x m x x G G ??=

+

?

1216

8

4

412

1616k h k l i k R x R m x Q x x G G ?+?=?+

+

?

161648

kh4i kl 12k R X M X R X Q x G 16

G 16

G 16

???=?+

+

+

16

48

kh4i k k (R M )X R X Q x G 16

G 16

+??=?+

+

。 //44

12kl k R x R x =??

查半字节表计算m k+1的crc 校验码的语言表述为:16

kh4i (R M )2+?查半字节表+(k R 4<<)。示例程序中,每次取1个字节,所以分两次分别计算前半字节和后半字节。

//f6 根据前n 半字节的crc 码计算前n+1半字节的crc 码,按低半字节查表 unsigned short f6(unsigned char *mess,unsigned int len) { unsigned short crc0=0; unsigned char crc0_m; unsigned char i;

for(i=0;i

crc0_m=(unsigned char)(crc0>>12); //得到前次余数的最高4位

crc0=crc0<<4; //前次余数右移4位,使最低4位为0 crc0=crc0^rem05[crc0_m^(*mess>>4)]; //相加后得本次中间余数

//一个字节的低半字节

crc0_m=(unsigned char)(crc0>>12); //得到本次中间余数的最高4位

crc0=crc0<<4; //本次中间余数右移4位,使最低4位为0 crc0=crc0^rem05[crc0_m^(*mess&0x0f)]; //相加后得本次余数 mess++; }

return crc0; }

7 余数表计算

计算余数表采用仿手工算法,以单字节数0-255为索引的crc-ccitt 的余数表,其256项,512个字节。余数用printf 函数输出到开发环境的不i/o 窗口,将余数表复制下来,在函数中建立一个常量数组,将余数表粘贴到数组中。另一个比较好的办法是,建立一个头文件,例如crc_32.h ,在其中建立一个常量数组,将余数表粘贴到数组中。 unsigned short crc01(void)

{ unsigned short remain;

unsigned short i,j;

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

{ remain=j<<8;

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

{ if((remain&0x8000)!=0)

{ remain<<=1;

remain^=0x1021;

}

else remain<<=1;

}

printf("0x%04x, ",remain); //16进制输出,4位宽度,不足4位左端补0

if((j+1)%8==0) printf("\n");

}

return 0;

}

32位CRC校验码的计算机计算

32位CRC校验码的算法与16位CRC校验码的算法以及c源码,同出一辙,差别在于crc校验码的位数不同,因而在公式推导和程序的变量设置上略有不同。鉴于计算32位校验码的实际情况,相应于6位crc校验码的f1-f6,以下仅给出f1,f3,f4,3个公式的推导的示例程序。G32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1=0x104C11DB7。

1 模拟手工移位计算

//f1 仿手工,逐位移位

unsigned long hand(unsigned char *byt,unsigned int len)

{ unsigned char buff_ch=0;

unsigned long crc=0;

unsigned int i,j;

for(j=0;j<4;j++) //data中至少填入4个信息字节

{ crc<<=8; //信息字节数少于4时,用0补齐

if(j

byt++;

}

if(j

for(j=0;j

if((buff_ch&0x80)!=0) crc^=0x00000001; crc^= 0x04C11DB7; } else { crc<<=1;

if((buff_ch&0x80)!=0) crc^=0x00000001; }

buff_ch<<=1; }

if(j+5

return crc; }

2 根据前k 字节信息码的CRC 校验码移位计算前k+1字节信息码的CRC 校验码 计算前k 字节信息码的crc 校验码:

32k k k M 2R Q G32

G32

?=+

式中R k 即为前k 字节信息码M k 的crc 校验码。

若在前k 字节信息码之后的一字节为M i ,计算M k+1的crc 校验码:

832

328

32k i k i (M X M )X M X X M X G 32

G 16G 32?+????=

+

24

8

8

k

i k R M X Q X X G 32G 32

?=+

?+?

248

k i k (R M X )X Q G 32

+??=+

按字节移位计算M k+1的crc 校验码方法表述为:24

8

k i (R M X )X

+??,左移位除8次。即,单字节的M i 与4字节的R k 的最高位字节相异或,然后,进行左移位除8次。 //f3

unsigned long f3(unsigned char *mess,unsigned int len) { unsigned long crc0=0; unsigned long i;

while(len--)

{ crc0=crc0^(*mess<<24); for(i=0;i<8;i++)

{ if((crc0&0x80000000)!=0) { crc0<<=1;

crc0^=0x04C11DB7; }

else crc0<<=1; } mess++; }

return crc0; }

4 根据前k 字节信息码的CRC 校验码查表计算前k+1字节信息码的CRC 校验码

为了计算32bit 的CRC 码,应将M k 向左移32位,再除以33bit 的生成多项式,余数即为CRC 码:

32248

24

323232

k k k h k l k k M x R R x R Q Q G G G ??+=+=+。 如果在M k 之后增加一个字节m i ,计算前k+1个字节的CRC 校验码:

3283232

32

8

1k k i k i M x (M x m )x M x m x x G G G

G

++????==+

?。 将

323232

k k k M x R

Q G G ?=+代入上式, 3283232881k k i k i k M x (M x m )x R m x Q x x G G G G ++???==++

??

2432

8

88243232k h k l i k R x R m x Q x x G G ?+?=++

?? 3288

83232)k h i k k (R m x R x Q x G G +??=?++

。 //88

24kl k R x R x =??

查字节表计算m

k+1的crc校验码的语言表述为:

8)

kh i

(R m

+查字节表+8

24

kl

(R x)

?。

//f2

unsigned long f4(unsigned char *mess,unsigned int len)

{ unsigned long crc0=0;

unsigned long crc_m;

unsigned int i;

for(i=0;i

{ crc_m=rem[(crc0>>24)^*mess];

crc0=crc_m^(crc0<<8);

mess++;

}

return crc0;

}

7 余数表计算

计算余数表采用仿手工算法,以单字节数0-255为索引的crc-32的余数表,共256项,1024个字节。程序中dxs=0x1EDC6F41。余数用printf函数输出到开发环境下的i/o窗口。在函数中建立一个常量数组,将余数表复制下来,粘贴到数组中。或者,建立一个头文件,例如crc_32.h,在其中建立一个常量数组,将余数表粘贴到数组中。

unsigned long crc01(void)

{ unsigned long remain;

unsigned short i,j;

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

{ remain=j<<24;

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

{ if((remain&0x80000000)!=0)

{ remain<<=1;

remain^=dxs;

}

else remain<<=1;

}

printf("0x%08x, ",remain); //16进制输出,8位宽度,不足8位左端补0

if((j+1)%8==0) printf("\n");

}

return 0;

}

CRC标准及计算过程

CRC标准及计算过程 根据应用环境与习惯的不同,CRC又可分为以下几种标准: ①CRC-8码; ②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值。

CRC16算法原理

CRC算法及C实现 学习体会2008-09-20 15:21:13 阅读161 评论0 字号:大中小订 阅 一、CRC算法原理 CRC校验的基本思想是利用线性编码理论,在发送端根据要传送的k位二进制码序列,以一定的规则产生一个校验用的监督码(既CRC码)r位,并附在信息后边,构成一个新的二进制码序列数共(k+r)位,最后发送出去。在接收端,则根据信息码和CRC码之间所遵循的规则进行检验,以确定传送中是否出错。 16位的CRC码产生的规则是先将要发送的二进制序列数左移16位(既乘以)后,再除以一个多项式,最后所得到的余数既是 CRC码。 假设数据传输过程中需要发送15位的二进制信息 g=101001110100001,这串二进制码可表示为代数多项式g(x) = x^14 + x^12 + x^9 + x^8 + x^7 + x^5 + 1,其中g中第k位的值,对应g(x)中x^k的系数。将g(x)乘以x^m,既将g后加m个0,然后除以m阶多项式h(x),得到的(m-1)阶余项 r(x)对应的二进制码r就是 CRC编码。 h(x)可以自由选择或者使用国际通行标准,一般按照h(x)的阶数m,将CRC算法称为CRC-m,比如CRC-32、CRC-64等。国际通行标准可

以参看 https://www.doczj.com/doc/3d6329379.html,/wiki/Cyclic_redundancy_check g(x)和h(x)的除运算,可以通过g和h做xor(异或)运算。比如将 11001与10101做xor运算: 明白了xor运算法则后,举一个例子使用CRC-8算法求101001110100001的效验码。CRC-8标准的h(x) = x^8 + x^7 + x^6 + x^4 + x^2 + 1,既h是9位的二进制串111010101。

计算法简单实现crc校验

计算法简单实现crc校验 计算法简单实现crc校验 前一段时间做协议转换器的时间用到CRC-16校验,查了不少资料发现都不理想。查表法要建表太麻烦,而计算法觉得那些例子太罗嗦。最后只好自己写了,最后发现原来挺简单嘛:)两个子程序搞定。这里用的多项式为:CRC-16=X16+X12+X5+X0=2 +2 +2+2 =0x11021 因最高位一定为“1”,故略去计算只采用0x1021即可 CRC_Byte:计算单字节的CRC值 CRC_Data:计算一帧数据的CRC值 CRC_HighCRC_Low:存放单字节CRC值 CRC16_HighCRC16_Low:存放帧数据CRC值; ------------------------------------------------------------- ;Functi on:CRConebyte ;Input:CRCByte ;Output:CRC_HighCRC_Low ; ------------------------------------------------------------- CRC_Byte: clrfCRC_Low clrfCRC_High movlw09H movwfv_Loop1 movfCRCByte,w movwfCRC_High CRC: decfszv_Loop1;8次循环,每一位相应计算 gotoCRC10 gotoCRCend CRC10 bcfSTATUS,C rlfCRC_Low rlfCRC_High btfssSTATUS,C   ;gotoCRC;为0不需计算movlw10H;若多项式改变,这里作相应变化xorwfCRC_High,f movlw21H;若多项式改变,这里作相应变化 xorwfCRC_Low,f gotoCRC CRCend: nop nop return ; ------------------------------------------------------------- ;CRCone byteend ; ------------------------------------------------------------- ; ------------------------------------------------------------- ;Functi on:CRCdate ;Input:BufStart(A,B,C)(一帧数据的起始地址)v_Count(要做CRC的字节数);Output:CRC16_HighCRC16_Low(结果); ------------------------------------------------------------- CRC_Data: clrfCRC16_High clrfCRC16_Low CRC_Data10 movfINDF,w

CRC校验解读

三种常用的CRC16校验算法的C51程序的优化2009-10-10 09:34:17| 分类:技术知识| 标签:|字号大 CRC校验又称为循环冗余校验,是数据通讯中常用的一种校验算法。它可以有效的判别出数据在传输过程中是否发生了错误,从而保障了传输的数据可靠性。 CRC校验有多种方式,如:CRC8、CRC16、CRC32等等。在实际使用中,我们经常使用CRC16校验。CRC16校验也有多种,如:1005多项式、1021多项式(CRC-ITU)等。在这里我们不讨论CRC算法是怎样产生的,而是重点落在几种算法的C51程序的优化上。 计算CRC校验时,最常用的计算方式有三种:查表、计算、查表+计算。一般来说,查表法最快,但是需要较大的空间存放表格;计算法最慢,但是代码最简洁、占用空间最小;而在既要求速度,空间又比较紧张时常用查表+计算法。 下面我们分别就这三种方法进行讨论和比较。这里以使用广泛的51单片机为例,分别用查表、计算、查表+计算三种方法计算1021多项式(CRC-ITU)校验。原始程序都是在网上或杂志上经常能见到的,相信大家也比较熟悉了,甚至就是正在使用或已经使用过的程序。 编译平台采用Keil C51 7.0,使用小内存模式,编译器默认的优化方式。 常用的查表法程序如下,这是网上经常能够看到的程序范例。因为篇幅关系,省略了大部分表格的内容。 code unsigned int Crc1021Table[256] = { 0x0000, 0x1021, 0x2042, 0x3063,... 0x1ef0 }; unsigned int crc0(unsigned char *pData, unsigned char nLength) { unsigned int CRC16 = 0;

crc校验码计算例题

crc校验码计算例题 1、若信息码字为11100011,生成多项式G(X)=X5+X4+X+1,则计算出的CRC 校验码为?x的最高次幂5则信息码(被除数)补五个0为:1110001100000 除数为110011 ------------10110110 --------------------- 110011/1110001100000 -------110011 ------------------ ---------101111 ---------110011 ------------------ ----------111000 ----------110011 ------------------ ------------101100 ------------110011 ------------------------ -------------111110 -------------110011 ------------------------- ---------------11010 2、信息码为101110101,生成多项式X4+X2+1,求冗余位??? 算法同上被除数补四个0 为:1011101010000 除数为:10101 答案:1100 7E 00 05 60 31 32 33 计算CRC16结果应该是:5B3E 方法如下: CRC-16码由两个字节构成,在开始时CRC寄存器的每一位都预置为1,然后把CRC寄存器与8-bit的数据进行异或(异或:二进制运算相同为0,不同为1;0^0=0;0^1=1;1^0=1;1^1=0),之后对CRC寄存器从

CRC算法

CRC算法与实现bhw98 摘要: 本文首先讨论了CRC的代数学算法,然后以常见的CRC-ITU为例,通过硬件电路的实现,引出了比特型算法,最后重点介绍了字节型快速查表算法,给出了相应的C 语言实现。 关键词: CRC, FCS, 生成多项式, 检错重传 引言 CRC的全称为Cyclic Redundancy Check,中文名称为循环冗余校验。它是一类重要的线性分组码,编码和解码方法简单,检错和纠错能力强,在通信领域广泛地用于实现差错控制。实际上,除数据通信外,CRC在其它很多领域也是大有用武之地的。例如我们读软盘上的文件,以及解压一个ZIP文件时,偶尔会碰到“Bad CRC”错误,由此它在数据存储方面的应用可略见一斑。 差错控制理论是在代数理论基础上建立起来的。这里我们着眼于介绍CRC的算法与实现,对原理只能捎带说明一下。若需要进一步了解线性码、分组码、循环码、纠错编码等方面的原理,可以阅读有关资料。 利用CRC进行检错的过程可简单描述为:在发送端根据要传送的k位二进制码序列,以一定的规则产生一个校验用的r位监督码(CRC码),附在原始信息后边,构成一个新的二进制码序列数共k+r位,然后发送出去。在接收端,根据信息码和CRC码之间所遵循的规则进行检验,以确定传送中是否出错。这个规则,在差错控制理论中称为“生成多项式”。 1 代数学的一般性算法 在代数编码理论中,将一个码组表示为一个多项式,码组中各码元当作多项式的系数。例如1100101 表示为 1·x6+1·x5+0·x4+0·x3+1·x2+0·x+1,即x6+x5+x2+1。 设编码前的原始信息多项式为P(x),P(x)的最高幂次加1等于k;生成多项式为G(x),G(x)的最高幂次等于r;CRC多项式为R(x);编码后的带CRC的信息多项式为T(x)。 发送方编码方法:将P(x)乘以xr(即对应的二进制码序列左移r位),再除以G(x),所得余式即为R(x)。用公式表示为 T(x)=x r P(x)+R(x) 接收方解码方法:将T(x)除以G(x),如果余数为0,则说明传输中无错误发生,否则说

查表法计算CRC

在硬件实现中,CRC 通常采用线性反馈移位寄存器实现。其中一个单元对应CRC 的每一比特,图3-2给出了8比特寄存器。对于移位寄存器中的每一单元,如果在发生器多项式中D 的某次幂为1,那么到下一个单元的连接要经过一个异或门(XOR)。对于每一传输块,首先将移位寄存器置零;接传输块数据输入移位寄存器,当传输块的所有比特全部输入移位寄存器后,移位寄存器的存储内容就是所要求的CRC 比特。这些比特以倒序传输,如图3-2,首先传输在最左寄存器中的CRC 比特。 图3-2 8比特CRC 生成移位寄存器 对于上述算法,当输入1个比特时,要经过一系列的异或和移位,才能完成。上图只是8比特CRC 的实现图,考虑到g CRC24A (D)的多项式,实现更为复杂。而下行峰值速率又相对很高,采用这种方法显然是达不到需求的速率的。下面介绍一种更为高效的查表法[17],多核DSP 计算CRC 也使用了查表法。 设传输块有k 比特,CRC 比特数为k n -;下面是按4比特查表计算24比特CRC 的过程。对于传输块中的二进制序列,可以用下面的多项式表示: ()1011222k k k k m x m m m m --=++++ 式(3-1) 将上式每4个比特组合在一起,如下所示: ()44(1)4011222n n n n m x m m m m --=++ ++ 式(3-2) 求此序列的24比特CRC 时,先乘以242(左移24位)后,再除以CRC 的生成多项式()x g ,所得到的余数即为所求的CRC 码。如下式所示: ()()()() () 242424 2444(1) 01222222n n n m x m m m g x g x g x g x -=+++ 式(3-3) 设:()()()()24 0002r x m Q x g x g x =+ ,其中()0r x 为24位二进制余数;将它代入式(3-3)可得: ()()()()()()()()()()()()2424 24044(1)1042424 044(1)102222222222 n n n n n n m x r x m m Q x g x g x g x g x r x m m Q x g x g x g x --??=++++??? ?????=++++?????? 式(3-4) 因为,()()()()()4204244000002[2]222h l h l r x r x r x r x r x =+=+ 式(3-5)

16位CRC算法原理及C语言实现

按字节计算CRC unsigned int cal_crc(unsigned char *ptr,unsigned char len) { unsigned int crc; unsigned char da; unsigned int crc_ta[256]={/*CRC余式表*/ 0x0000,0x1021,0x2042,0x3063,0x4084,0x50a5,0x60c6,0x70e7, 0x8108,0x9129,0xa14a,0xb16b,0xc18c,0xd1ad,0xe1ce,0xf1ef, 0x1231,0x0210,0x3273,0x2252,0x52b5,0x4294,0x72f7,0x62d6, 0x9339,0x8318,0xb37b,0xa35a,0xd3bd,0xc39c,0xf3ff,0xe3de, 0x2462,0x3443,0x0420,0x1401,0x64e6,0x74c7,0x44a4,0x5485, 0xa56a,0xb54b,0x8528,0x9509,0xe5ee,0xf5cf,0xc5ac,0xd58d, 0x3653,0x2672,0x1611,0x0630,0x76d7,0x66f6,0x5695,0x46b4, 0xb75b,0xa77a,0x9719,0x8738,0xf7df,0xe7fe,0xd79d,0xc7bc, 0x48c4,0x58e5,0x6886,0x78a7,0x0840,0x1861,0x2802,0x3823, 0xc9cc,0xd9ed,0xe98e,0xf9af,0x8948,0x9969,0xa90a,0xb92b, 0x5af5,0x4ad4,0x7ab7,0x6a96,0x1a71,0x0a50,0x3a33,0x2a12, 0xdbfd,0xcbdc,0xfbbf,0xeb9e,0x9b79,0x8b58,0xbb3b,0xab1a, 0x6ca6,0x7c87,0x4ce4,0x5cc5,0x2c22,0x3c03,0x0c60,0x1c41, 0xedae,0xfd8f,0xcdec,0xddcd,0xad2a,0xbd0b,0x8d68,0x9d49, 0x7e97,0x6eb6,0x5ed5,0x4ef4,0x3e13,0x2e32,0x1e51,0x0e70, 0xff9f,0xefbe,0xdfdd,0xcffc,0xbf1b,0xaf3a,0x9f59,0x8f78, 0x9188,0x81a9,0xb1ca,0xa1eb,0xd10c,0xc12d,0xf14e,0xe16f, 0x1080,0x00a1,0x30c2,0x20e3,0x5004,0x4025,0x7046,0x6067, 0x83b9,0x9398,0xa3fb,0xb3da,0xc33d,0xd31c,0xe37f,0xf35e, 0x02b1,0x1290,0x22f3,0x32d2,0x4235,0x5214,0x6277,0x7256, 0xb5ea,0xa5cb,0x95a8,0x8589,0xf56e,0xe54f,0xd52c,0xc50d, 0x34e2,0x24c3,0x14a0,0x0481,0x7466,0x6447,0x5424,0x4405, 0xa7db,0xb7fa,0x8799,0x97b8,0xe75f,0xf77e,0xc71d,0xd73c, 0x26d3,0x36f2,0x0691,0x16b0,0x6657,0x7676,0x4615,0x5634,

modbus_rtu_crc计算方法

MODBUS RTU模式下的CRC方法 使用RTU模式,消息包括了一基于CRC方法的错误检测域。CRC域检测了整个消息的内容。 CRC域是两个字节,包含一16位的二进制值。它由传输设备计算后加入到消息中。接收设备重新计算收到消息的CRC,并与接收到的CRC域中的值比较,如果两值不同,则有误。 CRC是先调入一值是全“1”的16位寄存器,然后调用一过程将消息中连续的8位字节各当前寄存器中的值进行处理。仅每个字符中的8Bit数据对CRC有效,起始位和停止位以及奇偶校验位均无效。 CRC产生过程中,每个8位字符都单独和寄存器内容相或(O R),结果向最低有效位方向移动,最高有效位以0填充。L SB被提取出来检测,如果LSB为1,寄存器单独和预置的值或一下,如果LSB为0,则不进行。整个过程要重复8次。在最后一位(第8位)完成后,下一个8位字节又单独和寄存器的当前值相或。最终寄存器中的值,是消息中所有的字节都执行之后的C RC值。 CRC添加到消息中时,低字节先加入,然后高字节。CRC简单函数如下: unsigned short CRC16(puchMsg, usDataLen) unsigned char *puchMsg ; /* 要进行CRC校验的消息 */ unsigned short usDataLen ; /* 消息中字节数 */ { unsigned char uchCRCHi = 0xFF ; /* 高CRC字节初始化 */ unsigned char uchCRCLo = 0xFF ; /* 低CRC 字节初始化 */ unsigned uIndex ; /* CRC循环中的索引 */ while (usDataLen--) /* 传输消息缓冲区 */

CRC16校验码如何计算

CRC16校验码如何计算 比如我有一个16进制只字符串 7E 00 05 60 31 32 33 要在末尾添加两个CRC16校验码校验这7个16进制字符请写出算法和答案 7E 00 05 60 31 32 33 计算CRC16结果应该是:5B3E 方法如下: 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(16位)多项式为 X16+X15+X2+1,其对应校验二进制位列为1 1000 0000 0000 0101。

CRC校验实用程序库(一)

CRC校验实用程序库(一) 在数据存储和数据通讯领域,为了保证数据的正确,就不得不采用检错的手段。在诸多检错手段中,CRC是最著名的一种。CRC的全称是循环冗余校验,其特点是:检错能力极强,开销小,易于用编码器及检测电路实现。从其检错能力来看,它所不能发现的错误的几率仅为0.0047%以下。从性能上和开销上考虑,均远远优于奇偶校验及算术和校验等方式。因而,在数据存储和数据通讯领域,CRC无处不在:著名的通讯协议X.25的FCS(帧检错序列)采用的是CRC-CCITT,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程序库*/ #defineCRCCCITT0x1021 #defineCCITT-REV0x8408 #defineCRC160x8005 #defineCRC16-REV0xA001 #defineCRC32-POLYNOMIAL0xEDB88320L /*以上为CRC除数的定义*/ #defineNIL0 #definecrcupdate(d,a,t)*(a)=(*(a)>8)^(d)]; #definecrcupdate16(d,a,t)*(a)=(*(a)>>8^(t)(*(a)^(d))&0x00ff]) /*以上两个宏可以代替函数crcupdate和crcrevupdate*/ #include #include

CRC_校验码的计算方法

CRC 校验码的计算方法 CRC从原理到实现=============== 作者:Spark Huang(hcpp@https://www.doczj.com/doc/3d6329379.html,) 日期:2004/12/8 摘要:CRC(Cyclic Redundancy Check)被广泛用于数据通信过程中的差错检测,具有很强的检错能力。本文详细介绍了CRC的基本原理,并且按照解释通行的查表算法的由来的思路介绍了各种具体的实现方法。 1.差错检测 数据通信中,接收端需要检测在传输过程中是否发生差错,常用的技术有奇偶校验(Parity Check),校验和(Checksum)和CRC(Cyclic Redundancy Check)。它们都是发送端对消息按照某种算法计算出校验码,然后将校验码和消息一起发送到接收端。接收端对接收到的消息按照相同算法得出校验码,再与接收到的校验码比较,以判断接收到消息是否正确。 奇偶校验只需要1位校验码,其计算方法也很简单。以奇检验为例,发送端只需要对所有消息位进行异或运算,得出的值如果是0,则校验码为1,否则为0。接收端可以对消息进行相同计算,然后比较校验码。也可以对消息连同校验码一起计算,若值是0则有差错,否则校验通过。 通常说奇偶校验可以检测出1位差错,实际上它可以检测出任何奇数位差错。 校验和的思想也很简单,将传输的消息当成8位(或16/32位)整数的序列,将这些整数加起来而得出校验码,该校验码也叫校验和。校验和被用在IP协议中,按照16位整数运算,而且其MSB(Most Significant Bit)的进位被加到结果中。 显然,奇偶校验和校验和都有明显的不足。奇偶校验不能检测出偶数位差错。对于校验和,如果整数序列中有两个整数出错,一个增加了一定的值,另一个减小了相同的值,这种差错就检测不出来。 2.CRC算法的基本原理------------------- CRC算法的是以GF(2)(2元素伽罗瓦域)多项式算术为数学基础的,听起来很恐怖,但实际上它 的主要特点和运算规则是很好理解的。 GF(2)多项式中只有一个变量x,其系数也只有0和1,如: 1*x^7 + 0*x^6 + 1*x^5 + 0*x^4 + 0*x^3 + 1*x^2 +1*x^1 + 1*x^0

CRC16 三种算法及c实现

标准CRC生成多项式如下表: 名称生成多项式简记式* 标准引用 CRC-4 x4+x+1 3 ITU G.704 CRC-8 x8+x5+x4+1 0x31 CRC-8 x8+x2+x1+1 0x07 CRC-8 x8+x6+x4+x3+x2+x1 0x5E CRC-12 x12+x11+x3+x+1 80F CRC-16 x16+x15+x2+1 8005 IBM SDLC CRC16-CCITT x16+x12+x5+1 1021 ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCS CRC-32 x32+x26+x23+...+x2+x+1 04C11DB7 ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCS CRC-32c x32+x28+x27+...+x8+x6+1 1EDC6F41 SCTP 生成多项式的最高位固定的1,故在简记式中忽略最高位1了,如0x1021实际是0x11021。 I、基本算法(人工笔算): 以CRC16-CCITT为例进行说明,CRC校验码为16位,生成多项式17位。假如数据流为4字节:BYTE[3]、BYTE[2]、BYTE[1]、BYTE[0]; 数据流左移16位,相当于扩大256×256倍,再除以生成多项式0x11021,做不借位的除法运算(相当于按位异或),所得的余数就是CRC校验码。 发送时的数据流为6字节:BYTE[3]、BYTE[2]、BYTE[1]、BYTE[0]、CRC[1]、CRC[0]; 注意:使用长除法进行计算式,需要将除数多项式与预置位0x0000或0xFFFF异或以后再进行计算。II、计算机算法1(比特型算法): 1)将扩大后的数据流(6字节)高16位(BYTE[3]、BYTE[2])放入一个长度为16的寄存器; 2)如果寄存器的首位为1,将寄存器左移1位(寄存器的最低位从下一个字节获得),再与生成多项式的简记式异或; 否则仅将寄存器左移1位(寄存器的最低位从下一个字节获得); 3)重复第2步,直到数据流(6字节)全部移入寄存器; 4)寄存器中的值则为CRC校验码CRC[1]、CRC[0]。

CCITT CRC-16计算原理与实现

CCITT CRC-16计算原理与实现 CRC的全称为Cyclic Redundancy Check,中文名称为循环冗余校验。它是一类重要的线性分组码,编码和解码方法简单,检错和纠错能力强,在通信领域广泛地用于实现差错控制。实际上,除数据通信外,CRC在其它很多领域也是大有用武之地的。例如我们读软盘上的文件,以及解压一个ZIP文件时,偶尔会碰到“Bad CRC”错误,由此它在数据存储方面的应用可略见一斑。 差错控制理论是在代数理论基础上建立起来的。这里我们着眼于介绍CRC的算法与实现,对原理只能捎带说明一下。若需要进一步了解线性码、分组码、循环码、纠错编码等方面的原理,可以阅读有关资料。 利用CRC进行检错的过程可简单描述为:在发送端根据要传送的k位二进制码序列,以一定的规则产生一个校验用的r位监督码(CRC码),附在原始信息后边,构成一个新的二进制码序列数共k+r位,然后发送出去。在接收端,根据信息码和CRC码之间所遵循的规则进行检验,以确定传送中是否出错。这个规则,在差错控制理论中称为“生成多项式”。 1 代数学的一般性算法 在代数编码理论中,将一个码组表示为一个多项式,码组中各码元当作多项式的系数。例如 1100101 表示为 1·x6+1·x5+0·x4+0·x3+1·x2+0·x+1,即 x6+x5+x2+1。 设编码前的原始信息多项式为P(x),P(x)的最高幂次加1等于k;生成多项式为G(x),G(x)的最高幂次等于r;CRC多项式为R(x);编码后的带CRC的信息多项式为T(x)。 发送方编码方法:将P(x)乘以xr(即对应的二进制码序列左移r位),再除以 G(x),所得余式即为R(x)。用公式表示为 T(x)=xrP(x)+R(x) 接收方解码方法:将T(x)除以G(x),如果余数为0,则说明传输中无错误发生,否则说明传输有误。 举例来说,设信息码为1100,生成多项式为1011,即P(x)=x3+x2,G(x)=x3+x+1,计算CRC的过程为 xrP(x) x3(x3+x2) x6+x5 x -------

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位

16位CRC校验码计算程序

/*************************************************************** 16位CRC计算方法 1.预置1个16位的寄存器为十六进制FFFF(即全为1);称此寄存器为CRC寄存器;2.把第一个8位二进制数据(既通讯信息帧的第一个字节)与16位的CRC寄存器的低8位相异或,把结果放于CRC寄存器; 3.把CRC寄存器的内容右移一位(朝低位)用0填补最高位,并检查右移后的移出位;4.如果移出位为0:重复第3步(再次右移一位); 如果移出位为1:CRC寄存器与多项式A001(1010 0000 0000 0001)进行异或;5.重复步骤3和4,直到右移8次,这样整个8位数据全部进行了处理; 6.重复步骤2到步骤5,进行通讯信息帧下一个字节的处理; 7.将该通讯信息帧所有字节按上述步骤计算完成后,得到的16位CRC; *****************************************************************/ /**************************************************************************** 名称: UART_CRC16_Work() 说明: CRC16校验程序 参数: *CRC_Buf:数据地址 CRC_Leni:数据长度 返回: CRC_Sumx:校验值 *****************************************************************************/ unsigned int UART_CRC16_Work(unsigned char *CRC_Buf,unsigned char CRC_Leni) { unsigned char i,j; unsigned int CRC_Sumx; CRC_Sumx=0xFFFF; for(i=0;i>=1; CRC_Sumx^=0xA001; } else

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原理 及算法总结

引言 CRC 的全称为Cyclic Redundancy Check ,中文名称为循环冗余校验。它是一类重要的线性分组码,编码和解码方法简单,检错和纠错能力强,在通信领域广泛地用于实现差错控制。实际上,除数据通信外,CRC 在其它很多领域也是大有用武之地的。例如我们读软盘上的文件,以及解压一个ZIP 文件时,偶尔会碰到“Bad CRC ”错误,由此它在数据存储方面的应用可略见一斑。 CRC 的算法与实现,对原理只能捎带说明一下。若需要进一步了解线性码、分组码、循环码、纠错编码等方面的原理,可以阅读有关资料。 利用CRC 进行检错的过程可简单描述为: k 位二进制码序列,以一定的规则产生一个校验用的r 位监督码(CRC 码),附在原始信息后边,构成一个新的二进制码序列数共k+r 位, 然后发送出去。 CRC 码之间所遵循的规则进行检验,以确定传送中是否出错。这个规则,在差错控制理论中称为“生成多项式”。 1 代数学的一般性算法 在代数编码理论中,将一个码组表示为一个多项式,码组中各码元当作多项式的系数。例如 1100101 表示为 1·x^6+1·x^5+0·x^4+0·x^3+1·x^2+0·x+1,即 x^6+x^5+x^2+1。 设: 编码前的原始信息多项式为P(x),P(x)的最高幂次加1等于k ; 生成多项式为G(x),G(x)的最高幂次等于r ; CRC 多项式为R(x); 编码后的带CRC 的信息多项式为T(x)。 发送方编码方法: 将P(x)乘以x^r(即对应的二进制码序列左移r 位),再除以G(x),所得余式即为R(x)。用公式表示为 ()()()r T x x P x R x =+ 接收方解码方法: 将T(x)除以G(x),如果余数为0,则说明传输中无错误发生,否则说明传输有误。 举例来说,设信息码为1100,生成多项式为1011,即P(x)=x3+x2,G(x)=x3+x+1,计算CRC 的过程为 ()()()()3326532333 111 r x x x x P x x x x x x x G x x x x x x x ++==+++++++++= 即 R(x)=x 。注意到G(x)最高幂次r=3,得出CRC 为010。

CRC 三种检验方法

计算机网络报告 CRC 三种检验方法 CRC 三种检验方法: //CRC16校验在通讯中应用广泛,这里不对其理论进行讨论,只对常见的3种//实现方法进行测试。方法1选用了一种常见的查表方法,类似的还有512字//节、256字等查找表的,至于查找表的生成,这里也略过。 // ---------------- POPULAR POL YNOMIALS ----------------

// CCITT: x^16 + x^12 + x^5 + x^0 (0x1021) // CRC-16: x^16 + x^15 + x^2 + x^0 (0x8005) #define CRC_16_POL YNOMIALS 0x8005 // -------------------------------------------------------------- // CRC16计算方法1:使用2个256长度的校验表 // -------------------------------------------------------------- const BYTE chCRCHTalbe[] = // CRC 高位字节值表{ 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40 }; const BYTE chCRCLTalbe[] = // CRC 低位字节值表{ 0x00, 0xC0, 0xC1, 0x01, 0xC3, 0x03, 0x02, 0xC2, 0xC6, 0x06, 0x07, 0xC7, 0x05, 0xC5, 0xC4, 0x04, 0xCC, 0x0C, 0x0D, 0xCD, 0x0F, 0xCF, 0xCE, 0x0E, 0x0A, 0xCA, 0xCB, 0x0B, 0xC9, 0x09, 0x08, 0xC8, 0xD8, 0x18, 0x19, 0xD9, 0x1B, 0xDB, 0xDA, 0x1A, 0x1E, 0xDE, 0xDF, 0x1F, 0xDD, 0x1D, 0x1C, 0xDC, 0x14, 0xD4, 0xD5, 0x15, 0xD7, 0x17, 0x16, 0xD6, 0xD2, 0x12, 0x13, 0xD3, 0x11, 0xD1, 0xD0, 0x10, 0xF0, 0x30, 0x31, 0xF1, 0x33, 0xF3, 0xF2, 0x32, 0x36, 0xF6, 0xF7, 0x37, 0xF5, 0x35, 0x34, 0xF4, 0x3C, 0xFC, 0xFD, 0x3D, 0xFF, 0x3F, 0x3E, 0xFE, 0xFA, 0x3A, 0x3B, 0xFB, 0x39, 0xF9, 0xF8, 0x38, 0x28, 0xE8, 0xE9, 0x29, 0xEB, 0x2B, 0x2A, 0xEA, 0xEE, 0x2E, 0x2F, 0xEF,

相关主题
相关文档 最新文档