“异或”校验漏检率分析.pdf

第 卷第 期计算机应用与软件 年 月 “异或”校验漏检率分析梁梦涛韩壮志吴玉柱（石家庄铁道大学电气与电子工程学院河北 石家庄 ）（陆军工程大学石家庄校区电子与光学工程系河北 石家庄 ）收稿日期：。梁梦涛，硕士生，主研领域：北斗短报文通信，嵌入式系统设计。韩壮志，副教授。吴玉柱，硕士生。摘要“异或”校验（）在使用中存在错误无法检测即漏检的发生，其可靠性未得到理论层面的证明。为证明“异或”校验的可靠性，通过对“异或”校验的校验过程进行分析，得到了“异或”校验发生漏检的原理并找到了漏检出现的根本原因。采用数学分析的方法得到了影响漏检率的因素是校验位长度与所校验数据量，推导出“异或”校验的漏检率计算公式。最后将计算公式应用在北斗短报文通信这一重要实际应用中，得到了北斗短报文“异或”校验位的漏检率在 范围内，证明了“异或”校验在短报文通信应用中的可靠性。关键词“异或”校验漏检率分析北斗短报文中图分类号 文献标志码 ：（，）（，）（），引言“异或”校验是一种通过将传输数据进行“异或”运算并将最终结果作为接收数据后验证数据准确性凭证的一种数据验证方式。与现有常用的几种数据校验方式比如奇偶检验、冗余校验 以及 等相比，“异或”校验不但实现过程简单，且“异或”校验的可靠性强于奇偶校验而额外添加的冗余数据又少于 以及 等验证方式，故“异或”校验在串口通信以及数据存储等领域得到了广泛应用 。值得注意的是，虽然使用“异或”校验作为校验方式的应用不断推广，但“异或”校验的可靠性即检错能力却因无文献可查而无法得到理论支持，“异或”校验的可靠性分析仅停留在研究员的使用经验上。在实际使用中，“异或”校验存在错误无法检测即漏检情况的发生，同时实验中发现在使用不同位数的校验位时，漏检率有不同结果的现象。使用“异或”校验的信息传输系统在不同应用场合都得到了应用，如果发生“异或”校验的可靠性无法满足某些应用场合对数据校验正确第 期梁梦涛，等：“异或”校验漏检率分析 性的要求时，继续使用“异或”校验作为校验方式数据传输的正确性就无法得到保证，这对后续的数据处理将造成严重影响，甚至会因数据的错误而造成重大损失，故判断应用场合的“异或”校验可靠性十分必要。为证明“异或”校验的可靠性，同时证明检验位数与数据长度对漏检率的影响，下面将从出现漏检的原理作为出发点，通过数据分析计算出“异或”校验方式的漏检率表达式，系统分析“异或”校验方式在采用不同校验位数及不同数据长度时的漏检率变化情况。并在最后结合北斗短报文这一重要应用，对“异或”校验实际的应用性能进行了分析。校验漏检原理分析在分析“异或”校验漏检的原理之前，首先对“异或”校验的具体实现过程做一个说明，这里使用一对 位二进制数进行运算说明：假设需要传输 、两组数据，将两者进行“异或”运算，计算结果为 ，得到一组新八位二进制数 ，将 加入两组数据之后进行封装，将三组数据发送给接收方，接收方对前两组数据再进行一次“异或”运算，验算得到的结果是否与第三组数组 相同，若相同则证明数据正确，如不同则认为传输出错。下面开始进入“异或”校验的漏检发生的理论分析：设传输的数据为：（）式中：为一组位数为 数量为 的二进制数。对全部数据进行“异或”运算得到运算结果：（）那么将两者进行封装发送给接收方的数据为 ，接收方在接收到数据后便重新对 进行一次“异或”运算，将所得结果与 进行比较以判断接收数据的完整性。若发生位置相同但数量为奇数的错误，此时情况可等价为错误数据两两组合且余出一个错误的情形，那么此时的 变为：式中：、等数据为对应原、等数据发生错误后的数据。由上述分析可知，在两组数据相同位置同时发生错误对结果无影响，这时奇数个错误余出的 数据使该位计算结果发生变化，不会发生漏检。这意味着错误数据数量应该为偶数，这是产生漏检的必要条件。从上述过程结合“异或”运算法则可以得到算法中的一个缺陷，即一位二进制数“异或”运算有四种结果 、，但“异或”校验结果仅有两种结果 与 ，这意味着当正确传输结果出现错误且出错的结果“异或”运算结果与原结果相同时，“异或”校验这时就错误地认为传输数据正确，发生漏检。这时可以得到一个结论，漏检的发生需要满足的充分条件是在参与计算的两组数据的相同位置均发生错误，若仅一组数据发生错误则不会发生漏检。漏检发生的情况如图 所示。图 “异或”校验发生漏检的情形图中给出了一对同位置数据发生错误的情况，发生漏检的条件需满足 ，当其他同位置的一对数据发生错误时，情况相同，这里就不一一给出。由此可以得出结论，“异或”校验漏检的发生实际上是二进制数结果在每一位仅有 种可能而可能出现的结果有 种，校验位的结果不足以表示出所有排列组合的计算结果，错误的组合方式也被“通过”造成的。“异或”校验漏检率计算由上节的分析可知，漏检出现的直接原因是错误的组合也得出了正确结果，那么漏检率的分析也将从这一点入手。本节将使用排列组合的方式，对漏检率的计算方法进行推导。若发生漏检，至少为两个数据发生错误才会导致最终结果漏检，且错误位置需对应相同。当 位二进制数“异或”运算的结果 出现漏检，即意味着每一位数据均为与原结果相同的数字，那么此时每一位均有两种情况为正确或错误，个 位的二进制数“异或”的排列组合结果有 种，除去 种正确组合那么错误排列组合的总数量为 种，但位数据一共可以表示的最终结果仅有 种，其中同样包含一种结果为正确数据，那么可识别的结果的数量为 种。由第 节的分析已知造成漏检的根本原因是校验位结果数量不足以表达出所有排列组合结果，这时可计算出所有与原结果相同的排列组合种类：（）这意味着在所有错误中有这些数量的错误是无法被检测出的，那么可进一步推出位校验位漏检率计算公式为：计算机应用与软件 年（）（）为保证计算结果有意义，这里限定 、的取值范围为（，）。继而将 看做常数，对 进行求导：（）（）（）（）（）（）化简得：（）（）（）因为 ，故（）。继续验证 的关系。令：（）（）（）（）（）因为 、的取值范围为（，），在取值范围内恒成立，且（），那么可以求得 ，即随着位数 的增加，漏检率为一单调递减函数，由此可证明位数越长的校验位越不容易发生漏检。继续设 为常数，求参与运算的数据数量 对校验和的影响。对 求导可得：（）（）（）（）（）（）化简得：（）（）因为两个分式在取值范围内均大于 恒成立，故 为一单调递增函数，且（），则证明参与运算的数据数量越多，漏检率会增加，但漏检率不会无限扩大，因为当 时，漏检率 将收敛于。以上分析基于了一个前提，就是校验结果在传输过程中无误码是正确的，那么如果校验结果传输错误，漏检率又会如何变化？接下来假设校验和在传输过程中发生误码，分析漏检率的变化。与校验结果传输正确的情况不同的是，此时本次数据传输将无正确结果，与校验结果一致的所有排列组和均为漏检。总体思路不变，仅将原来包含 种正确结果的计算方式改变，此时的漏检率变为了：（）（）即：（）通过以上分析，可以得到关于“异或”校验的两个推论：位数越长的校验位越不容易漏检；校验位校验的数据越少越不容易漏检。校验应用实例及漏检率计算“异或”校验方式的一个重要应用为北斗短报文通信。本节将以北斗短报文通信为例，对“异或”校验方式的实际应用做一个分析。北斗短报文通信的流程如图 所示。图 北斗短报文通信流程由图 可知：短报文发送终端将报文信息发送至北斗卫星；北斗卫星将报文信息发送至地面基站；地面基站将报文信息发送至北斗卫星；北斗卫星将报文信息通过广播发送至接收终端。短报文通信协议如表 所示。表 短报文通信发送协议数据类别数据长度 备注帧头 信息类别长度 数据长度本机地址 本机 卡号信息类别区分传输方式用户地址 收方 卡号电文长度 应答标志位是否应答电文内容最长 校验和“异或”校验位协议中，帧头为信息类别标志位，格式为“?信息类别拼音首字母”，例如发送数据的标志位为“通信申请”，表示为“?”。“长度”表示从“指令或内第 期梁梦涛，等：“异或”校验漏检率分析 容”起始符“?”开始到“校验和”（含校验和）为止的数据总字节数。校验和在北斗协议中的定义为：“校验和”是指从“指令或内容”起始符“?”起到“校验和”前一字节，按字节“异或”的结果。即按“异或”校验的计算规则，对从“?”至全部电文内容进行“异或”运算。由表 所示协议可知，短报文通信自带两个信息校验位，分别为 校验与检验和校验，校验和就是将检验和位之前的全部数据进行“异或”运算后生成的计算结果，发送校验和需在发送端计算生成并发送。值得注意的是，校验位仅作为一个状态标志位，以十六进制数 与 表示 校验正确与错误两种状态，并不是 校验多项式，在实际使用中该标志位默认上传 ，即默认信息正确，用此标志位判断信息的正确性是不可靠的。表 短报文通信接收协议数据类别数据长度 备注帧头 信息类别长度 数据长度本机地址 本机 卡号信息类别区分传输方式发信方地 发送方 卡号发信时间 电文长度 电文内容最长 标志位校验和“异或”校验位在北斗通信中，符号与字母均采用美国信息交换标准代码（，）进行表示，简单解释即为用对应十六进制数代替不同字母、数字或符号。的说明这里进行举例，符号“?”在 中为 ，为 ，为 ，为 ，为 。那么“?”即转化为了“，”，短报文通信中便传输该组数字表示帧头的信息类别标志。那么北斗短报文通信校验和的生成过程为：校验和的作用在一次北斗短报文通信中体现了两次，第一次是在信息进入地面基站时，对数据进行“异或”运算验证结果是否与发送校验和一致，一致则进行下一步通信流程，若不一致则认为信息传输出错，将整段信息丢弃；第二次是在接收方，地面基站对信息进行转发时会重新生成新校验和，接收方利用新校验和与接收信息进行的“异或”运算结果作对比进行验证。校验和为 位二进制数，短报文通信长度根据通信 卡的等级不同，单次通信信息长度从 字节到 字节不等，根据第 节中对漏检率的分析可以计算出，当检验和传输正确时，校验和漏检率在 之间，具体数值根据传输信息长度不同而变化，当校验和传输错误时，漏检率在 之间，具体数值根据传输信息长度不同而变化。故“异或”校验在北斗短报文通信的应用中是可靠的。结语“异或”校验的应用十分广泛，但“异或”校验在使用中存在漏检情况的发生，为证明“异或”校验的可靠性，对异或校验漏检率进行了分析。通过原理及理论计算两个方面的分析，得出了影响“异或”运算校验位漏检率的因素，分别为校验位长度与校验数据量。并通过结合北斗短报文通信这一重要应用方式，得出了短报文通信校验和的漏检率在 之间，是可靠的。且值得注意的是，虽然漏检率关于数据量是一个递增函数，当数据量趋于无穷时，漏检率会收敛于一个与校验位长度成反比的数字，影响漏检率的决定因素为校验位长度。那么在这里对使用“异或”校验的工程给出的建议是使用更长的校验位，例如当校验位为两位或四位时，使用连续多个校验位连接成长度更长的校验位，例如两位变四位、四位变八位等，可大大提高校验位校验能力，保证信息传输的正确性。参考文献朱正鹏，朱旭锋，李宾，等 一种位宽可变的 校验算法及硬件实现 航天控制，（）：崔彦坤，马萌 校验算法的设计与实现 计算机与网络，（）：肖凯嘉 循环冗余校验在数据采集系统中的应用 电子测试，（）：姚七栋，张春玉 校验及其软件实现 现代电子技术，（）：刘春阳 基于 的串行通信实现与 校验 北京：北京化工大学，靳燕 基于 算法的文件完整性检测系统分析及设计 网络安全技术与应用，（）：李森 算法的分析与研究 杭州：杭州电子科技大学，胡娜，崔晓锐 加密算法在校验网站完整性上的巧妙应用 网络安全技术与应用，（）：，（下转第 页）第 期钟经谋，等：基于骨骼关节点和物体属性的动作指令学习方法 ，：，：，：，：，：，：，：，（）：，：，（）：，：，：，：，：，：，：，：，：，：，：，：，：，：，：，：（上接第 页）苏俊，王鑫，王涛，等 循环移位与异或构造扩散层的新证明方法 密码学报，（）：韩津生，林家骏，叶建武，等 基于 的 高速处理模型设计 北京理工大学学报，（）：吴思齐 基于异或运算的快速纠删码计算方法 集成电路应用，（）：刘雍，汪文彬，马玉春 环境下的数据包的校验技术 电脑编程技巧与维护，（）：鲁威志 准循环低密度奇偶校验码的研究 济南：山东大学，陈晓琳，李盛乐，刘坚，等 基于北斗卫星通信的地震应急指挥系统研究 地震工程学报，（）：李志炜，傅军，刘李欢，等 基于北斗短报文的远程图像通信系统设计 导航定位与授时，（）：韩燕燕 基于北斗系统的即时通信终端设计与实现 北京：中央民族大学，冯新岗，宋志强，张立新 卫星搜救与北斗短报文通信搜救对比研究 空间电子技术，（）：