当前位置:首页 >> 农林牧渔 >>

1 循环冗余校验码(CRC)


第八届工业仪表与自动化学术会议

工业控制系统中的 CRC 算法实现
邱继涛
(上海新华控制技术(集团)有限公司研发中心,上海 摘 201108)

要:针对工业控制系统中的特殊应用,提出利用 CRC(Cyclic Redundancy Check)校验方法提高通信可靠性,

并着重介绍了 CRC 校

验原理及在工业控制网络中的实现方法, 重点阐述了查表法的 CRC 实现, 同时给出余式项的 生成程序,进一步方便大家编写 CRC 校验程序。此计算方式已经在新华 TisNet 系统中成功应用,并取得了较好 的实时通信能力。 关键词:通信 CRC 余式项 TiSNet

0

引言

随着工业控制系统网络化的不断发展, 控制器同控制器间或控制器的某些部件之间的协调都 是通过网络来传输的,建立可靠、稳定、高速的通信网络已成为控制系统的必然要求,尤其是在 环境普遍比较恶劣的工业现场。然而,在数字通信中可靠与快速往往是一对矛盾。若要求快速, 则必然使得每个数据码元所占地时间缩短、波形变窄、能量减少,从而在受到干扰后产生错误的 可能性增加,传送信息的可靠性下降。若是要求可靠,则使得传送消息的速率变慢。因此,如何 合理地解决可靠性和速度这一对矛盾, 是正确设计一个工业通信网络的关键问题之一。 其中差错 检测和纠错控制是保证高可靠性的一种切实方法。在各种通信领域,多项式编码循环冗余码 CRC 简单且误判概率很低,被普遍应用。本文重点介绍 CRC 校验的原理及其算法实现。

1

循环冗余校验码(CRC)

多项式编码是基于将位串看成是系数为 0 或 1 的多项式,一个 k 位帧可以看成是从 X(k-1) 到 X(0)的 k-1 次多项式的系数序列。如果采用多项式编码的方式,发送方和接收方必须事先商 定一个生成多项式 G(x),生成多项式的高位和低位必须是 1。要计算 m 位的帧 M(x)的校验和, 生成多项式必须比该多项式短。基本思想是:将校验和加在帧的末尾,使这个带校验和的帧的多 项式能被 G(x)除尽。当接收方收到带校验和的帧时,用 G(x)去除它,如果有余数,则传输出错。 计算校验和算法如下: ① 设 G(x)为 r 阶,在帧的末尾附加 r 个零,使帧为 m+r 位,则相应的多项式是 XrM(x); ② 按模 2 除法用对应于 G(x)的位串去除对应于 XrM(x)的位串; ③ 按模 2 减法从对应于 XrM(x)的位串中减去余数,结果就是要传送带校验和的帧,叫多项 式 T(x)。 CRC 校验采用多项式编码方法。被处理的数据块可以看作是一个 n 阶的二进制多项式,由

a n ?1 x n ?1 + a n ? 2 x x ? 2 + ? ? ? + a1 x + a0 。如一个 8 位二进制数 10110101 可以表示为:

1x 7 + 0 x 6 + 1x 5 + 1x 4 + 0 x 3 + 1x 2 + 0 x + 1 。 多项式乘除法运算过程与普通代数多项式的乘除法
相同。多项式的加减法运算以 2 为模,加减时不进,错位,和逻辑异或运算一致。
1

第八届工业仪表与自动化学术会议

采用 CRC 校验时,发送方和接收方用同一个生成多项式 g(x),并且 g(x)的首位和最后一 位的系数必须为 1。CRC 的处理方法是:发送方以 g(x)去除 t(x) ,得到余数作为 CRC 校验码。 校验时,以计算的校正结果是否为 0 为据,判断数据帧是否出错。 以下 3 个多项式已经成为国际标准: CRC -12 = x^12+x^11+x^3+x^2+x+1 CRC -16 = x^16+x^15+x^2+1 CRC -CCITT = x^16+x^12+x^5+1 这 3 个多项式都包含了 x+1 作为基本因子。当字符串长度为 6 位时,使用 CRC-12;其余两 个多项式用在字符串长度为 8 位的情况下。一个 16 位的校验和,如 CRC-16 或 CRC-CCITT,可以 捕捉到所有的单位差错和双位差错、所有奇数位数的差错、所有长度小于或等于 16 位的突发差 错、 99.997%的长度为 17 位的突发差错以及 99.998%的长度为 18 位或多于 18 位的突发差错。 CRC 校验可以 100%地检测出所有奇数个随机错误和长度小于等于 k(k 为 g(x)的阶数)的突发错 误。所以 CRC 的生成多项式的阶数越高,误判的概率就越小。采用 16 位 CRC 校验,可以保证在 14 10 bit 码元中只含有一位未被检测出的错误。 IBM 的同步数据链路控制规程 SDLC 的帧校验序 在 列 FCS 中,使用 CRC-16;而在 CCITT 推荐的高级数据链路控制规程 HDLC 的帧校验序列 FCS 中, -5 使用 CCITT-16。由于采用 CRC-32 出错的概率比 CRC-16 低 10 倍,把 CRC-32 用于重要数据传输 十分合适,所以在通信、计算机等领域运用十分广泛。在一些 UART 通信控制芯片(如 MC6582、 Intel8273 和 Z80-SIO)内,都采用了 CRC 校验码进行差错控制。

2
2.1

CRC 计算在单片机系统上的实现

硬件电路的实现方法 多项式除法可用除法电路来实现。除法电路的主体由一组移位寄存器和模 2 加法器(异或单 元)组成。以 CRC-16 为例,它由 16 级移位寄存器和 3 个加法器组成,如图 1 所示(编码/解码共 用)。编码、解码前将各寄存器初始化为"1",信息位随着时钟移入。当信息位全部输入后,从寄 存器组输出 CRC 结果。

15 14



13 12 11 10 9

8

7

6

5

4

3

2

1



0



数据贞

图1

CRC-16 硬件实现

上述硬件实现方式完全可以用软件模拟。定义一个寄存器组,初始化为全"1"。依照电路图, 每输入一个信息位相当于一个时钟脉冲到来,从高到低依次移位。移位前信息位与 bit0 相加产 生临时位,其中 bit15 移入临时位,bit10、bit3 还要加上临时位。当全部信息位输入完成后, 从寄存器组取出它们的值,这就是 CRC 码。 2.2 字节形式进行的 CRC 运算 比特型算法逐位进行运算,效率比较低,不适用于高速通信的场合。数字通信系统(各种通
2

第八届工业仪表与自动化学术会议

信标准)一般是对一帧数据进行 CRC 校验,而字节是帧的基本单位。最常用的是一种按字节查表 的快速算法。该算法基于这样一个事实:计算本字节后的 CRC 码,等于上一字节余式 CRC 码的低 8 位左移 8 位,加上上一字节 CRC 右移 8 位和本字节之和后所求得的 CRC 码。如果我们把 8 位二 进制序列数的 CRC(共 256 个)全部计算出来,放在一个表里 ,编码时只要从表中查找对应的值 进行处理即可,此种方法被称作字节型算法。 CRC-16 的计算算法如下: ① 寄存器组初始化为全"1"(0xFFFF); ② 寄存器组向右移动一个字节; ③ 刚移出的那个字节与数据字节进行异或运算,得出一个指向值表的索引; ④ 索引所指的表值与寄存器组做异或运算; ⑤ 数据指针加 1,如果数据没有全部处理完,则重复步骤②; ⑥ 寄存器组取反,得到 CRC,附加在数据之后。 CRC-16 的验证算法如下: ① 寄存器组初始化为全"1"(0xFFFF); ② 寄存器组向右移动一个字节; ③ 刚移出的那个字节与数据字节进行异或运算,得出一个指向值表的索引; ④ 索引所指的表值与寄存器组做异或运算; ⑤ 数据指针加 1,如果数据没有全部处理完,则重复步骤②(数据包括 CRC 的两个字节); ⑥ 寄存器组的值是否等于 (0xF0B8),若相等则通过,否则失败。 2.3 余式表的生成 根据上述算法,CRC 校验程序需要事先计算余式表,根据不同的生成多项式,可算出对应的 余式表,其程序基本大同小异。下面给出了余式表的生成程序,此程序已在 C++BUILDER 上调试 通过。如果需要,仅对其中部分节选就可在单片机上生成。 #include <vcl.h> #pragma hdrstop #include "crcb.h" //--------------------------------------------------------------------------#pragma package(smart_init) #pragma resource "*.dfm" TForm1 *Form1; #include <stdio.h> unsigned int crc32_table[256]; unsigned int baseValue = 0x8005;//0x04c11db7; unsigned int Reflect(unsigned int ref, char ch) { unsigned int value(0); // 交换 bit0 和 bit7,bit1 和 bit6,类推 for(int i = 1; i < (ch + 1); i++) { if(ref & 1)
3

第八届工业仪表与自动化学术会议

value |= 1 << (ch - i); ref >>= 1; } return value; } void init_crc_table() { unsigned int crc,temp; // 256 个值 for(int i = 0; i <= 0xfF; i++) { temp=Reflect(i, 8); crc_table[i]= temp<< 8; for (int j = 0; j < 8; j++) { unsigned long int t1,t2; unsigned int flag=crc_table[i]&0x8000; t1=(crc_table[i] << 1); if(flag==0) t2=0; else t2=baseValue; crc_table[i] =t1^t2 ; } crc=crc_table[i]&0x0ffff; crc_table[i] = Reflect(crc_table[i],16)&0x0ffff; } } //--------------------------------------------------------------------------__fastcall TForm1::TForm1(TComponent* Owner) : TForm(Owner) { } //---------------------------------------------------------------------------

void __fastcall TForm1::Button1Click(TObject *Sender) { init_crc_table(); char buffer[80];
4

第八届工业仪表与自动化学术会议

puts(buffer); for(int i=0;i<256;i++) { sprintf(buffer, "** %x", crc_table[i]); Memo1->Lines->Add(IntToStr(i)+"**"+buffer);//IntToStr(crc_table[i])) ; } } 该程序生成的 CRC-16 余式表如下: 0x0000,0xc0c1,0xc181,0x0140,0xc301,0x03c0,0x0280,0xc241, 0xc601,0x06c0,0x0780,0xc741,0x0500,0xc5c1,0xc481,0x0440, 0xcc01,0x0cc0,0x0d80,0xcd41,0x0f00,0xcfc1,0xce81,0x0e40, 0x0a00,0xcac1,0xcb81,0x0b40,0xc901,0x09c0,0x0880,0xc841, 0xd801,0x18c0,0x1980,0xd941,0x1b00,0xdbc1,0xda81,0x1a40, 0x1e00,0xdec1,0xdf81,0x1f40,0xdd01,0x1dc0,0x1c80,0xdc41, 0x1400,0xd4c1,0xd581,0x1540,0xd701,0x17c0,0x1680,0xd641, 0xd201,0x12c0,0x1380,0xd341,0x1100,0xd1c1,0xd081,0x1040, 0xf001,0x30c0,0x3180,0xf141,0x3300,0xf3c1,0xf281,0x3240, 0x3600,0xf6c1,0xf781,0x3740,0xf501,0x35c0,0x3480,0xf441, 0x3c00,0xfcc1,0xfd81,0x3d40,0xff01,0x3fc0,0x3e80,0xfe41, 0xfa01,0x3ac0,0x3b80,0xfb41,0x3900,0xf9c1,0xf881,0x3840, 0x2800,0xe8c1,0xe981,0x2940,0xeb01,0x2bc0,0x2a80,0xea41, 0xee01,0x2ec0,0x2f80,0xef41,0x2d00,0xedc1,0xec81,0x2c40, 0xe401,0x24c0,0x2580,0xe541,0x2700,0xe7c1,0xe681,0x2640, 0x2200,0xe2c1,0xe381,0x2340,0xe101,0x21c0,0x2080,0xe041, 0xa001,0x60c0,0x6180,0xa141,0x6300,0xa3c1,0xa281,0x6240, 0x6600,0xa6c1,0xa781,0x6740,0xa501,0x65c0,0x6480,0xa441, 0x6c00,0xacc1,0xad81,0x6d40,0xaf01,0x6fc0,0x6e80,0xae41, 0xaa01,0x6ac0,0x6b80,0xab41,0x6900,0xa9c1,0xa881,0x6840, 0x7800,0xb8c1,0xb981,0x7940,0xbb01,0x7bc0,0x7a80,0xba41, 0xbe01,0x7ec0,0x7f80,0xbf41,0x7d00,0xbdc1,0xbc81,0x7c40, 0xb401,0x74c0,0x7580,0xb541,0x7700,0xb7c1,0xb681,0x7640, 0x7200,0xb2c1,0xb381,0x7340,0xb101,0x71c0,0x7080,0xb041, 0x5000,0x90c1,0x9181,0x5140,0x9301,0x53c0,0x5280,0x9241, 0x9601,0x56c0,0x5780,0x9741,0x5500,0x95c1,0x9481,0x5440, 0x9c01,0x5cc0,0x5d80,0x9d41,0x5f00,0x9fc1,0x9e81,0x5e40, 0x5a00,0x9ac1,0x9b81,0x5b40,0x9901,0x59c0,0x5880,0x9841, 0x8801,0x48c0,0x4980,0x8941,0x4b00,0x8bc1,0x8a81,0x4a40,
5

第八届工业仪表与自动化学术会议

0x4e00,0x8ec1,0x8f81,0x4f40,0x8d01,0x4dc0,0x4c80,0x8c41, 0x4400,0x84c1,0x8581,0x4540,0x8701,0x47c0,0x4680,0x8641, 0x8201,0x42c0,0x4380,0x8341,0x4100,0x81c1,0x8081,0x4040

3

CRC 算法在新华 TiSNet 系统中的应用

为提高新华 TisNe 控制系统通信网络可靠性及实时性,系统通信算法中运用了字节形式的 CRC 查表递推运算, 并用上述程序生成了余式表, 嵌入到各通信子模块中, 实现了边通信边运算, 不会增加处理器的处理负荷, 既保证了数据的实时处理, 又可将实时信息及时通过网络传输到其 他模块中,实现了现场总线控制方式。新华 TiSNet 控制系统已经成功运用于石油、化工、造纸 等工业控制领域,系统运行稳定、可靠,再次验证了该算法之稳定与可行。

4

结束语

综上所述, 理论上 CRC 校验可以按算法定义利用多项式除法一步步推算出, 但这种方法程序 实现上须进行逐位异或和移位运算,若有 N 个字节数据,就进行 8N 次移位和 8N 次异或运算,而 且只有得到整个数据串后才能计算出 CRC 码, 这样就不能满足通信上的实时处理要求。 本文给出 了基于查表的递推算法,可以在得到每个字节时就进行运算,每次运算只需要两次异或运算,一 次位与和一次移位运算, 这样就可以极大满足工业控制系统实时处理的要求。 本计算方式已经在 新华 TisNet 系统中成功应用,并取得了较好的实时通信能力,为提高系统通信可靠性奠定了坚 实基础。
参考文献
1 2 3 ANDREW S.TANENBAUM,VRIJE UNIVERSITEIT,AMSTERDAM,THE NETHERLANDS 著,潘爱民译, 计算机网络.清华大学出版社. 循环冗余码 CRC 及其实现.微型电脑,1987.4. 顾尚杰.计算机通信网基础. 电子工业出版社.

6


相关文章:
循环冗余校验码的仿真与实现1
*** 实践教学 *** 兰州理工大学计算机与通信学院 2013 年秋季学期 《计算机通信与网络》 课程设计题 目: ( 15 ,11 )CRC 冗余校验码的编译码仿真实现通信工程...
循环冗余校验码(CRC)的基本原理
循环冗余校验码( 循环冗余校验码(CRC)的基本原理 ) 循环冗余校验码(CRC)的...解: (1) 将生成多项式 G(x)=x3+x+1 转换成对应的二进制除数 1011 。(2...
CRC循环冗余校验码
1循环冗余校验码(CRC 码,CRC=Cyclic Redundancy Check):是数据通信领域中最常用的 种差错校验码,其特征是信息字段和校验字段的长度可以任意选定。 2、生成 ...
循环冗余校验码
奇偶校验编码通过增加位校验位来使编码 中 1 的个数为奇数(奇校验)或者为...循环冗余校验码(CRC)的基本原理是:在 K 位信息码后再拼接 R 位的校验码,...
循环冗余校验码原理
1循环冗余校验码原理 CRC 校验采用多项式编码方法,如个 8 位二进制数(B7B6B5B4B3B2B1B0)可以用 7 阶二进制码多项式 B7X7+B6X6+B5X5+B4X4+B3X3+B...
CRC循环冗余校验码课设
《计算机通信》课程设计 题姓学成 目:循环冗余校验码(CRC)的编译码仿真实现通信工程(1)班 专业班级: 名: 号: 绩: 指导教师: 摘要 CRC 即循环冗余校验码(...
crc校验码 详细介绍看懂了就会了
详细介绍 循环冗余校验码(CRC)的基本原理是:在 K 位信息码后再拼接 R 位的...3 CRC 码的生成步骤 1、将 x 的最高次幂为 R 的生成多项式 G(x)转换成...
循环冗余校验码
简介CRC(Cyclic Redundancy Check)循环冗余校验码 是常用的校验码,在早期的通信中...编辑本段 例子例如: g(x)=x4+x3+x2+1,(7,3)码,信息码 110 产生的 ...
循环冗余校验码(CRC)
循环冗余校验码(CRC)_电子/电路_工程科技_专业资料。学习CRC的很好的资料CRC32 算法学习笔记以及如何用 java 实现 :说明 二:基本概念及相关介绍 2.1 什么是 ...
CRC32 冗余校验码的计算
CRC32 冗余校验码的计算_其它课程_小学教育_教育专区。西北工业大学 << 计算机...RC 即循环冗余校验码(Cyclic Redundancy Check[1] ):是数据 通信领域中最常用...
更多相关标签:
crc循环冗余校验码 | 循环冗余校验码 | 循环冗余校验码计算 | 循环冗余校验码例题 | 循环冗余校验码原理 | 循环冗余校验码 纠错 | 循环冗余校验码论文 | 循环冗余校验码c语言 |