“異或”校驗漏檢率分析

梁夢濤 韓壯志 吳玉柱

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

0 引 言

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

1 BCC校驗漏檢原理分析

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

設傳輸的數據為:

M=(M1M2…MN)

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

R=(M1⊕M2⊕…⊕MN)

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

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

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

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

圖1 “異或”校驗發生漏檢的情形

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

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

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

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

(1)

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

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

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

(3)

化簡得:

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

令:

f(m)=n2m-2mn

(5)

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

(6)

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

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

(7)

化簡得:

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

與校驗結果傳輸正確的情況不同的是,此時本次數據傳輸將無正確結果,與校驗結果一致的所有排列組和均為漏檢。總體思路不變,僅將原來包含1種正確結果的計算方式改變,此時的漏檢率變為了:

即:

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

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

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

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

圖2 北斗短報文通信流程

由圖2可知:

① 短報文發送終端將報文信息發送至北斗衛星;

② 北斗衛星將報文信息發送至地面基站;

③ 地面基站將報文信息發送至北斗衛星;

④ 北斗衛星將報文信息通過廣播發送至接收終端。

短報文通信協議如表1所示。

表1 短報文通信發送協議

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

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

表2 短報文通信接收協議

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

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

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

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

4 結 語

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