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

发布时间：2019-08-14 06:42

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

卡诺图,函数,最小项,乘积项

仍?低于常规的指数时间,从而使算法能够地有效解决较大规模电路的覆盖等性检测问题.1函数间包含关系判定定理1.1基本概念函数间包含关系判断涉及蕴含项、覆盖、覆盖等效、重言式和余子式等基本概念.在介绍这些概念的基础上,将介绍扩展性概念乘积项余子式.不失一般性,下文中逻辑函数表达式均是积之和形式.蕴含项.在组合逻辑函数表达式中,每个乘积项及其对应的最小项都称为该函数的蕴含项.同时,乘积项间利用代数式等效操作得到的乘积项也是该函数的蕴含项[10].对于两变量函数11213123fxxxxxxx,其卡诺图如图1所示.显然,121323123xx,xx,xx,xxx等都是f1的蕴含项..图1函数f1的卡诺图覆盖.任意一个包含且仅包含函数所有最小项信息的蕴含项集合构成函数的一个覆盖.当覆盖中的乘积项都是最小项时,称为最小项覆盖.函数的不同覆盖之间是等效的,且任意逻辑函数均可用它的任意覆盖来等效表示[11].结合图1,两蕴含项集合1213{xx,xx}和123{xxx,23123xx,xxx}都是函数f1的覆盖.覆盖等效.若两函数可用同一个最小项覆盖表示,称它们是覆盖等效的.函数212323123fxxxxxxxx的3个乘积项显然构成它的一个覆盖12323123{xxx,xx,xxx}.由于此覆盖与函数f1对应同一个最小项覆盖,故函数f1和f2是覆盖等效的.重言式.若对于输入变量的任意确定性取值,某函数的值恒为逻辑1,称该函数是重言式.容易验证,函数311fxx和函数412fxx131231xxxxxx都是重言式,因为这2个函数在各自输入变量所有可能取值下的逻辑值都是1.其中函数f4的卡诺图如图2所示.余子式.式(1)所示逻辑函数的香农展开中,1xf和1xf分别称为此函数对于1x和1x的余子式.111111212(,,)(1,,,)(0,

函数,乘积项,包含关系,重言式

2142计算机辅助设计与图形学学报第29卷图2函数f4的卡诺图本文称1x为拆分变量.2个余子式可通过把拆分变量的对应形式(即原形或反变量)等于1代入原函数计算得到.对余子式的概念进行扩展,可得函数对具体乘积项的余子式.乘积项余子式.设某乘积项12kmxxx,函数f对于m的余子式fm的计算方法为1212((()))kkmxxxxxxfff(2)即把m的所有分量ix等于1代入函数f即得fm.式(2)中,分量ix(i1,2,,k)为对应变量的原形ix或取反形式ix;fm的计算结果与拆分变量的选取顺序无关,即对于m的任意2个分量ix和jx(i,j=1,2,…,k,ij),有()()ijjixxxxff.显然,变量或乘积项余子式的求取本质上是基于某个或某些变量对原函数降阶分解的过程.1.2函数包含关系及其判定定理函数表达式中,对于某个或某些变量未出现的乘积项,总是可以应用等式1iixx扩展得到该乘积项对应的所有最小项.故基于覆盖的定义,可以确定函数间是否存在包含关系.函数间的包含关系.对于2个组合逻辑函数f和g,若f的一个覆盖包含g的所有乘积项信息,则该覆盖必包含g的所有最小项信息,称f包含g,记为fg.若两函数f和g存在相互包含关系,则它们是覆盖等效的.因为相互包含表明,函数f的任一覆盖必包含且仅包含g的所有最小项,即f的任一覆盖同时也是g的覆盖.故f和g是覆盖等效的.可见,包含关系判定是函数覆盖等效性检测的关键步骤.利用余子式和重言式概念,本文提出函数包含关系判定定理.定理1.对于函数f和g,若f对g的每个乘积项的余子式都是重言式,则f包含g.证明.设函数f对g的乘积项mi的余子式为.imfimf是重言式表明:把mi的每个分量ix等于1代入函数f,所得结果恒为1;或者说,mi为1时恒有f
【作者单位】：宁波大学电路与系统研究所;
【基金】：国家自然科学基金(61306041,61234002) 浙江省自然科学基金(LY13F040003)
【分类号】：TN791

【相似文献】