逻辑函数高阶布尔e偏导数求解算法的实现

doi:10.3785/j.issn.1008-9497.2018.04.008

摘要
图/表
参考文献
相关文章 (2)

全文: PDF (1052 KB) HTML( )
输出: BibTeX | EndNote (RIS)

摘要针对已有方法在求解布尔e偏导数时只能解决小规模电路的问题，提出了一种基于逻辑函数不相交运算的大函数高阶布尔e偏导数的求解算法.该方法将逻辑函数转化为不相交乘积项的集合，用逻辑函数的不相交运算替代布尔e导数运算中的逻辑“与”运算；并将不包含待求导变量的乘积项拆分出来，不参与布尔e导数运算，以达到降低算法复杂度、提高算法速度的目的.提出的算法用C语言编程实现，并用MCNC测试电路进行了测试.实验结果显示，本算法能快速实现大函数高阶布尔e偏导数的求解，求解效率与参与不相交运算的乘积项数量有关，但对输入变量的数量不敏感.

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	罗文强
	王伦耀
	夏银水

关键词 ： 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

ZTFLH:

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偏导数求解算法的实现[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.

链接本文:

http://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2018.04.008 或 http://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.
[14] 王玉花, 王伦耀, 夏银水. 基于不相交项并行列表技术的FPRM实现[J]. 电子与信息学报, 2014, 36(9):2258-2264. WANG Y H, WANG L Y, XIA Y S. FPRM conversion using parallel tabular technique with disjointed products[J]. Journal of Electronics & Information Technology, 2014, 36(9):2258-2264.