基于delta码的乘除法运算错误检测改进算法  

Improved algorithm for multiplication and division error detection based on delta code

作　　者：孙宗奇[1] 臧海娟[2] 张春花[1] 潘勇[1] 

机构地区：[1]同济大学电子与信息工程学院,上海201804 [2]江苏理工学院计算机工程学院,江苏常州213001

出　　处：《计算机应用》2017年第4期975-979,985,共6页journal of Computer Applications

基　　金：国家科技支撑计划项目(2015BAG13B01)~~

摘　　要：为确保安全苛求系统中程序执行的正确性,研究人员将差错控制理论用于对计算机指令进行编码,但由于编码大多涉及模运算,导致复杂度大量增加,应用于实时系统有困难。针对复杂度问题对delta码的乘除法运算算法进行改进。算法在乘法运算中引入冗余编码及差异化思想,从而确保安全性;在除法运算中引入逆元,将除法运算转化为低复杂度的乘法运算,避免了模运算带来的开销,降低了复杂度并提高了算法安全性,并对安全性进行理论论证。理论分析表明:所提算法漏检率可达2.3×10^(-10)。测试结果表明,所提算法的漏检率与理论值相符,且复杂度是未编码运算6.4~7.2倍,比原delta码降低了7%~19%,在漏检率与复杂度方面均满足安全苛求系统的应用要求。In order to ensure the correctness of program execution in the safety critical system, the error control theory is used to encode the computer instructions, but the algorithm involves the modular operation, resulting in high additional complexity and difficulty to use in real-time systems. Aiming at reducing the additional complexity, delta code＇s multiplication and division algorithm was improved. The idea of redundancy encoding and differentiated ideology was introduced to ensure security, while the inverse element was introduced into division to transform division into multiplication, thus avoiding the overhead of the modular operation and reducing the additional complexity while improving the security of the algorithm.Theoretical analysis shows that the undetected error rate is proved to be 2.3＊ 10^-10. Simulation results show that the undetected error rate of the proposed algorithm is consistent with the theoretical value, and the complexity is 6.4-7.2 times of the original algorithm, but 7%-19% lower than original delta code. The proposed algorithm satisfies the requirements of safety critical application systems in terms of error detection rate and complexity.

关 键 词：安全编码 数据差异化 错误检测 安全性 逆元 

分 类 号：TP302.8[自动化与计算机技术—计算机系统结构]