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

摘要：

覆盖等效性检测指验证2个具有不同表达式的组合逻辑电路是否实现相同的函数功能.通过扩展余子式概念,提出一种基于乘积项余子式分解及重言式判别的组合逻辑电路覆盖等效性检测算法.首先将等效性检测问题分解成电路包含检测子问题,逐一求取其中一个电路表达式对另一个电路表达式各乘积项的余子式;然后在建立各乘积项余子式的香农结构图基础上判断其是否重言式;最后根据重言式判别结果确定两电路间是否覆盖等效关系.该算法通过求取乘积项余子式对逻辑函数进行分解和降阶处理,从而加快了覆盖等效性验证速度.电路测试结果表明,文中算法是稳定有效的;对EXPRESSO软件集成的3种算法所得电路的测试结果表明,与基于真值表和BDD的2种检测算法相比,该算法具有明显的速度优势.

关键词：组合逻辑电路、覆盖等效性、余子式、香农结构图

所属期刊栏目：29

分类号：TP391.41(计算技术、计算机技术)

资助基金：国家自然科学基金61306041, 61234002;浙江省自然科学基金 LY13F040003

在线出版日期：2017-12-04（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：2140-2146