梁夢濤 韓壯志 吳玉柱

1(石家莊鐵道大學電氣與電子工程學院 河北 石家莊 050043)2(陸軍工程大學石家莊校區(qū)電子與光學工程系 河北 石家莊 050003)

0 引 言

“異或”校驗是一種通過將傳輸數(shù)據(jù)進行“異或”運算并將最終結(jié)果作為接收數(shù)據(jù)后驗證數(shù)據(jù)準確性憑證的一種數(shù)據(jù)驗證方式。與現(xiàn)有常用的幾種數(shù)據(jù)校驗方式比如奇偶檢驗、CRC冗余校驗[1-5]以及MD5[6-10]等相比,“異或”校驗不但實現(xiàn)過程簡單,且“異或”校驗的可靠性強于奇偶校驗而額外添加的冗余數(shù)據(jù)又少于CRC以及MD5等驗證方式,故“異或”校驗在串口通信以及數(shù)據(jù)存儲等領(lǐng)域得到了廣泛應用[11-14]。值得注意的是,雖然使用“異或”校驗作為校驗方式的應用不斷推廣,但“異或”校驗的可靠性即檢錯能力卻因無文獻可查而無法得到理論支持,“異或”校驗的可靠性分析僅停留在研究員的使用經(jīng)驗上。在實際使用中,“異或”校驗存在錯誤無法檢測即漏檢情況的發(fā)生,同時實驗中發(fā)現(xiàn)在使用不同位數(shù)的校驗位時,漏檢率有不同結(jié)果的現(xiàn)象。使用“異或”校驗的信息傳輸系統(tǒng)在不同應用場合都得到了應用,如果發(fā)生“異或”校驗的可靠性無法滿足某些應用場合對數(shù)據(jù)校驗正確性的要求時,繼續(xù)使用“異或”校驗作為校驗方式數(shù)據(jù)傳輸?shù)恼_性就無法得到保證,這對后續(xù)的數(shù)據(jù)處理將造成嚴重影響,甚至會因數(shù)據(jù)的錯誤而造成重大損失,故判斷應用場合的“異或”校驗可靠性十分必要。為證明“異或”校驗的可靠性,同時證明檢驗位數(shù)與數(shù)據(jù)長度對漏檢率的影響,下面將從出現(xiàn)漏檢的原理作為出發(fā)點,通過數(shù)據(jù)分析計算出“異或”校驗方式的漏檢率表達式,系統(tǒng)分析“異或”校驗方式在采用不同校驗位數(shù)及不同數(shù)據(jù)長度時的漏檢率變化情況。并在最后結(jié)合北斗短報文這一重要應用,對“異或”校驗實際的應用性能進行了分析。

1 BCC校驗漏檢原理分析

在分析“異或”校驗漏檢的原理之前,首先對“異或”校驗的具體實現(xiàn)過程做一個說明,這里使用一對8位二進制數(shù)進行運算說明:假設需要傳輸00000000、11111111兩組數(shù)據(jù),將兩者進行“異或”運算,計算結(jié)果為00000000⊕11111111=11111111,得到一組新八位二進制數(shù)11111111,將11111111加入兩組數(shù)據(jù)之后進行封裝,將三組數(shù)據(jù)發(fā)送給接收方,接收方對前兩組數(shù)據(jù)再進行一次“異或”運算,驗算得到的結(jié)果是否與第三組數(shù)組11111111相同,若相同則證明數(shù)據(jù)正確,如不同則認為傳輸出錯。下面開始進入“異或”校驗的漏檢發(fā)生的理論分析:

設傳輸?shù)臄?shù)據(jù)為:

M=(M1M2…MN)

式中:M為一組位數(shù)為m數(shù)量為n的二進制數(shù)。對全部數(shù)據(jù)進行“異或”運算得到運算結(jié)果:

R=(M1⊕M2⊕…⊕MN)

那么將兩者進行封裝發(fā)送給接收方的數(shù)據(jù)為M+R,接收方在接收到數(shù)據(jù)后便重新對M進行一次“異或”運算,將所得結(jié)果與R進行比較以判斷接收數(shù)據(jù)的完整性。若發(fā)生位置相同但數(shù)量為奇數(shù)的錯誤,此時情況可等價為錯誤數(shù)據(jù)兩兩組合且余出一個錯誤的情形,那么此時的R變?yōu)?

R′=M1⊕M2⊕…⊕M′i⊕M′j⊕…⊕M′k⊕…

式中:M′i、M′j等數(shù)據(jù)為對應原Mi、Mj等數(shù)據(jù)發(fā)生錯誤后的數(shù)據(jù)。由上述分析可知,在兩組數(shù)據(jù)相同位置同時發(fā)生錯誤對結(jié)果無影響,這時奇數(shù)個錯誤余出的M′k數(shù)據(jù)使該位計算結(jié)果發(fā)生變化,不會發(fā)生漏檢。這意味著錯誤數(shù)據(jù)數(shù)量應該為偶數(shù),這是產(chǎn)生漏檢的必要條件。

從上述過程結(jié)合“異或”運算法則可以得到算法中的一個缺陷,即一位二進制數(shù)“異或”運算有四種結(jié)果1⊕1=0、0⊕0=0、1⊕0=1、0⊕1=1,但“異或”校驗結(jié)果僅有兩種結(jié)果0與1,這意味著當正確傳輸結(jié)果出現(xiàn)錯誤且出錯的結(jié)果“異或”運算結(jié)果與原結(jié)果相同時,“異或”校驗這時就錯誤地認為傳輸數(shù)據(jù)正確,發(fā)生漏檢。這時可以得到一個結(jié)論,漏檢的發(fā)生需要滿足的充分條件是在參與計算的兩組數(shù)據(jù)的相同位置均發(fā)生錯誤,若僅一組數(shù)據(jù)發(fā)生錯誤則不會發(fā)生漏檢。漏檢發(fā)生的情況如圖1所示。

圖1 “異或”校驗發(fā)生漏檢的情形

圖中給出了一對同位置數(shù)據(jù)發(fā)生錯誤的情況,發(fā)生漏檢的條件需滿足A⊕W=A′⊕W′,當其他同位置的一對數(shù)據(jù)發(fā)生錯誤時,情況相同,這里就不一一給出。由此可以得出結(jié)論,“異或”校驗漏檢的發(fā)生實際上是二進制數(shù)結(jié)果在每一位僅有2種可能而可能出現(xiàn)的結(jié)果有4種,校驗位的結(jié)果不足以表示出所有排列組合的計算結(jié)果,錯誤的組合方式也被“通過”造成的。

2 “異或”校驗漏檢率計算

由上節(jié)的分析可知,漏檢出現(xiàn)的直接原因是錯誤的組合也得出了正確結(jié)果,那么漏檢率的分析也將從這一點入手。本節(jié)將使用排列組合的方式,對漏檢率的計算方法進行推導。若發(fā)生漏檢,至少為兩個數(shù)據(jù)發(fā)生錯誤才會導致最終結(jié)果漏檢,且錯誤位置需對應相同。

當m位二進制數(shù)“異或”運算的結(jié)果R出現(xiàn)漏檢,即意味著每一位數(shù)據(jù)均為與原結(jié)果相同的數(shù)字,那么此時每一位均有兩種情況為正確或錯誤,n個m位的二進制數(shù)“異或”的排列組合結(jié)果有2nm種,除去1種正確組合那么錯誤排列組合的總數(shù)量為2nm-1種,但m位數(shù)據(jù)一共可以表示的最終結(jié)果僅有2m種,其中同樣包含一種結(jié)果為正確數(shù)據(jù),那么可識別的結(jié)果的數(shù)量為2m種。由第1節(jié)的分析已知造成漏檢的根本原因是校驗位結(jié)果數(shù)量不足以表達出所有排列組合結(jié)果,這時可計算出所有與原結(jié)果相同的排列組合種類:

(1)

這意味著在所有錯誤中有這些數(shù)量的錯誤是無法被檢測出的,那么可進一步推出位校驗位漏檢率計算公式為:

為保證計算結(jié)果有意義,這里限定m、n的取值范圍為(m,n|m≥1,n≥2)。

繼而將n看做常數(shù),對m進行求導:

(3)

化簡得:

因為n≥2,故(1-n)<0。繼續(xù)驗證n2m-2mn的關(guān)系。

令:

f(m)=n2m-2mn

(5)

f′(m)=n(2m-2mn)ln2

(6)

因為m、n的取值范圍為(m,n|m≥1,n≥2),在取值范圍內(nèi)恒成立,且f(1)<0,那么可以求得P′<0,即隨著位數(shù)m的增加,漏檢率為一單調(diào)遞減函數(shù),由此可證明位數(shù)越長的校驗位越不容易發(fā)生漏檢。

繼續(xù)設m為常數(shù),求參與運算的數(shù)據(jù)數(shù)量n對校驗和的影響。對n求導可得:

(7)

化簡得:

以上分析基于了一個前提,就是校驗結(jié)果在傳輸過程中無誤碼是正確的,那么如果校驗結(jié)果傳輸錯誤,漏檢率又會如何變化?接下來假設校驗和在傳輸過程中發(fā)生誤碼,分析漏檢率的變化。

與校驗結(jié)果傳輸正確的情況不同的是,此時本次數(shù)據(jù)傳輸將無正確結(jié)果,與校驗結(jié)果一致的所有排列組和均為漏檢?？傮w思路不變,僅將原來包含1種正確結(jié)果的計算方式改變,此時的漏檢率變?yōu)榱?

即:

通過以上分析,可以得到關(guān)于“異或”校驗的兩個推論:① 位數(shù)越長的校驗位越不容易漏檢;② 校驗位校驗的數(shù)據(jù)越少越不容易漏檢。

3 BCC校驗應用實例及漏檢率計算

“異或”校驗方式的一個重要應用為北斗短報文通信。本節(jié)將以北斗短報文通信為例,對“異或”校驗方式的實際應用做一個分析。

北斗短報文通信的流程如圖2所示。

圖2 北斗短報文通信流程

由圖2可知:

① 短報文發(fā)送終端將報文信息發(fā)送至北斗衛(wèi)星;

② 北斗衛(wèi)星將報文信息發(fā)送至地面基站;

③ 地面基站將報文信息發(fā)送至北斗衛(wèi)星;

④ 北斗衛(wèi)星將報文信息通過廣播發(fā)送至接收終端。

短報文通信協(xié)議如表1所示。

表1 短報文通信發(fā)送協(xié)議

協(xié)議中,幀頭為信息類別標志位,格式為“＄+信息類別拼音首字母”,例如發(fā)送數(shù)據(jù)的標志位為“通信申請”,表示為“＄TXSQ”?！伴L度”表示從“指令或內(nèi)容”起始符“＄”開始到“校驗和”(含校驗和)為止的數(shù)據(jù)總字節(jié)數(shù)。校驗和在北斗協(xié)議中的定義為:“校驗和”是指從“指令或內(nèi)容”起始符“＄”起到“校驗和”前一字節(jié),按字節(jié)“異或”的結(jié)果。即按“異或”校驗的計算規(guī)則,對從“＄”至全部電文內(nèi)容進行“異或”運算。

由表2所示協(xié)議可知,短報文通信自帶兩個信息校驗位,分別為CRC校驗與檢驗和校驗,校驗和就是將檢驗和位之前的全部數(shù)據(jù)進行“異或”運算后生成的計算結(jié)果,發(fā)送校驗和需在發(fā)送端計算生成并發(fā)送。值得注意的是,CRC校驗位僅作為一個狀態(tài)標志位,以十六進制數(shù)0×00H與0×01H表示CRC校驗正確與錯誤兩種狀態(tài),并不是CRC校驗多項式,在實際使用中該標志位默認上傳0×00H,即默認信息正確,用此標志位判斷信息的正確性是不可靠的。

表2 短報文通信接收協(xié)議

在北斗通信中,符號與字母均采用美國信息交換標準代碼(American Standard Code for Information Interchange,ASCII)進行表示,ASCII簡單解釋即為用對應十六進制數(shù)代替不同字母、數(shù)字或符號。ASCII的說明這里進行舉例,符號“＄”在ASCII中為0×24H,T為0×54H,X為0×58H,S為0×53H,Q為0×51H。那么“＄TXSQ”即轉(zhuǎn)化為了“0×24,0×54,0×58,0×53,0×51”,短報文通信中便傳輸該組數(shù)字表示幀頭的信息類別標志。那么北斗短報文通信校驗和的生成過程為:

R=0×24·0×54·0×58·0×53·0×51·…

校驗和的作用在一次北斗短報文通信中體現(xiàn)了兩次,第一次是在信息進入地面基站時,對數(shù)據(jù)進行“異或”運算驗證結(jié)果是否與發(fā)送校驗和一致,一致則進行下一步通信流程,若不一致則認為信息傳輸出錯,將整段信息丟棄;第二次是在接收方,地面基站對信息進行轉(zhuǎn)發(fā)時會重新生成新校驗和,接收方利用新校驗和與接收信息進行的“異或”運算結(jié)果作對比進行驗證。

校驗和為8位二進制數(shù),短報文通信長度根據(jù)通信IC卡的等級不同,單次通信信息長度從13字節(jié)到210字節(jié)不等,根據(jù)第2節(jié)中對漏檢率的分析可以計算出,當檢驗和傳輸正確時,校驗和漏檢率在0.003 90～0.003 91之間,具體數(shù)值根據(jù)傳輸信息長度不同而變化,當校驗和傳輸錯誤時,漏檢率在0.003 90～0.003 91之間,具體數(shù)值根據(jù)傳輸信息長度不同而變化。故“異或”校驗在北斗短報文通信的應用中是可靠的。

4 結(jié) 語

“異或”校驗的應用十分廣泛,但“異或”校驗在使用中存在漏檢情況的發(fā)生,為證明“異或”校驗的可靠性,對異或校驗漏檢率進行了分析。通過原理及理論計算兩個方面的分析,得出了影響“異或”運算校驗位漏檢率的因素,分別為校驗位長度與校驗數(shù)據(jù)量。并通過結(jié)合北斗短報文通信這一重要應用方式,得出了短報文通信校驗和的漏檢率在0.003 90～0.003 91之間,是可靠的。且值得注意的是,雖然漏檢率關(guān)于數(shù)據(jù)量是一個遞增函數(shù),當數(shù)據(jù)量趨于無窮時,漏檢率會收斂于一個與校驗位長度成反比的數(shù)字,影響漏檢率的決定因素為校驗位長度。那么在這里對使用“異或”校驗的工程給出的建議是使用更長的校驗位,例如當校驗位為兩位或四位時,使用連續(xù)多個校驗位連接成長度更長的校驗位,例如兩位變四位、四位變八位等,可大大提高校驗位校驗能力,保證信息傳輸?shù)恼_性。