梁梦涛 韩壮志 吴玉柱

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之间,是可靠的。且值得注意的是,虽然漏检率关于数据量是一个递增函数,当数据量趋于无穷时,漏检率会收敛于一个与校验位长度成反比的数字,影响漏检率的决定因素为校验位长度。那么在这里对使用“异或”校验的工程给出的建议是使用更长的校验位,例如当校验位为两位或四位时,使用连续多个校验位连接成长度更长的校验位,例如两位变四位、四位变八位等,可大大提高校验位校验能力,保证信息传输的正确性。