利用C語言實(shí)現(xiàn)循環(huán)冗余校驗(yàn)碼的方法

楊俊春

(1.北京控制工程研究所，北京100190;2.空間智能控制技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京100190)

利用C語言實(shí)現(xiàn)循環(huán)冗余校驗(yàn)碼的方法

楊俊春

(1.北京控制工程研究所，北京100190;2.空間智能控制技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京100190)

給出了一種利用C語言實(shí)現(xiàn)循環(huán)冗余校驗(yàn)碼(CRC)的方法并將其應(yīng)用到衛(wèi)星控制系統(tǒng)中.首先介紹了CRC校驗(yàn)碼的原理，在此基礎(chǔ)上推導(dǎo)了計(jì)算多字節(jié)數(shù)據(jù)序列CRC校驗(yàn)碼的遞推算法，然后給出了算法的C語言實(shí)現(xiàn)，最后將其應(yīng)用到衛(wèi)星控制系統(tǒng)中.試驗(yàn)數(shù)據(jù)表明給出的CRC算法實(shí)現(xiàn)能夠靈敏的檢測出數(shù)據(jù)傳輸過程中產(chǎn)生的錯誤.

衛(wèi)星;控制系統(tǒng);CRC;C語言;

衛(wèi)星控制系統(tǒng)需要實(shí)時處理地面發(fā)送的遙控指令以及遙測下傳星上的各種參數(shù)供地面判讀，遙控指令和遙測參數(shù)均通過星地通信鏈路進(jìn)行傳輸.由于受到各種電磁干擾的影響，數(shù)據(jù)在傳輸過程中會發(fā)生不可預(yù)知的變化，造成接收到的數(shù)據(jù)和實(shí)際發(fā)送的數(shù)據(jù)不一致.衛(wèi)星控制系統(tǒng)如果不能及時正確的處理地面發(fā)送的遙控指令，或者下傳的遙測參數(shù)顯示錯誤而導(dǎo)致地面做出錯誤的決定，這些都可能對衛(wèi)星造成致命的影響.因此，為了保證通信的可靠性，必須采用差錯檢測.常用的差錯檢測機(jī)制有:奇偶校驗(yàn)、校驗(yàn)和校驗(yàn)、海明碼校驗(yàn)、循環(huán)冗余校驗(yàn)(CRC校驗(yàn))，其中CRC校驗(yàn)的檢錯能力最強(qiáng)[1-2].本文推導(dǎo)了計(jì)算多字節(jié)數(shù)據(jù)序列CRC校驗(yàn)碼的遞推算法，并給出了軟件的C語言實(shí)現(xiàn)及其在衛(wèi)星控制系統(tǒng)中的應(yīng)用.試驗(yàn)數(shù)據(jù)表明給出的CRC算法實(shí)現(xiàn)能夠靈敏的檢測出數(shù)據(jù)傳輸過程中產(chǎn)生的錯誤.

1 CRC校驗(yàn)碼的原理

生成CRC碼的基本原理[3]是任意一組由二進(jìn)制數(shù)組成的代碼都可以和一系列僅為0和1取值的多項(xiàng)式一一對應(yīng).例如代碼1010111對應(yīng)的多項(xiàng)式為x6+x4+x2+x+1.CRC碼集選擇的原則是:若碼字長度為n，其中信息字段為k位，校驗(yàn)字段為r位(n=k+r)，則對于CRC碼集中的任一碼字，存在且僅存在一個r次多項(xiàng)式G(x)，使得

其中M(x)為k次信息多項(xiàng)式，R(x)為r次校驗(yàn)多項(xiàng)式.通常將G(x)稱為生成多項(xiàng)式，所有合法的碼字都可以由G(x)所生成.數(shù)據(jù)通信的發(fā)送方通過指定的G(x)產(chǎn)生CRC碼字，接收方通過該G(x)來驗(yàn)證收到的CRC碼字.

1.1 CRC校驗(yàn)碼的算法[4-7]

當(dāng)傳送k位信息:M=(mk-1，mk-2，…，m1，m0)，若將其視為一多項(xiàng)式系數(shù)，它對應(yīng)的多項(xiàng)式為:M(x)=mk-1xk-1+mk-2xk-2+…+m1x+m0.在信息碼的后面添加r個0，可構(gòu)成多項(xiàng)式xrM(x)=mk-1xr+k-1+mk-2xr+k-2+…+m1xr+1+m0xr.將其作為被除式，選擇一個r次的生成多項(xiàng)式G(x)=grxr+gr-1xr-1+…+g1x+g0來除，得到一個商式Q(x)和余式R(x)，即

上式中xrM(x)表示將數(shù)據(jù)系列左移r位，Q(x)代表這一除法所得到的商，R(x)為所需的余式，它表示的r位信息就是所需的校驗(yàn)碼.在CRC編碼過程中，四則運(yùn)算采用模2運(yùn)算，即不考慮借位和進(jìn)位，加減都相當(dāng)于異或運(yùn)算.因此，對式(2)進(jìn)行整理可得到

xr.M(x)+R(x)=Q(x).G(x)(3)從式(3)可以看出，將r位的校驗(yàn)碼附在k位數(shù)據(jù)位的后面所得到的k+r數(shù)據(jù)作為系數(shù)所表示的多項(xiàng)式是生成多項(xiàng)式G(x)的整數(shù)倍，即余數(shù)為0.在數(shù)據(jù)接收端接收到k+r位數(shù)據(jù)后，進(jìn)行校驗(yàn)，如果它表示的多項(xiàng)式能被G(x)整除，則表示通信正常，否則，表示數(shù)據(jù)傳輸有誤，達(dá)到檢錯的目的.

1.2 多字節(jié)數(shù)據(jù)序列校驗(yàn)

為了討論方便，下面介紹16位CRC校驗(yàn)碼的計(jì)算方法.假設(shè)需要傳送一組k個字節(jié)的二進(jìn)制序列Mk=[m1，m2，…，mk]，其中mi(i=1～k)為信息碼中的各個字節(jié).截取M中的前k-1個字節(jié)構(gòu)成一個Mk-1序列:Mk-1=[m1，m2，…，mk-1]，則對應(yīng)多項(xiàng)式Mk(x)和Mk-1(x)的關(guān)系可表示為

則

因?yàn)?/p>

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

序列Mk-1的余式表示為Rk-1=hk-1lk-1，hk-1表示余式的高字節(jié)，lk-1為余式的低字節(jié)，則余式Rk-1對應(yīng)的多項(xiàng)式表示為

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

由式(8)～(9)可知，根據(jù)Rk-1和mk，可以求得Rk.具體算法為:取R1的高字節(jié)h1與m2進(jìn)行異或得R′，再取R′的CRC碼R″，R″的低字節(jié)即是R2的低字節(jié)，R″的高字節(jié)與R1的低字節(jié)l1進(jìn)行異或得到R2的高字節(jié).依次類推，可以求得Rk.算法實(shí)現(xiàn)流程如圖1所示.

圖1 多字節(jié)數(shù)據(jù)序列CRC碼計(jì)算流程圖

2 CRC校驗(yàn)碼的C語言實(shí)現(xiàn)

2.1 單字節(jié)數(shù)據(jù)CRC校驗(yàn)碼的程序?qū)崿F(xiàn)

從上述推導(dǎo)中可知，在求多字節(jié)數(shù)據(jù)序列的CRC碼時，要多次求取單字節(jié)的CRC碼.因此，首先計(jì)算單字節(jié)數(shù)據(jù)的CRC碼.這里以生成多項(xiàng)式G(x)=x16+x12+x5+1[8]為例，它對應(yīng)的二進(jìn)制數(shù)據(jù)為1 0001 0000 0010 0001.

定義m為單字節(jié)數(shù)據(jù)，g=0x1021為生成多項(xiàng)式，crc為CRC校驗(yàn)碼，則:

crc=m左移8位

循環(huán)8次

如果crc的最高位為1，則

crc左移一位后與g異或

否則

crc左移一位

循環(huán)結(jié)束.

上述函數(shù)中m為需要計(jì)算CRC的1個字節(jié)數(shù)據(jù)，取值為0x00～0xFF，返回值crc即為m的CRC校驗(yàn)碼.

2.2 多字節(jié)數(shù)據(jù)CRC校驗(yàn)碼的程序?qū)崿F(xiàn)

根據(jù)1.2節(jié)的推導(dǎo)，求取N字節(jié)數(shù)據(jù)CRC校驗(yàn)碼時需要重復(fù)調(diào)用單字節(jié)數(shù)據(jù)CRC校驗(yàn)碼的求取函數(shù)，下面給出計(jì)算多字節(jié)數(shù)據(jù)的CRC校驗(yàn)碼偽代碼描述，由于篇幅限制，省去C語言源代碼.

調(diào)用單字節(jié)的CRC碼計(jì)算程序，獲得第一個字節(jié)的CRC校驗(yàn)碼crc.

R1=crc

循環(huán)N次

取R1的高8位右移8位后與第二個字節(jié)異或，結(jié)果保存為臨時變量temp

調(diào)用單字節(jié)的CRC碼計(jì)算程序，獲取temp的CRC碼，結(jié)果保存為R-temp

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

保留R2的低16位

R1=R2

循環(huán)結(jié)束.

求取N字節(jié)數(shù)據(jù)序列的CRC校驗(yàn)碼共需調(diào)用N+1次單字節(jié)CRC碼求取函數(shù)，最后返回值R1即為N字節(jié)數(shù)據(jù)序列的CRC碼.

3 CRC算法在衛(wèi)星上的應(yīng)用

衛(wèi)星發(fā)射以后，需要通過測控系統(tǒng)接收來自地面的遙控指令、控制參數(shù)等數(shù)據(jù)，為了保證接收數(shù)據(jù)的正確性，星上軟件必須采取一定的方法對接收的數(shù)據(jù)進(jìn)行差錯檢驗(yàn).本文2.2節(jié)給出了計(jì)算任意字節(jié)數(shù)據(jù)序列的CRC函數(shù)，下面介紹其在衛(wèi)星控制系統(tǒng)中的應(yīng)用.衛(wèi)星控制系統(tǒng)從緩沖區(qū)中取出來自測控系統(tǒng)的N字節(jié)數(shù)據(jù)，該數(shù)據(jù)的前N-2字節(jié)為有效信息碼，后2個字節(jié)為CRC校驗(yàn)碼.控制系統(tǒng)調(diào)用計(jì)算多字節(jié)數(shù)據(jù)CRC校驗(yàn)碼的函數(shù)即可獲得CRC校驗(yàn)碼，若該校驗(yàn)碼取值為0，則接收的數(shù)據(jù)正確，控制系統(tǒng)可以對其進(jìn)行處理;若該校驗(yàn)碼不為0，說明數(shù)據(jù)在傳輸過程中發(fā)生了錯誤，控制系統(tǒng)不能使用此數(shù)據(jù).表1給出一組數(shù)據(jù)，驗(yàn)證CRC算法的檢錯能力.測控系統(tǒng)發(fā)送一幀16字節(jié)數(shù)據(jù)，其中最后兩個字節(jié)為CRC校驗(yàn)碼，所有數(shù)據(jù)均用16進(jìn)制表示.

從表1可以看出，當(dāng)控制系統(tǒng)接收的數(shù)據(jù)正確時，接收端計(jì)算的CRC校驗(yàn)碼為0，當(dāng)數(shù)據(jù)在傳輸過程中發(fā)生錯誤時，接收端計(jì)算的CRC校驗(yàn)碼不為0，可見給出的CRC算法能靈敏的檢測出通信錯誤.

表1 試驗(yàn)數(shù)據(jù)

4 結(jié) 論

本文推導(dǎo)了CRC算法，給出了計(jì)算任意字節(jié)數(shù)據(jù)序列CRC校驗(yàn)碼的C語言實(shí)現(xiàn).將CRC算法封裝為兩個函數(shù)，使用時只需提供數(shù)據(jù)的字節(jié)數(shù)就可獲得該數(shù)據(jù)序列的CRC校驗(yàn)碼，模塊獨(dú)立，算法簡潔.本文將CRC算法應(yīng)用到衛(wèi)星控制系統(tǒng)中，試驗(yàn)數(shù)據(jù)表明，該CRC算法能夠有效的檢測出通信過程中產(chǎn)生的數(shù)據(jù)錯誤.

[1] Joe C.串行通訊C程序員指南[M].徐定國，廖衛(wèi)東譯，北京:清華大學(xué)出版社，1990

[2] 熊貴喜.計(jì)算機(jī)網(wǎng)絡(luò)(第三版)[M].北京:清華大學(xué)出版社，1998

[3] 李肇慶，韓濤.串行端口技術(shù)[M].北京:國防工業(yè)出版社，2004

[4] 王春森.程序員教程[M].北京:清華大學(xué)出版社，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—)，女，四川人，高級工程師，研究方向?yàn)轱w行器導(dǎo)航、制導(dǎo)與控制，衛(wèi)星姿態(tài)與軌道控制(e-mail:yangjunchun@163.com).