基于BDD和布尔差分的组合电路测试生成方法摘要：引入布尔差分的思想，对被测电路函数的BDD结构进行判断生成测试向量。本方案较传统的以图进行搜索的ATPG方法有效地减少了时空开销，并将布尔差分的理论方法应用于实际。实验表明，本方案可以有效地进行测试生成。关键词：二元决策图；布尔差分；自动测试向量生成中图分类号：TP331文献标志码：A文章编号：1001-3695(2008)05-1450-03在数字系统的测试中，ATPG是对测试电路产生测试向量的过程[1]。通常ATPG算法首先给电路插入一个故障；然后通过在电路输入端激活这个故障，并将其产生的响应通过电路传播到输出端。若输出信号与无故障电路的期望值不同，就可以检测到这个故障了。针对组合电路中固定型故障，目前存在一些ATPG算法。最基本的是布尔差分法[2，3]。它描述严格，是研究组合电路测试生成的理论基础。最经典的是Roth的D算法[4]，采用D立方建立了ATPG的运算。此外还有Geol的PODEM算法、Fujiwara的FAN算法[6]等，在回溯和加快搜索速度上作出了很大的贡献。Geol在其PODEM算法[5]中采用二元决策树（binarydecisiontree，BDT）进行搜索。Akers[7]提出的使用BDD来表述逻辑电路则更为实际。近年来，BDD的理论有了更进一步的完善和发展[8,9]，并更多地运用到数字电路设计中的验证、综合[10]及自动测试模式生成[11]。??本文尝试采用简洁的简化排序二元决策图（reducedorderedBDD,ROBDD）来对组合电路进行表示及运算；同时融入布尔差分的思想，对被测电路BDD结构进行判断，从而进行测试生成。??1BDD的相关知识??1．1使用BDD表示布尔函数??对式（1）,将x??1分别设置为0值和1值时，在运算中就会产生两种不同的情况，以图的形式表述如图1（a）（图中的虚线边表示节点变量取0值，为节点的左后继；同理实线边表示取1值，为右后继）所示。接下来继续对此函数中的另外两个变量x??2和x??3也进行同样的展开操作，直至全部变量都被展开。至此，布尔函数f=(x??1∧x??2)?荬Cx??3中可能的变量取值及运算结果全部由图1（b）表示。??图1（b）称为二元决策树。Geol首先在组合电路ATPG的文献[5]中采用这种二元树。一个表示含有n个变量函数的二元决策树中有2(n+1)-1个节点，这对于含有变量较多的布尔函数表述的开销是很大的。??注意到在对函数生成决策树时根据一定的变量顺序（图1（b）中的（x??1,x??2,x??3）），并且处于树的同一层的节点标记一样（图1（b）中自上向下第二层均为x??2），这种决策树称做排序二元决策树。在决策树的形式中，存在很多重复的相同节点（特别是终节点，图1（b））。通过相应的化简，可以得到排序决策树相对应的BDD形式。在此引入节点冗余和节点等价的概念。??定义1对于一个决策树（或决策图）中的任一节点，如果其左右后继相同，则此节点为冗余节点。??定义2对于一个决策树（或决策图）中的任意两个节点，如果它们具有相同的标记、左后继及右后继，则这两个节点称为等价节点。??如图1（b）中自上而下第二层中左边的x??2节点为冗余节点，第三层中自左向右第1、2、3个x??3节点均两两为等价节点。针对上述两种情况的节点，可以采取相应的化简操作进行化简。节点化简操作如下：??a)如果节点a为冗余节点，则将节点a删除并将其所有入边指向其任一后继；??b)如果节点a和b等价，则删除节点b并将其所有入边指向节点a。??通过以上两个操作对图1（b）进行相应的化简，继而生成函数f=(x??1∧x??2)?荬Cx??3所对应的BDD（图2）。BDD是一个有根节点的有向无环图（DAG），含有一个或两个出度为0的终节点（即0或1节点）、若干出度为2的内部节点。对于一个含有n个变量的函数，其对应BDD的节点个数范围为[n+2,??2??n+1]（上限为理论值，实际中很难达到），相对于BDT的表达方式，时间空间开销大量减少，对于表述函数更为实际有效。??对于函数F，将其变量根据一定的顺序（x??1,x??2,x??3,…,x??n）生成的BDD称为OBDD(orderedBDD，排序二元决策图)。当OBDD满足非冗余性（不存在冗余节点）及惟一性（不存在等价节点）时，被称为ROBDD(reducedOBDD，简化排序二元决策图)，简称BDD。??1．2BDD间的同构??笔者注意到定义2中提到的两个节点等价的情况是发生...