高级检索
瞿婷, 王伦耀, 夏银水, 储著飞. 逻辑函数高阶布尔c-偏导数求解的算法实现[J]. 计算机辅助设计与图形学学报, 2017, 29(8): 1557-1562.
引用本文: 瞿婷, 王伦耀, 夏银水, 储著飞. 逻辑函数高阶布尔c-偏导数求解的算法实现[J]. 计算机辅助设计与图形学学报, 2017, 29(8): 1557-1562.
Ju Ting, Wang Lunyao, Xia Yinshui, Chu Zhufei. The Algorithm for Logic Function High-order c-Partial Boolean Derivative[J]. Journal of Computer-Aided Design & Computer Graphics, 2017, 29(8): 1557-1562.
Citation: Ju Ting, Wang Lunyao, Xia Yinshui, Chu Zhufei. The Algorithm for Logic Function High-order c-Partial Boolean Derivative[J]. Journal of Computer-Aided Design & Computer Graphics, 2017, 29(8): 1557-1562.

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

The Algorithm for Logic Function High-order c-Partial Boolean Derivative

  • 摘要: 针对已有方法在求解布尔c-偏导数时只能解决小规模电路的问题,提出一种基于变量操作运算的大函数高阶布尔c-偏导数求解算法.首先将高阶布尔c-偏导数求解运算转化为逻辑函数的展开运算;然后根据乘积项是否包含需要展开的变量将函数分解成需要展开和不需要展开的二部分,进一步提高算法的速度.文中算法用C语言编程实现,并用MCNC测试电路进行了测试,结果表明,该算法能快速实现大函数高阶c-偏导数的求解;其效率与函数拆分的结果有关,但对输入变量的数量不敏感.

     

    Abstract: To cope with the problem that the existing algorithms were unable to calculate the high-order c-partial derivative of the Boolean functions with large number of inputs,an effective algorithm based on the bit-wise operation was proposed.And the calculation of the high-order c-partial derivative was finished by the product terms expansion using bit-wise operation,rather than by the definition.Further,in order to accelerate the calculation speed,the logic function was divided into two parts according to the variables whether they were needed to be expanded or not.The proposed algorithm was implemented in C and tested under MCNC benchmarks.The 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 result of function decomposition,but less affected by the number of input variables.

     

/

返回文章
返回