利用C语言实现循环冗余校验码的方法

杨俊春

(1.北京控制工程研究所，北京100190;2.空间智能控制技术重点实验室，北京100190)

利用C语言实现循环冗余校验码的方法

杨俊春

(1.北京控制工程研究所，北京100190;2.空间智能控制技术重点实验室，北京100190)

给出了一种利用C语言实现循环冗余校验码(CRC)的方法并将其应用到卫星控制系统中.首先介绍了CRC校验码的原理，在此基础上推导了计算多字节数据序列CRC校验码的递推算法，然后给出了算法的C语言实现，最后将其应用到卫星控制系统中.试验数据表明给出的CRC算法实现能够灵敏的检测出数据传输过程中产生的错误.

卫星;控制系统;CRC;C语言;

卫星控制系统需要实时处理地面发送的遥控指令以及遥测下传星上的各种参数供地面判读，遥控指令和遥测参数均通过星地通信链路进行传输.由于受到各种电磁干扰的影响，数据在传输过程中会发生不可预知的变化，造成接收到的数据和实际发送的数据不一致.卫星控制系统如果不能及时正确的处理地面发送的遥控指令，或者下传的遥测参数显示错误而导致地面做出错误的决定，这些都可能对卫星造成致命的影响.因此，为了保证通信的可靠性，必须采用差错检测.常用的差错检测机制有:奇偶校验、校验和校验、海明码校验、循环冗余校验(CRC校验)，其中CRC校验的检错能力最强[1-2].本文推导了计算多字节数据序列CRC校验码的递推算法，并给出了软件的C语言实现及其在卫星控制系统中的应用.试验数据表明给出的CRC算法实现能够灵敏的检测出数据传输过程中产生的错误.

1 CRC校验码的原理

生成CRC码的基本原理[3]是任意一组由二进制数组成的代码都可以和一系列仅为0和1取值的多项式一一对应.例如代码1010111对应的多项式为x6+x4+x2+x+1.CRC码集选择的原则是:若码字长度为n，其中信息字段为k位，校验字段为r位(n=k+r)，则对于CRC码集中的任一码字，存在且仅存在一个r次多项式G(x)，使得

其中M(x)为k次信息多项式，R(x)为r次校验多项式.通常将G(x)称为生成多项式，所有合法的码字都可以由G(x)所生成.数据通信的发送方通过指定的G(x)产生CRC码字，接收方通过该G(x)来验证收到的CRC码字.

1.1 CRC校验码的算法[4-7]

当传送k位信息:M=(mk-1，mk-2，…，m1，m0)，若将其视为一多项式系数，它对应的多项式为:M(x)=mk-1xk-1+mk-2xk-2+…+m1x+m0.在信息码的后面添加r个0，可构成多项式xrM(x)=mk-1xr+k-1+mk-2xr+k-2+…+m1xr+1+m0xr.将其作为被除式，选择一个r次的生成多项式G(x)=grxr+gr-1xr-1+…+g1x+g0来除，得到一个商式Q(x)和余式R(x)，即

上式中xrM(x)表示将数据系列左移r位，Q(x)代表这一除法所得到的商，R(x)为所需的余式，它表示的r位信息就是所需的校验码.在CRC编码过程中，四则运算采用模2运算，即不考虑借位和进位，加减都相当于异或运算.因此，对式(2)进行整理可得到

xr.M(x)+R(x)=Q(x).G(x)(3)从式(3)可以看出，将r位的校验码附在k位数据位的后面所得到的k+r数据作为系数所表示的多项式是生成多项式G(x)的整数倍，即余数为0.在数据接收端接收到k+r位数据后，进行校验，如果它表示的多项式能被G(x)整除，则表示通信正常，否则，表示数据传输有误，达到检错的目的.

1.2 多字节数据序列校验

为了讨论方便，下面介绍16位CRC校验码的计算方法.假设需要传送一组k个字节的二进制序列Mk=[m1，m2，…，mk]，其中mi(i=1～k)为信息码中的各个字节.截取M中的前k-1个字节构成一个Mk-1序列:Mk-1=[m1，m2，…，mk-1]，则对应多项式Mk(x)和Mk-1(x)的关系可表示为

则

因为

将式(6)代入式(5)整理得

序列Mk-1的余式表示为Rk-1=hk-1lk-1，hk-1表示余式的高字节，lk-1为余式的低字节，则余式Rk-1对应的多项式表示为

将式(8)代入式(7)整理得

由式(8)～(9)可知，根据Rk-1和mk，可以求得Rk.具体算法为:取R1的高字节h1与m2进行异或得R′，再取R′的CRC码R″，R″的低字节即是R2的低字节，R″的高字节与R1的低字节l1进行异或得到R2的高字节.依次类推，可以求得Rk.算法实现流程如图1所示.

图1 多字节数据序列CRC码计算流程图

2 CRC校验码的C语言实现

2.1 单字节数据CRC校验码的程序实现

从上述推导中可知，在求多字节数据序列的CRC码时，要多次求取单字节的CRC码.因此，首先计算单字节数据的CRC码.这里以生成多项式G(x)=x16+x12+x5+1[8]为例，它对应的二进制数据为1 0001 0000 0010 0001.

定义m为单字节数据，g=0x1021为生成多项式，crc为CRC校验码，则:

crc=m左移8位

循环8次

如果crc的最高位为1，则

crc左移一位后与g异或

否则

crc左移一位

循环结束.

上述函数中m为需要计算CRC的1个字节数据，取值为0x00～0xFF，返回值crc即为m的CRC校验码.

2.2 多字节数据CRC校验码的程序实现

根据1.2节的推导，求取N字节数据CRC校验码时需要重复调用单字节数据CRC校验码的求取函数，下面给出计算多字节数据的CRC校验码伪代码描述，由于篇幅限制，省去C语言源代码.

调用单字节的CRC码计算程序，获得第一个字节的CRC校验码crc.

R1=crc

循环N次

取R1的高8位右移8位后与第二个字节异或，结果保存为临时变量temp

调用单字节的CRC码计算程序，获取temp的CRC码，结果保存为R-temp

R2=((R-temp的高8位)异或(R1的低8位左移8位))或(R-temp的低8位)

保留R2的低16位

R1=R2

循环结束.

求取N字节数据序列的CRC校验码共需调用N+1次单字节CRC码求取函数，最后返回值R1即为N字节数据序列的CRC码.

3 CRC算法在卫星上的应用

卫星发射以后，需要通过测控系统接收来自地面的遥控指令、控制参数等数据，为了保证接收数据的正确性，星上软件必须采取一定的方法对接收的数据进行差错检验.本文2.2节给出了计算任意字节数据序列的CRC函数，下面介绍其在卫星控制系统中的应用.卫星控制系统从缓冲区中取出来自测控系统的N字节数据，该数据的前N-2字节为有效信息码，后2个字节为CRC校验码.控制系统调用计算多字节数据CRC校验码的函数即可获得CRC校验码，若该校验码取值为0，则接收的数据正确，控制系统可以对其进行处理;若该校验码不为0，说明数据在传输过程中发生了错误，控制系统不能使用此数据.表1给出一组数据，验证CRC算法的检错能力.测控系统发送一帧16字节数据，其中最后两个字节为CRC校验码，所有数据均用16进制表示.

从表1可以看出，当控制系统接收的数据正确时，接收端计算的CRC校验码为0，当数据在传输过程中发生错误时，接收端计算的CRC校验码不为0，可见给出的CRC算法能灵敏的检测出通信错误.

表1 试验数据

4 结 论

本文推导了CRC算法，给出了计算任意字节数据序列CRC校验码的C语言实现.将CRC算法封装为两个函数，使用时只需提供数据的字节数就可获得该数据序列的CRC校验码，模块独立，算法简洁.本文将CRC算法应用到卫星控制系统中，试验数据表明，该CRC算法能够有效的检测出通信过程中产生的数据错误.

[1] Joe C.串行通讯C程序员指南[M].徐定国，廖卫东译，北京:清华大学出版社，1990

[2] 熊贵喜.计算机网络(第三版)[M].北京:清华大学出版社，1998

[3] 李肇庆，韩涛.串行端口技术[M].北京:国防工业出版社，2004

[4] 王春森.程序员教程[M].北京:清华大学出版社，2001

[5] Peter K.Fast calculation of the number of minimum weigh twords of CRC codes[J].IEEE Transaction on Information Theory，2001，43(3):1190-1195

[6] Campobello G，Patane G，Russo M.Parrallel CRC realization[J].IEEE Transaction Computers，2003，52(10)，1312-1319

[7] Tanner M R.A recursive approach to low comp lexity codes[J].IEEE Transaction Information Theory，1981(27)，533-547

[8] Nguyen G D.Error detection codes:Algorithm and fast implementation[J].IEEE Transaction Computers，2005，54(1)，1-11

A Method of CRC Check Implemented by Using C Language

YANG Junchun
(1.Beijing Institute of Control Engineering，Beijing 100190，China;2.Science and Technology on Space Intelligent Control Laboratory，Beijing 100190，China)

A method of CRC(Cyclic Redundancy Code)check is implemented by C language in this paper and used in the satellite control system.First，the theory of CRC check is introduced.A recursive method is proposed to calculate the CRC of multi-byte data sequences.Then the algorithm is implemented by C language and used in the satellite control system.The test data shows that the CRC algorithm can check errors produced in data transmission sensitively.

satellite;control system;CRC;C language

V448

A

1674-1579(2011)05-0049-03

10.3969/j.issn.1674-1579.2011.05.010

2011-03-26

杨俊春(1979—)，女，四川人，高级工程师，研究方向为飞行器导航、制导与控制，卫星姿态与轨道控制(e-mail:yangjunchun@163.com).