摘? 要: 討論了在自報(bào)式水情無(wú)線遙測(cè)系統(tǒng)數(shù)據(jù)通信中進(jìn)行快速差錯(cuò)校驗(yàn)的必要性,給出了經(jīng)過(guò)實(shí)際檢驗(yàn)、可行的軟件快速校驗(yàn)方法,并比較了它們的優(yōu)劣與適應(yīng)的場(chǎng)合。?

　　關(guān)鍵詞: CRC? 漢明碼? 水情遙測(cè)? 數(shù)據(jù)通信? 差錯(cuò)校驗(yàn)?

?

　　將測(cè)站的實(shí)時(shí)水情數(shù)據(jù)(水位、閘位、雨量等)準(zhǔn)確無(wú)誤地發(fā)送到中心站,提供給水文洪水預(yù)報(bào)、洪水調(diào)度、防洪排澇決策等高一級(jí)系統(tǒng),是水情遙測(cè)系統(tǒng)最基本、最重要的功能之一。水情遙測(cè)系統(tǒng)是一個(gè)軟硬件綜合系統(tǒng)。其基本工作流程是:在測(cè)量端(測(cè)站)完成水情參數(shù)的采集與處理(信源編碼、存儲(chǔ)記錄、信道編碼等),然后將處理過(guò)的數(shù)據(jù)通過(guò)無(wú)線或有線信道直接或經(jīng)中繼發(fā)送至遠(yuǎn)端的中心站,由中心站進(jìn)行接收解碼并作進(jìn)一步處理。圖1為水情無(wú)線遙測(cè)系統(tǒng)結(jié)構(gòu)示意圖。測(cè)站和中繼站的主控設(shè)備一般采用單片機(jī),用匯編語(yǔ)言編程;而中心接收端主機(jī)一般采用微型機(jī),用C語(yǔ)言(或其它高級(jí)語(yǔ)言)編程。

?

?

　　水情遙測(cè)系統(tǒng)的報(bào)汛方式一般有三種:定時(shí)自報(bào)式、查詢-應(yīng)答式和混合式(自報(bào)和查詢-應(yīng)答兼容)。三種報(bào)汛方式兼有長(zhǎng)短。綜合考慮系統(tǒng)功耗、可靠性、復(fù)雜性等要素,定時(shí)自報(bào)方式在水情遙測(cè)系統(tǒng)中仍占主流。其優(yōu)點(diǎn)是:功耗極低(值守狀態(tài)<50μA@+12V,大多以蓄電池供電),系統(tǒng)結(jié)構(gòu)簡(jiǎn)單,可靠性較高;缺點(diǎn)是無(wú)法實(shí)現(xiàn)反饋重發(fā)、反傳校驗(yàn)等差錯(cuò)控制。顯然,需要選擇一種合適的差錯(cuò)校驗(yàn)方法。?

　　水情遙測(cè)系統(tǒng)的數(shù)據(jù)通信方式可分為超短波通信、微波通信、衛(wèi)星通信、移動(dòng)通信、有線通信等。因其遙測(cè)站點(diǎn)常建于交通不便、供電及有線通信條件不足的地區(qū),基于建設(shè)成本及運(yùn)行費(fèi)用等考慮,數(shù)據(jù)通信仍以無(wú)線超短波通信為主要方式。?

　　在無(wú)線數(shù)據(jù)通信過(guò)程中,即使信道質(zhì)量良好,但由于信號(hào)衰減、失真,特別是某些突發(fā)性的干擾(如雷電,電磁輻射)不可避免地會(huì)發(fā)生數(shù)據(jù)誤傳,即誤碼。根據(jù)水情遙測(cè)系統(tǒng)的相關(guān)規(guī)范,超短波數(shù)據(jù)傳輸?shù)恼`碼率應(yīng)小于10^-4,以及在每個(gè)數(shù)據(jù)收集周期平均應(yīng)有90%以上的測(cè)站(重點(diǎn)控制站必須包括在內(nèi))能準(zhǔn)確傳送數(shù)據(jù)至中心站。因此采取適當(dāng)?shù)牟铄e(cuò)控制方法,提高數(shù)據(jù)傳輸?shù)目煽啃院苡斜匾?。常用的差錯(cuò)控制方法分軟件和硬件方式。最簡(jiǎn)單的是由器件直接實(shí)現(xiàn)奇偶校驗(yàn)方式,它占用10%的時(shí)間,只檢出奇數(shù)個(gè)位出錯(cuò)。據(jù)檢測(cè),在電話網(wǎng)中以1200波特率傳輸數(shù)據(jù)時(shí),若采用奇偶校驗(yàn)方式,仍會(huì)有40%的錯(cuò)誤不能檢出,這對(duì)水情遙測(cè)顯然是不夠的。欲對(duì)包括中繼在內(nèi)的每一個(gè)站實(shí)行碼校驗(yàn),還要求所選校驗(yàn)方式具有高檢出率、速度快、編碼簡(jiǎn)單等特點(diǎn)。常見的方式有漢明碼、循環(huán)冗余校驗(yàn)(CRC)等,雖然這些校驗(yàn)方式也可由硬件實(shí)現(xiàn),但人們?nèi)詢A向于采用簡(jiǎn)單經(jīng)濟(jì)又具靈活性的軟件校驗(yàn)。以下結(jié)合工作實(shí)際給出經(jīng)驗(yàn)證可行的快速校驗(yàn)方法,并比較了它們的優(yōu)劣。文中所涉及到的程序算法均以C語(yǔ)言的形式給出,而將其轉(zhuǎn)變成單片機(jī)的算法也不難。?

1 CRC校驗(yàn)?

　　CRC(Cyclical? Redundancy? Check)校驗(yàn),又稱循環(huán)冗余校驗(yàn),具有極強(qiáng)的檢錯(cuò)能力(不能糾錯(cuò)),算法簡(jiǎn)單。早期用硬件電路直接搭成,但軟件方法成本更低,實(shí)現(xiàn)更簡(jiǎn)單,運(yùn)算速度也很快。16位的CRC檢錯(cuò)率如表1所示^[1]。?

?

?

　　常用的16位CRC多項(xiàng)式有兩種:一種是CRC-CCITT標(biāo)準(zhǔn),在微機(jī)通信的XMODEM協(xié)議中得到了應(yīng)用;另一種是CRC-16標(biāo)準(zhǔn),它實(shí)際捕獲錯(cuò)誤的能力不如CRC-CCITT,在IBM的二進(jìn)制同步協(xié)議(BYSYNC)的數(shù)據(jù)傳送中應(yīng)用已久。兩者采用的多項(xiàng)式如表2所示,本文采用前者。?

?

?

1.1 直接模2除法CRC實(shí)現(xiàn)方式?

　　對(duì)16位的CRC而言,用信息段作被除數(shù),生成多項(xiàng)式(本文用1021H,CCITT標(biāo)準(zhǔn))作除數(shù),進(jìn)行模2除法所產(chǎn)生的余數(shù)(2字節(jié))即為CRC校驗(yàn)值,且CRC校驗(yàn)只問(wèn)余數(shù)而不管商是多少。發(fā)送時(shí)將校驗(yàn)值連在信息段的后面一起發(fā)送。在接收端,接收方只需把接收到的CRC校驗(yàn)值連同信息一起,作為新的信息段并對(duì)其進(jìn)行相同的CRC運(yùn)算(只比發(fā)送時(shí)多2字節(jié))。若得到的新余數(shù)(校驗(yàn)值)為0,則表明接收到的信息段和CRC都無(wú)差錯(cuò);反之,說(shuō)明信息段或CRC有錯(cuò),應(yīng)做相應(yīng)處理。所以CRC的編碼和譯碼并沒(méi)有本質(zhì)的區(qū)別。程序如下:?

USHORT crc(USHORT data， USHORT genpoly， USHORT accum)?

{// data:數(shù)據(jù),所用信息字的第一個(gè)字節(jié);genpoly:CRC多項(xiàng)式,如1021H;accum:累加器的值,第一次賦0,以后放每次校驗(yàn)結(jié)果。?

　　data<<=8; ????????????? //信息字節(jié)左移到高字節(jié)?

　　for(int i=8;i>0;i--)??? {?

　　??? if((data^accum)&0x8000) // 如果(data 異或accum)的最高位是1?

????????????? accum=(accum<<1)^genpoly; //移位與genpoly異或?

??? ??? else??? accum<<=1; //否則僅移位?

??? ??? data<<=1;??? ?????? //將信息字的下一位升格?

??? }?

??? return accum;?? ??????????? //返回用作下一個(gè)信息字校驗(yàn)的累加器值?

}?

1.2 快速CRC實(shí)現(xiàn)方式?

　　直接模2除法CRC方式雖編程簡(jiǎn)單,但效率不高。采用該方式,要使用16位的多項(xiàng)式及兩字節(jié)的累加器,對(duì)每一信息位(bit)累加器都要移位一次,再根據(jù)移位結(jié)果判斷是否作異或;每一字節(jié)重復(fù)8 次,運(yùn)算速度相對(duì)較慢,不符合計(jì)算機(jī)按比特進(jìn)行計(jì)算的規(guī)律。但如果采用微機(jī)通信中XMODEM協(xié)議所使用的CRC查詢方法,則比直接CRC模2除法方式快4～10倍。查詢方法實(shí)施過(guò)程:首先用信息字節(jié)與累加器的高字節(jié)進(jìn)行異或,并將其結(jié)果作初始累加器為0的CRC;然后與原累加器的低字節(jié)再作一次異或。第一步只有256個(gè)樣式,可以構(gòu)造一個(gè)256個(gè)雙字節(jié)的查詢表,一步實(shí)現(xiàn)。這樣對(duì)每一字節(jié)只要作兩次操作就可完成。以下是具體步驟。?

　　(1)構(gòu)造查詢表,運(yùn)行直接模2除法CRC函數(shù)CRC(i，1021，0),用i從0～255代入,將結(jié)果按序排列可得到一個(gè)256個(gè)樣式的雙字節(jié)查詢表。該表只作一次,可以先用C語(yǔ)言在微型機(jī)上作好,然后再轉(zhuǎn)到單片機(jī)上,留作以后查詢使用。?

　　(2)取一個(gè)雙字節(jié)累加器accum,賦初值0,將信息流的第一個(gè)字節(jié)賦給另一雙字節(jié)變量data(accum 和data 都是雙字節(jié)變量,以下步驟也是作雙字節(jié)運(yùn)算)。?

　　(3)將accum>>8(也即取原累加器accum的高字節(jié))的值與信息字data相異或,所得結(jié)果(是一個(gè)<256的值)查上述構(gòu)造好的查詢表,得到一個(gè)16位的暫存值。?

　　(4)將accum<<8(即原累加器accum的低字節(jié)左移成高字節(jié),低位補(bǔ)0),與上一步得到的暫存值(16位的值)相異或,結(jié)果作為新的累加器值,賦值給accum。?

　　(5)取信息流的下一個(gè)字節(jié)賦給data,重復(fù)進(jìn)行第(3)步和第(4)步,直至所有的信息字節(jié)被用完為止,最后累加器的值就是余數(shù)。?

2 擴(kuò)展?jié)h明碼?

2.1 編碼方法?

　　CRC校驗(yàn)只能檢錯(cuò)但不能糾錯(cuò)。而1949年提出的漢明碼是一種能糾正單個(gè)錯(cuò)誤的線性分組碼。其中,既是線性分組碼同時(shí)也是循環(huán)碼的(7,4)碼有兩種。其生成矩陣和校驗(yàn)矩陣分列如下:?

　　?

　　兩者使用效果等價(jià)。 ?

　　漢明碼是糾正單個(gè)錯(cuò)誤的完備碼,所有的接收碼都可對(duì)應(yīng)到一個(gè)信息(多一對(duì)應(yīng)),要么是正確信息,要么是發(fā)生單個(gè)錯(cuò)誤的情形。當(dāng)有兩個(gè)錯(cuò)誤時(shí),會(huì)把它當(dāng)成另一個(gè)碼的單個(gè)錯(cuò)誤加以糾正,導(dǎo)致誤碼。?

　　擴(kuò)展?jié)h明碼在此基礎(chǔ)上引入一個(gè)校驗(yàn)和,即在編碼的時(shí)候增加第8位偶校驗(yàn)位,構(gòu)成(8,4)線性分組碼,因而可以糾正一位錯(cuò)誤同時(shí)檢出兩位錯(cuò)誤。事實(shí)上,在發(fā)生錯(cuò)誤時(shí)就是這個(gè)偶校驗(yàn)位確定了是錯(cuò)一位還是錯(cuò)兩位。若錯(cuò)一位則可以糾正,錯(cuò)兩位就只能檢出但不能糾正。?

　　編、譯碼均以擴(kuò)展?jié)h明碼(8,4)線性分組碼為例。為了方便單片機(jī)的運(yùn)算,實(shí)現(xiàn)快速編碼,可采用查詢法。因?yàn)樾畔⑹且粋€(gè)4位的矢量,記作C,共有16個(gè)可能值。為了構(gòu)成8位發(fā)送碼矢量,可以建立16個(gè)一字節(jié)的查詢作為8位的發(fā)送碼。以生成矩陣G₁為例,用信息矢量C乘以生成矩陣G₁再加上一位偶校驗(yàn)就得到了生成碼(發(fā)送碼)。查詢表為:?

?

?

2.2 譯碼方法?

　　用查詢法對(duì)(8,4)碼進(jìn)行譯碼,需要建造有256個(gè)值的查詢表。按照譯碼編寫查詢表。先寫出擴(kuò)展?jié)h明碼的校驗(yàn)矩陣,實(shí)際上就是將原校驗(yàn)矩陣H₁擴(kuò)充,記為?

?????

??? 對(duì)于任一8位的接收碼矢量R,進(jìn)行運(yùn)算,得到一個(gè)4位的伴隨矢量,再按如下步驟比較確定原信息。?

　　(1)如果伴隨式矢量是全0矢量,接收碼是正確的,碼的前(低)4位就是信息。?

　　(2)如果伴隨矢量的最后一位是1,則有一位錯(cuò),可糾正。將伴隨矢量與矩陣的每一列相比校,找出相同的那一列,記下列號(hào),再將接收碼與該列號(hào)相對(duì)應(yīng)的那一位變號(hào)(1變0,0變1),得到的碼就是糾正后的原碼,信息取碼的前(低)4位。?

　　(3)否則,是一位以上的錯(cuò)碼且不能糾正。?

　　將一個(gè)字節(jié)可能出現(xiàn)的所有0～255個(gè)可能值都按上面的譯碼步驟做一遍得到查詢表,留作譯碼用。另外譯碼和編碼還可以對(duì)整個(gè)信息字節(jié)作一字節(jié)的垂直校驗(yàn)以增強(qiáng)校驗(yàn)?zāi)芰Α?

　　上述檢驗(yàn)方式已在江蘇、寧夏、福建等地的實(shí)際工作中得到了驗(yàn)證。CRC校驗(yàn)雖不具備糾錯(cuò)功能但有很高的檢錯(cuò)率,應(yīng)用面也很廣。其中,直接模2除法CRC方式因編程簡(jiǎn)單、占用程序空間少(不用查詢表),適合于數(shù)據(jù)通信量不大且程序及內(nèi)存空間有限的場(chǎng)合,反之可選用快速CRC方式。在對(duì)數(shù)據(jù)完整性要求高的場(chǎng)合,可根據(jù)具體情況考慮使用漢明碼或擴(kuò)展?jié)h明碼。在某些要求更高的特殊情況下,則可選用更復(fù)雜一些的校驗(yàn)碼,同時(shí)通信條件的好壞也是影響校驗(yàn)方式選用的因素之一。?

參考文獻(xiàn)?

1 顧慰文.糾錯(cuò)碼及其在計(jì)算機(jī)中的應(yīng)用.北京:國(guó)防工業(yè)出版社,1980?

2 馬彥恒,尚朝軒.CRC差錯(cuò)校驗(yàn)在IBM/PC與8031單片機(jī)無(wú)線通訊中的應(yīng)用.電子技術(shù)應(yīng)用,1997;23(7):17～18?

3 Joe Campbel,張國(guó)定譯.串行通信C程序指南.北京:清華大學(xué)出版社,1995?