互联网 qkzz.net
全刊杂志网:首页 > 女性 > 文章正文
刊社推荐

基于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]中采用二元决策树(binary decision tree,BDT)进行搜索。Akers[7]提出的使用BDD来表述逻辑电路则更为实际。近年来,BDD的理论有了更进一步的完善和发展[8,9],并更多地运用到数字电路设计中的验证、综合[10]及自动测试模式生成[11]。
  本文尝试采用简洁的简化排序二元决策图(reduced ordered BDD,ROBDD)来对组合电路进行表示及运算;同时融入布尔差分的思想,对被测电路BDD结构进行判断,从而进行测试生成。
  
  1BDD的相关知识
  
  1.1使用BDD表示布尔函数
  
  对式(1),将x1分别设置为0值和1值时,在运算中就会产生两种不同的情况,以图的形式表述如图1(a)(图中的虚线边表示节点变量取0值,为节点的左后继;同理实线边表示取1值,为右后继)所示。接下来继续对此函数中的另外两个变量x2和x3也进行同样的展开操作,直至全部变量都被展开。至此,布尔函数f=(x1∧x2)x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形式。在此引入节点冗余和节点等价的概念。 ......
很抱歉,暂无全文,若需要阅读全文或喜欢本刊物请联系《计算机应用研究》杂志社购买。
欢迎作者提供全文,请点击编辑
分享:
 

了解更多资讯,请关注“木兰百花园”
分享:
 
精彩图文


关键字
支持中国杂志产业发展,请购买、订阅纸质杂志,欢迎杂志社提供过刊、样刊及电子版。
关于我们 | 网站声明 | 刊社管理 | 网站地图 | 联系方式 | 中图分类法 | RSS 2.0订阅 | IP查询
全刊杂志赏析网 2017