摘? 要: 討論了在自報式水情無線遙測系統數據通信中進行快速差錯校驗的必要性,給出了經過實際檢驗、可行的軟件快速校驗方法,并比較了它們的優劣與適應的場合。?

　　關鍵詞: CRC? 漢明碼? 水情遙測? 數據通信? 差錯校驗?

?

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

?

?

　　水情遙測系統的報汛方式一般有三種:定時自報式、查詢-應答式和混合式(自報和查詢-應答兼容)。三種報汛方式兼有長短。綜合考慮系統功耗、可靠性、復雜性等要素,定時自報方式在水情遙測系統中仍占主流。其優點是:功耗極低(值守狀態<50μA@+12V,大多以蓄電池供電),系統結構簡單,可靠性較高;缺點是無法實現反饋重發、反傳校驗等差錯控制。顯然,需要選擇一種合適的差錯校驗方法。?

　　水情遙測系統的數據通信方式可分為超短波通信、微波通信、衛星通信、移動通信、有線通信等。因其遙測站點常建于交通不便、供電及有線通信條件不足的地區,基于建設成本及運行費用等考慮,數據通信仍以無線超短波通信為主要方式。?

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

1 CRC校驗?

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

?

?

　　常用的16位CRC多項式有兩種:一種是CRC-CCITT標準,在微機通信的XMODEM協議中得到了應用;另一種是CRC-16標準,它實際捕獲錯誤的能力不如CRC-CCITT,在IBM的二進制同步協議(BYSYNC)的數據傳送中應用已久。兩者采用的多項式如表2所示,本文采用前者。?

?

?

1.1 直接模2除法CRC實現方式?

　　對16位的CRC而言,用信息段作被除數,生成多項式(本文用1021H,CCITT標準)作除數,進行模2除法所產生的余數(2字節)即為CRC校驗值,且CRC校驗只問余數而不管商是多少。發送時將校驗值連在信息段的后面一起發送。在接收端,接收方只需把接收到的CRC校驗值連同信息一起,作為新的信息段并對其進行相同的CRC運算(只比發送時多2字節)。若得到的新余數(校驗值)為0,則表明接收到的信息段和CRC都無差錯;反之,說明信息段或CRC有錯,應做相應處理。所以CRC的編碼和譯碼并沒有本質的區別。程序如下:?

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

{// data:數據,所用信息字的第一個字節;genpoly:CRC多項式,如1021H;accum:累加器的值,第一次賦0,以后放每次校驗結果。?

　　data<<=8; ????????????? //信息字節左移到高字節?

　　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;?? ??????????? //返回用作下一個信息字校驗的累加器值?

}?

1.2 快速CRC實現方式?

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

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

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

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

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

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

2 擴展漢明碼?

2.1 編碼方法?

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

　　?

　　兩者使用效果等價。 ?

　　漢明碼是糾正單個錯誤的完備碼,所有的接收碼都可對應到一個信息(多一對應),要么是正確信息,要么是發生單個錯誤的情形。當有兩個錯誤時,會把它當成另一個碼的單個錯誤加以糾正,導致誤碼。?

　　擴展漢明碼在此基礎上引入一個校驗和,即在編碼的時候增加第8位偶校驗位,構成(8,4)線性分組碼,因而可以糾正一位錯誤同時檢出兩位錯誤。事實上,在發生錯誤時就是這個偶校驗位確定了是錯一位還是錯兩位。若錯一位則可以糾正,錯兩位就只能檢出但不能糾正。?

　　編、譯碼均以擴展漢明碼(8,4)線性分組碼為例。為了方便單片機的運算,實現快速編碼,可采用查詢法。因為信息是一個4位的矢量,記作C,共有16個可能值。為了構成8位發送碼矢量,可以建立16個一字節的查詢作為8位的發送碼。以生成矩陣G₁為例,用信息矢量C乘以生成矩陣G₁再加上一位偶校驗就得到了生成碼(發送碼)。查詢表為:?

?

?

2.2 譯碼方法?

　　用查詢法對(8,4)碼進行譯碼,需要建造有256個值的查詢表。按照譯碼編寫查詢表。先寫出擴展漢明碼的校驗矩陣,實際上就是將原校驗矩陣H₁擴充,記為?

?????

??? 對于任一8位的接收碼矢量R,進行運算,得到一個4位的伴隨矢量,再按如下步驟比較確定原信息。?

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

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

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

　　將一個字節可能出現的所有0～255個可能值都按上面的譯碼步驟做一遍得到查詢表,留作譯碼用。另外譯碼和編碼還可以對整個信息字節作一字節的垂直校驗以增強校驗能力。?

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

參考文獻?

1 顧慰文.糾錯碼及其在計算機中的應用.北京:國防工業出版社,1980?

2 馬彥恒,尚朝軒.CRC差錯校驗在IBM/PC與8031單片機無線通訊中的應用.電子技術應用,1997;23(7):17～18?

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