Please wait a minute...
浙江大学学报(理学版)  2018, Vol. 45 Issue (4): 420-426    DOI: 10.3785/j.issn.1008-9497.2018.04.008
电子科学     
逻辑函数高阶布尔e偏导数求解算法的实现
罗文强, 王伦耀, 夏银水
宁波大学 信息科学与工程学院, 浙江 宁波 315211
An algorithm for calculating the high-order Boolean e-partial derivative of logic function
LUO Wenqiang, WANG Lunyao, XIA Yinshui
Faculty of Electrical Engineering and Computer Science, Ningbo University, Ningbo 315211, Zhejiang Province, China
 全文: PDF(1052 KB)   HTML  
摘要: 针对已有方法在求解布尔e偏导数时只能解决小规模电路的问题,提出了一种基于逻辑函数不相交运算的大函数高阶布尔e偏导数的求解算法.该方法将逻辑函数转化为不相交乘积项的集合,用逻辑函数的不相交运算替代布尔e导数运算中的逻辑“与”运算;并将不包含待求导变量的乘积项拆分出来,不参与布尔e导数运算,以达到降低算法复杂度、提高算法速度的目的.提出的算法用C语言编程实现,并用MCNC测试电路进行了测试.实验结果显示,本算法能快速实现大函数高阶布尔e偏导数的求解,求解效率与参与不相交运算的乘积项数量有关,但对输入变量的数量不敏感.
关键词: e导数e偏导数高阶逻辑覆盖逻辑不相交运算    
Abstract: To cope with the problem that the existing algorithms are unable to calculate the high-order e-partial derivative of the Boolean functions with large inputs, an effective algorithm based on the logic disjointed operation between two logic functions is proposed. In the proposed algorithm, the products of the logic functions are firstly converted into the disjointed products, and the logic cover disjointed operation is used to replace the "AND" operation between two logic functions in e-partial derivation. The disjointed products which don't contain the variables taken for derivation are then identified and excluded from the further derivation. The proposed algorithm is implemented in C and tested under MCNC benchmarks. Experimental results show that the proposed algorithm can carry out the results quickly for the large functions. And its running time is related to the number of the products in the disjointed operation, but is less affected by the number of input variables.
Key words: e-derivative    e-partial derivative    high-order    logic cover    logic disjointed operation
收稿日期: 2016-10-13 出版日期: 2018-07-12
CLC:  TP331  
基金资助: 国家自然科学基金资助项目(61471211).
通讯作者: 王伦耀,通信作者,ORCID:http://orcid.org/0000-0002-6156-7495,E-mail:wanglunyao@nbu.edu.cn.     E-mail: wanglunyao@nbu.edu.cn
作者简介: 罗文强(1991-),ORCID:http://orcid.org/0000-0002-0980-940X,男,硕士,主要从事基于library-free的逻辑映射研究.
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章  
罗文强
王伦耀
夏银水

引用本文:

罗文强, 王伦耀, 夏银水. 逻辑函数高阶布尔e偏导数求解算法的实现[J]. 浙江大学学报(理学版), 2018, 45(4): 420-426.

LUO Wenqiang, WANG Lunyao, XIA Yinshui. An algorithm for calculating the high-order Boolean e-partial derivative of logic function. Journal of Zhejiang University (Science Edition), 2018, 45(4): 420-426.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2018.04.008        https://www.zjujournals.com/sci/CN/Y2018/V45/I4/420

[1] AGAIAN S S, PANETTA K A, NERCESSIAN S C, et al. Boolean derivatives with application to edge detection for imaging systems[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B:Cybernetics, 2010, 40(2):371-382.
[2] LI W W, WANG Z, HUANG J L. The e-derivative of Boolean functions and its application in the fault detection and cryptographic system[J]. Kybernetes, 2011, 40(6):905-911.
[3] LI H T, WANG Y Z. Boolean derivative calculation with application to fault detection of combinational circuits via the semi-tensor product method[J]. Automatica, 2012, 48(4):688-693.
[4] LEE S C, AULA F T. Fault detection in word-level NanoICs using vector Boolean derivative[C]//Proceedings of SPIE-Nanosensors, Biosensors, and Info-Tech Sensors and Systems. San Diego:Society of Photo-Optical Instrumentation Engineers (SPIE), 2013, 86910E. Doi:10.1117/12.2009527.
[5] LIU Z B, WANG Y Z, LI H T. New approach to derivative calculation of multi-valued logical functions with application to fault detection of digital circuits[J]. IET Control Theory Applications, 2014, 8(8):554-560.
[6] ZHANG Z J. The correlation between the internal construction and the property of Bent functions in cryptographic system[C]//2nd IEEE International Conference on Computer Science and Information Technology. Beijing:IEEE Conference Publications, 2009:329-332.
[7] LI W W. Correlation-immunity study of balanced H-Boolean functions[J]. Tongxin Xuebao/Journal on Communications, 2013, 34(8):82-87.
[8] HUANG J L, WANG Z, ZHANG J. Effects of e-derivative on algebraic immunity, correlation immunity and algebraic degree of H Boolean functions[J]. Applied Mechanics and Materials, 2013, 411/412/413/414:45-48.
[9] DUAN M, YANG M H, SUN X R, et al. Distinguishing properties and applications of higher order derivatives of Boolean functions[J]. Information Sciences, 2014, 271:224-235.
[10] 厉晓华, 郑强, 杭国强. 基于K图的布尔E-导数计算的图形方法[J]. 浙江大学学报(理学版), 2013, 40(3):260-262. LI X H, ZHENG Q, HANG G Q. Graphic method calculating Boolean E-derivative based on K-map[J]. Journal of Zhejiang University(Science Edition), 2013, 40(3):260-262.
[11] 马汝星, 陈偕雄. 基于最小项表计算e导数的方法[J]. 浙江大学学报(理学版), 2013, 40(5):531-534. MA R X, CHEN X X. Method of computing e-derivative based on minterm table[J]. Journal of Zhejiang University(Science Edition), 2013, 40(5):531-534.
[12] 马汝星. 基于分解表计算逻辑函数e导数的新方法[J]. 科技通报, 2014, 30(1):141-144. MA R X. A new method of calculating e-derivative of Boolean function based on the decomposition table[J]. Bulletin of Science and Technology, 2014, 30(1):141-144.
[13] WANG F. Research on properties of e-partial derivative[J]. Journal of Theoretical and Applied Information Technology, 2013, 47(1):201-205.
[1] 李娟. 高阶对流Cahn-Hilliard型方程的二阶线性化差分方法[J]. 浙江大学学报(理学版), 2022, 49(1): 60-65.
[2] 张萍,覃桂茳,杨甲山. 具正负系数和多变时滞的高阶非线性中立型差分方程非振动解的存在性[J]. 浙江大学学报(理学版), 2022, 49(1): 41-48.
[3] 有名辉, 范献胜. 关联余割函数的Hilbert型不等式及其应用[J]. 浙江大学学报(理学版), 2021, 48(2): 200-204.
[4] 张萍, 杨甲山. 一类高阶非线性非自治动态方程的动力学性质[J]. 浙江大学学报(理学版), 2020, 47(6): 681-686.
[5] 王芳. 关于布尔函数的布尔导数、e导数和c导数相互关系的研究[J]. 浙江大学学报(理学版), 2019, 46(4): 460-465.
[6] 王琪. 双曲空间中全脐超曲面与高斯映照像[J]. 浙江大学学报(理学版), 2016, 43(5): 537-538.
[7] 邱晓华, 陈偕雄. 关于高阶e导数性质之研究[J]. 浙江大学学报(理学版), 2013, 40(4): 424-427.