投审稿平台


投稿指南
下载专区
地  址:北京市海淀区中关村科学院
南路6号中国科学院计算所342号 [地图]
《计算机辅助设计与图形学学报》编辑部
邮政编码:100190
电  话:010-62562491
          010-62600342
订阅信息
ISSN      1003-9775
CN        11-2925/TP
邮发代号:82-456
单    价:80.00元
全年订价:960.00元
在线期刊

基于余子式的组合逻辑电路覆盖等效性检测算法

张会红, 汪鹏君*, 陈治文, 汪 涛
(宁波大学电路与系统研究所 宁波 315211)
分类号: TP391.41
出版年,卷(期):页码: 2017 , 29 ( 11 ): 2140-2146 张会红
摘要: 覆盖等效性检测指验证2个具有不同表达式的组合逻辑电路是否实现相同的函数功能. 通过扩展余子式概念, 提出一种基于乘积项余子式分解及重言式判别的组合逻辑电路覆盖等效性检测算法. 首先将等效性检测问题分解成电路包含检测子问题, 逐一求取其中一个电路表达式对另一个电路表达式各乘积项的余子式; 然后在建立各乘积项余子式的香农结构图基础上判断其是否重言式; 最后根据重言式判别结果确定两电路间是否覆盖等效关系. 该算法通过求取乘积项余子式对逻辑函数进行分解和降阶处理, 从而加快了覆盖等效性验证速度. 电路测试结果表明, 文中算法是稳定有效的; 对EXPRESSO软件集成的3种算法所得电路的测试结果表明, 与基于真值表和BDD的2种检测算法相比, 该算法具有明显的速度优势.
关键词: 组合逻辑电路; 覆盖等效性; 余子式; 香农结构图
A Cofactor Based Logic Coverage Equivalence Checking Algorithm for Combina-tional Circuits
Zhang Huihong, Wang Pengjun*, Chen Zhiwen, and Wang Tao
(Institute of Circuits and Systems, Ningbo University, Ningbo 315211)
abstract: Coverage equivalence checking of combinational circuits means to check whether two circuits with different expansions implement the same function. By expending the conception of cofactor, a logic coverage equivalence checking algorithm for combinational circuits is proposed which is based on decomposition and tautology determination of product term’s cofactors. Equivalence checking problem is firstly decomposed into two containment checking sub-problems. Cofactors of one circuit to each product term of the other circuit are calculated one by one, and then tautology checking is executed on each of these cofactors by developing their Shannon diagrams. Based on results of tautology checking, it will be finally deduced whether the two circuits are coverage equivalent. During calculation of product term’s cofactors, decomposition and order reduction of the logic functions are implemented which lead to speedup of the equivalence checking. Experimental results show that the proposed algorithm is stable and effective. And, data on MCNC Benchmark couples optimized by the three algorithms embodied in EXPRESSO indicated that the proposed algorithm has an obvious speed advantage over the other two equivalence checking algorithms which are based on truth table and BDD, respectively.
keyword: combinational circuits; coverage equivalence; cofactor; Shannon diagram
 
Copyright © 2004《计算机辅助设计与图形学学报》版权所有
电话:010-62600342 传真:010-62562491
E_mail:jcad@ict.ac.cn