（计算机科学与技术专业论文）基于sat的vlsi测试向量自动生成技术.pdf

授 提 同 中图分类号：t p 3 9 1 7 u d c ：0 0 4 9 学校代码：1 0 0 0 4 密级：公开 北京交通大学 硕士学位论文 基于s a t 的v l s i 测试向量自动生成技术 s a t - b a s e da u t o m a t i ct e s tp a t t e r ng e n e r a t i o no fv l s i 作者姓名：付宇 导师姓名：吴为民 学位类别：工学 学科专业：计算机科学与技术 学号：0 8 1 2 0 5 6 2 职称：副教授 学位级别：硕士 研究方向：电子设计自动化 北京交通大学 2 0 1 0 年7 月 致谢 本论文的工作是在我的导师吴为民副教授的悉心指导下完成的，吴为民副教 授严谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢两 年来吴为民老师对我的关心和指导。 吴为民副教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都 给予了我很大的关心和帮助，在此向吴为民老师表示衷心的谢意。 吴为民副教授对于我的科研工作和论文都提出了许多的宝贵意见，在此表示 衷心的感谢。 感谢国家自然科学基金( 批准号：6 0 6 7 3 0 3 4 ) 的资助，及北京交通大学科技 基金( 批准号2 0 0 7 x m 0 1 l 和2 0 0 8 r c 0 0 2 ) 的部分资助。 在实验室工作及撰写论文期间，陈科等同学对我论文中的遇到的困难给予了 热情帮助，在此向他们表达我的感激之情。 另外也感谢家人，他们的理解和支持使我能够在学校专心完成我的学业。 摘要 集成电路设计过程中，随着电路规模和复杂度的增大，设计故障变得越来越 多，因此对于设计故障的测试方法也提出越来越高的要求。自动测试向量生成算 法便是其中的一种，它是利用一些算法例如d 算法，通路敏化法或者布尔差分法 自动产生出能够检测某些故障的测试向量。本论文以布尔可满足性算法作为基础， 从下面三个方面对测试向量自动生成算法进行了研究： 首先提出并实现了针对组合电路单固定型故障的测试向量生成算法。在该算 法中，我们使用了类似丁布尔差分法中的思想，将正确电路和错误电路使用异或 门组合在一起，并转化为相关的c n f 范式，利用s a t 求解器寻找测试向量。 然后利用组合电路的单固定型测试向量生成算法，求出整个电路的所有故障 的测试向量集合，即故障字典。然后，以故障字典为基础，生成一个二叉的故障 诊断树，以便于在检测电路中某条线路故障的时候，可以方便的得到对应的测试 向量集合。 最后提出了对通路时延故障测试向量的自动生成算法，该算法采用与组合电 路单固定故障测试向量生成算法类似的思想，但以7 值逻辑系统为基础，使得在 生成完整的c n f 范式时与前边的算法有差异。该算法主要针对鲁棒性和非鲁棒性 测试产生测试向量。 我们用c 语言实现了上面三个算法并以i s c a s 系列电路对算法进行了检验， 实验结果表明了算法的有效性和可行性。 关键词：可满足性问题；单固定型故障；故障字典；测试向量自动生成；通路时 延故障 分类号：t p 3 9 1 7 a b s t r a c t a st o d a y sv l s id e s i g n sg r o wi n s c a l ea n dc o m p l e x i t y , e r r o r sb e c o m em o r e f r e q u e n ta n dd i f f i c u l tt ot r a c ki nt h ed e s i g np r o c e s so fi n t e g r a t e dc i r c u i t s ，s ot e s t i n g t e c h n i q u e sf o rf a u l t sa r em o r ea n dm o r er e q u e s t e d ，o n eo fw h i c hi sa u t o m a t i ct e s t p a t t e r ng e n e r a t i o n ( a t p g ) a t p gc a ng e n e r a t ea u t o m a t i c a l l yt e s tv e c t o r sf o rs p e c i f i c f a u l t su s i n gs o m ea l g o r i t h m ss u c ha sd ，p a t hs e n s i b i l i z a t i o no rb o o l e a nd i f f e r e n c e t h i s p a p e rs t u d i e st h ea t p ga l g o r i t h m sw h i c hu s es a t i s f i a b i l i t y ( s a t ) s o l v e ra st h es e a r c h e n g i n e t h ec o n t e n t sa r eo u t l i n e da sf o l l o w i n g ： f i r s t ，t h ea t p ga l g o r i t h mf o rs i n g l es t u c k a tf a u l t so fb i n c o m a t i o n a lc i r c u i ti s p r e s e n t e da n di m p l e m e n t e d w eu s eam e t h o ds i m i l a r t ob o o l e a nd i f f e r e n c e ，i e c o n s t r u c tan e wc i r c u i tb yx o r i n gt h ef a u l t ya n df a u l t f r e ec i r c u i t sa n dt r a n s l a t et h e n e wc i r c u i ti n t oac n fw h i c hw i l lb es e n tt oas a ts o l v e rf o rf i n d i n gt h et e s tv e c t o r s s e c o n d ，u s i n ga b o v ea l g o r i t h m ，w eg e tt h es e to ft e s tv e c t o r sf o ra l lf a u l t si nt h e c i r c u i t ，w h i c hi sc a l l e df a u l td i c t i o n a r y t h ef a u l td i a g n o s i st r e ec a nt h e nb eg e n e r a t e d a c c o r d i n gt ot h ef a u l td i c t i o n a r yt of i n de a s i l yt h ec o r r e s p o n d i n gs e t so f t h et e s tv e c t o r s f o rs p e c i f i cf a u l t si nt h ec i r c u i t l a s t ，t h ea t p gt e c h n i q u e sf o rp a t hd e l a yf a u l t sa r es t u d i e d i te x p l o i t ss i m i l a ri d e a t ot h a tu s e df o rs i n g l es t u c k a tf a u l t ，b u ti sb a s e do n7 - v a l u e sl o g i cs y s t e ms ot h ec n f g e n e r a t i o np r o c e s sd i f f e r s t h ea l g o r i t h mc a ng e n e r a t et e s tv e c t o r sf o rr o b u s ta n d n o n - r o b u s tt e s t i n g t h ea b o v et h r e ea l g o r i t h m si si m p l e m e n t e di nca n dt e s t e do nas e to fi s c a s c i r c u i t s t h er e s u l t so b t a i n e dd e m o n s t r a t et h ee f f e c t i v e n e s sa n df e a s i b i l i t yo ft h e p r o p o s e da l g o r i t h m s k e y w o r d s ：s a t ；s i n g l es t u c k a tf a u l t s ；f a u l td i c t i o n a r y ；a u t o m a t i ct e s tp a t t e r n g e n e r a t i o n ；p a t hd e l a yf a u l t c l a s s n o ：t p 3 9 1 7 目录 摘要i i i a b s t r a c t i v 1 绪论7 1 1课题研究的背景和意义7 1 1 1 自动测试向量生成算法研究的现状7 1 1 2 测试生成算法的发展趋势8 1 2课题研究的内容。9 1 3论文主要内容安排9 2组合电路故障测试研究1 1 2 1电路故障测试原理1 l 2 1 1 逻辑故障模型1 1 2 1 2 组合电路的故障检测原理1 2 2 2组合电路故障测试的经典算法1 3 2 2 1 通路敏化法1 4 2 2 2d 算法15 2 2 3 布尔差分法1 7 2 3本章小结2 0 3组合电路中单固定型故障测试向量生成算法2 l 3 1单固定型故障测试的基本知识2 1 3 1 1 基本概念2 l 3 1 2 符号定义2 2 3 2单固定型故障测试向量生成算法2 2 3 2 1 基本知识2 2 3 2 2 单固定型故障测试向量生成算法描述2 4 3 2 3 实例分析2 7 3 3实验结果分析3 0 3 4 本章小结3l 4基于s a t 的故障字典生成算法3 2 4 1故障字典的基本知识3 2 4 2故障字典3 2 4 2 1 故障字典生成方案3 3 4 2 2 故障字典生成算法3 4 4 3故障诊断树3 5 4 3 1 故障诊断树生成方案3 6 4 3 2 故障诊断树的算法3 7 4 4实验结果分析3 8 4 5本章小结4 0 5通路时延故障测试向量生成算法4 1 5 1时延故障测试的基本知识4 1 5 1 1 基本概念4 1 5 1 2 鲁棒性测试与非鲁棒性测试4 2 5 1 3 时延故障测试4 3 5 1 47 值逻辑系统4 5 5 2基于s a t 可满足性的通路时延故障测试向量生成算法4 7 5 2 1 基本知识4 7 5 2 2 通路时延故障测试向量生成算法描述4 9 5 2 3 实例分析5 0 5 3实验结果分析5 1 5 4本章小结5 2 6总结和展望5 3 6 1论文工作终结5 3 6 2工作展望5 4 参考文献5 5 作者简历5 8 独创性声明5 9 学位论文数据集6 0 1 1 课题研究的背景和意义 1 绪论 在过去的几十年里，随着微电子技术的高速发展和人们对信息技术的大量需 求，使得现代集成电路系统的规模和复杂程度日趋提高，这必将导致对未来集成 电路系统的设计和制造提出更高的要求。 一方面，要在包含数以亿计的晶体管电路中避免出现设计错误，这是一项非 常艰巨的任务。另一方面，从集成电路设计的角度看，系统设计要满足规范的需 求，并且在设计的各个阶段的等价性检验也对设计验证提出了很高的要求。据资 料显示，目前测试成本已经达到了所研制设备成本的5 0 ，甚至7 0 。 因此，必须寻找一些可以信赖的、简单可行的测试方法，以检测存在于电路 内部的故障。根据电路的类型可将故障诊断分为两类：数字系统的故障诊断和模 拟系统的故障诊断。由于模拟系统自身的特点，使得其故障诊断相比数字系统更 加复杂。由于模拟信号量是连续的，任何一个元件的参数超过其容差时就被认定 为是故障，因此模拟电路的故障状态是无限的。目前，传统的时域和频域测试方 法，对于模拟电路系统是久经考验而行之有效的，但对于复杂的数字电路系统却 未必能奏效，甚至会无能为力。因此，在这个背景之下产生了针对数字电路故障 诊断的各种方法，其中自动测试向量a t p g ( a u t o m a t i ct e s tp a t t e r ng e n e r a t i o n ) 便是 其中的一种诊断方法，本论文主要研究的内容是基于可满足性求解( b o o l e a n s a t i s f i a b i l i t y , 简称s a t ) 的a t p g 算法，分别针对组合电路中的单固定型故障，故障 字典，以及通路时延故障这三个方面进行研究，并且对每个部分都提出了相应的 a t p g 算法。 1 1 1 自动测试向量生成算法研究的现状 1 9 5 9 年e l d r e d 在其发表的一篇文章里第一次提出了关于组合电路的测试方 法，但该方法是一个比较简单的测试向量生成算法，不能解决两级以上的组合电 路的故障测试问题。 1 9 6 6 年d b a r m s t r o n g 根据e l d r e d 的基本思想提出了一维通路敏化的方法， 该方法的主要思想是在多级门电路中寻找一条从故障点到原始输出端的敏化通 路，最终通过原始输出端的输出值来检测电路故障。 7 1 9 6 8 年s e l l e r s 等人提出了布尔差分法，它是通过数字电路中的布尔方程式的 差分运算求出测试向量集合的一般表达式，从而可以求出所给故障的全部测试向 量。在布尔差分法的发展史中具有代表性的算法是主路径法以及近些年来发展起 来的二元判定图( b d d ) 测试向量生成算法。 在组合电路测试向量生成算法中，d 算法是对测试向量生成算法的发展影响 较大的一个算法。它是由r o t h 等人在1 9 6 6 年提出的，该算法克服了一维通路敏 化法的局限，采用多维敏化的思想，即同时敏化从故障位置到电路的所有输出端 的全部通路。 1 9 8 1 年g o e l 对d 算法进行改进提出了p o d e m 算法，这种算法是一种分支限 晁的隐式枚举算法，采用逐个地给原始输入赋值的办法为给定的故障生成测试向 量。1 9 8 3 年f u j i w a r a 等人提出了f a n 算法，该算法在减少回退次数，降低每一次 的回退时间以及扇出点等方面都做了细致处理。 2 0 0 1 年e g i z d a r s k i 等人提出了基于布尔可满足性( b o o l e a ns a t i s f i a b i l i t y , 简称 s a t ) 的测试向量生成算法，该方法用c n f ( c o n j u c t i v en o r m a lf o r m ) 范式来表示电 路模型，在此基础上作者又提出了基于蕴 ( i m p l i c a t i o ng r a p h ，简称i g ) 的测试向 量生成算法。在本论文中，我们主要研究的是基于s a t 的a t p g 算法。 我国在集成电路的测试方面也有很深入的研究。比如中科院计算所，清华大 学，上海交通大学，电子科技大学等都有很强的实力。尤其是近几年中科院计算 所在龙芯研发的驱动下，取得了非常好的成果。 可满足性求解技术在近十几年迅速发展，成为求解大型复杂问题的强大工具。 基于s a t 求解器例如z c h a f f 已成功地应用于很多其他领域，尤其在大型、复杂、 关键性的软件、硬件、以及协议的验证和测试中。本次论文中提出的算法实质就 是如何求出满足于s a t 求解器的c n f 范式，从而得出故障的测试向量。 1 1 2 测试生成算法的发展趋势 测试在集成电路的设计中占有越来越重要的地位，但同时也面临着越来越多 的困难，例如电路规模越来越大，复杂度越来越高等问题，为了解决这些困难， 人们意识到必须从集成电路设计自动化的角度全局地考虑测试问题。目前，测试 向量生成算法未来发展的几个重要方面如下： 1 进一步提高已有的测试向量生成算法的效率和研究新的测试方法与技术。 2 研制专家系统和并行处理方法。 3 进行可测试性设计。 8 1 2 课题研究的内容 本课题是以组合电路为研究对象，并且将为特定故障产生测试向量作为主要 目标，重点研究了组合电路中的单固定型故障，故障字典以及通路时延故障测试 向量生成算法。主要研究内容如下： 1 组合电路中的单固定型故障测试向量生成算法。该算法使用了图的拓扑结 构以及图的深度优先算法，将组合电路转化为相应的c n f 范式，使用s a t 求解器产生相应的测试向量。 2 组合电路中的故障字典生成算法。该算法是以单固定型故障测试向量生成 算法和回溯查找为基础，从而求出所有可测故障的测试向量组成故障字 典。 3 组合电路中的通路时延故障测试向量生成算法。该算法采用了7 值逻辑系 统( 4 个基本向量 s o ，s l ，1 d ，叫j ) ，三个辅助向量 x o , x l , x x ) 来表示时 延故障的特征，并且以单固定型故障测试向量生成算法为基础，对组合电 路中的通路时延故障进行测试，从而生成测试向量。 1 3 论文主要内容安排 论文的主要内容如下： 第一章：绪论。在本章中介绍了故障测试向量生成算法的研究意义、背景以 及现在的发展现状和趋势，同时介绍了本文的主要工作以及内容安排。 第二章：组合电路故障测试研究。在本章中分为两个部分，第一部分是对故 障模型进行介绍，而第二部分则是对组合电路中经典的a t p g 算法进行了说明， 并且对于一些算法使用了具体的例子进行了详尽的讲解。 第三章：组合电路中单固定型故障测试向量生成算法。在本章中提出了一个 针对单固定型故障的算法，该算法分为三个步骤，首先利用图的邻接表结构来表 示组合电路，然后使用深度优先算法对图进行遍历，同时将组合电路转化为相应 的c n f 范式，最后利用s a t 求解器( z c h a f f ) 求出测试向量。 第四章：基于s a t 的故障字典生成算法。在本章中提出了一个生成故障字典 的算法，该算法是以第三章提出的算法为基础分为两个步骤求出电路中所有可测 故障的测试向量，第一步是求出某一故障的测试向量，第二步是搜索与该故障具 有相同性质的故障，循环该过程直到所有的故障都产生测试向量，从而形成故障 字典。该章研究的另一个内容是利用生成的测试向量集合，产生棵故障诊断树， 便于产生测试故障的测试向量集合。 9 1 0 2 组合电路故障测试研究 2 1 电路故障测试原理 在这部分中我们会重点介绍故障模型的概念以及与它相关的一些知识。首先 介绍的是故障模型，由于在建模过程中需要将电路中的逻辑功能与时序功能分开， 所以故障模型也相应地被分为影响逻辑功能的逻辑功能故障以及影响电路运行时 序要求的时延故障。由于在后面的章节中主要使用的是逻辑功能故障模型，因此 在这里我将会把重点放在逻辑故障模型的介绍上。其次在这里还介绍了电路故障 检测的原理，重点介绍了电路故障测试中的敏化概念，并且辅助以实例加以详细 说明。 2 1 1 逻辑故障模型 逻辑故障模型表示物理故障对模型系统行为的影响。将物理故障转化为逻辑 故障后，可以将实际故障问题转变为一个逻辑问题，并且由于逻辑故障与具体的 工艺无关，所以依据逻辑故障模型建立起来的测试与诊断方法对于不同工艺产生 的故障依然有效。 逻辑故障模型可以分为两种类型，一种模型是显式故障模型，它定义了一个 故障空间，该空间内的每个故障可以单独被标识，因此，显式故障模型可以完全 被枚举出来。在故障空间不大的情况下，显示故障模型是具有很大的实用价值的。 另一种模型是隐式故障模型，与显式故障模型不同的是它通过故障的特征属性在 总体上标识感兴趣的故障，从而定义一个故障空间。 逻辑故障模型与系统所用模型类型密切相关，一旦给定一个逻辑故障模型和 一个系统模型，我们就可以确定该故障的系统逻辑功能。因此，按逻辑故障模型 与系统模型的关系又可以分为结构故障模型和功能故障模型。所谓的结构故障模 型是指故障修改了各单元( 部件) 之间的连接关系，而功能故障模型是指该故障 模型改变了系统单元内部的操作，例如功能故障可能会改变一个元件的真值表或 是限制了一个寄存器传输级的操作。本论文主要是针对结构故障模型进行研究， 没有涉及到功能故障模型。 一般来说结构故障模型认为部件是无故障的，只有部件之间的互连( 连线) 可能发生问题，影响连线的典型故障是短路和开路。短路是由于连接了不应被连 接的点引起的，而开路则是由于一个连线的断开引起的。 在许多故障中，固定型故障模型和桥接故障是两个比较常见的故障模型。所 谓的固定型故障模型是指一个信号线被连接到地或者电源上，从而使信号保持在 一个固定的电压值，这样的故障可以表示为固定( s t u c k a t ) 于一个逻辑值1 ，( 0 ，1 ) 的信号，记为s a - v ，在第三章中研究的故障就是这种固定型的故障模型。桥接故 障则是短路故障的代表，它是指两个信号线间的短路通常会引起一个新的逻辑功 能，根据短路所引入的功能的不同，可以区别a n d 桥接故障和o r 桥接故障【l 】f 2 】。 2 1 2 组合电路的故障检测原理 设删为组合电路c 的逻辑函数，其中工表示一个任意的输入向量，荆表示 由电路c 实现的一种变换。因此对于一个特定的输入向量t ，r ( o 表示c 对t 的响 应，而对于一个多输出的电路删表示的是一个输出向量。当电路c 出现一个故障 厂时，它就相当于变成了一个新的电路。假定。是一个组合电路并且其功能函数 为r j ( x ) ，施加包含测试t l , t 2 t o 的向量序列集乃将得到的输出响应与电路c 预期 的输出响应序列r ( t 1 ) ，玎纠y f 功作比较来测试该电路中的故障。如果说一个测试 向量t 能检测到一个故障万那么必然是r f ( t ) 荆，这个也是组合电路故障测试的 基础。如果应用序列t 中的任意向量都可以进行测试，那么对于组合电路来说， 就可以将丁称为一个测试集。对于单输出电路，一个能检测到故障厂的测试向量f ， 它使得r ( o = o 和r l ( t ) = l ，或者反之。因此，检测到故障厂的所有测试的集合可由下 列方程的解给出： 髟= l( 2 1 ) 其中。表示异或运算【3 】【4 1 。 接下来要介绍的是故障测试的另一个重要概念：敏化。首先看一个例子，如 图2 1 所示的电路，输入向量t = 1 0 0 1 ，分别对电路g 2 在具有s t u c k a t 1 固定型故障 和不具有故障两种情况进行模拟，图2 1 给出了这两个模拟的结果，两个结果不同， 并以v v e 的形式给出，其中1 ，和w 分别表示电路无上述故障和有上述故障情况下信 号线上的逻辑值。由于两个输出值不同，因此该路障能够被该测试向量检测到。 图2 1 所表示的例子反映了故障检测的两个基本特性：第一个特性是利用输入 向量t 可以使故障点产生不同的输出值，记为1 ，和坳从而激活故障 即生成一个 错误( 故障效应) 。第二个特性是输入向量t 传播该错误到一个原始输出端w ，即 从故障点到输出端w 之间至少有一条通路里的所有线路上存在着不同的v 和， 例如在图2 1 中由故障产生的错误沿着路径( g 2 g tg ) 传播。电路存在一个故障f 1 2 施加测试t ，如果电路中的一条线上的值由于故障厂的影响发生了变化，则称该线 路通过测试t 被敏化为故障，包含被敏化的线路称为敏化路径【5 1 。 g i x 20 x 30 x ll x 41 图2 - 1 敏化实例电路图 f i g u r e2 - 1i n s t a n c eo fs e n s i t i z a t i o ni nc i r c u i t 2 2 组合电路故障测试的经典算法 0 1 在数字系统中，大部分的故障都可以使用单固定型故障进行模拟，下面介绍 的几种故障测试方法都是以单固定型故障作为基础的。目前，取得故障测试集的 方法分为非确定性测试生成算法和确定性测试生成算法。非确定性测试生成算法 是将软件方法产生的伪随机测试向量与测试人员手工编写的测试集相结合，以产 生被测系统故障的测试集。非确定性生成算法可以使用较少的测试码覆盖较多的 故障，但是由于人工测试的局限性，使得它只适用于小规模的电路。确定性测试 生成算法是采用某种经典的算法，利用程序自动生成该系统的故障测试向量，该 算法是将被测电路转化为计算机可以识别的网表结构或者拓扑结构图，再利用算 法程序产生对应的被测电路故障的测试向量集合，即可以在无需人工干预的情况 下自动产生故障的测试向量集合。确定性测试生成算法的可信度高，特别适用于 大型电路，可用较少的测试向量达到很高的故障覆盖率，但是缺点是随着电路中 门数的增加，它所消耗的资源也是随着电路等效门数进行指数增长。本论文主要 讨论的就是确定性测试生成算法，下面介绍几个故障检测和故障定位的经典方法， 包括通路敏化法，d 算法和布尔差分法。 2 2 1 通路敏化法 在这个章节里我们将详细介绍通路敏化这种故障测试方法，它的基本原理是 寻找一条从故障线路到某一个输出的通道，从而得到该故障线路的测试向量。 通路敏化测试单固定型故障的过程大致可以分为如下五个步骤： 1 寻找一条通路，该通路是以指定的故障线路作为起始点，以电路某一个初 输出端作为终点。 2 若故障线是s t u c k a t 1 ( s t u e k a t 0 ) 故障，则给故障线赋值1 ( o ) 。 3 沿着选择的通路开始进行回溯，对于在通路中出现的所有门电路，除了通 路中的线路外，其余门电路的输入端都要被赋上非控制逻辑值，例如或门 和或非门的非控制逻辑值为o ，与门和与非门的非控制逻辑值为1 。 4 沿着敏化通路的各个门，直到通路的输入端，如果存在一组输入，使得通 路中没有产生矛盾，则过程就此结束。否则，如果产生了矛盾，则从故障 线开始，选择另一条通路，并重复上述的过程。 5 对每一个通路使用前4 步，若它们之中任何一个都不能敏化时，可以通过 增加可能组成一组的通路的个数继续进行敏化，直到每个通路的各种可能 组合都被实验过为止。 在这里要特别说明的是当一个敏化通路出现矛盾的时候，我们可以将通路中 存在多扇出的相关路径组合起来，将新组合出来的这些通路进行敏化，如果成功， 那么当中的所有通路也就被敏化了。因此我们在查找某些故障的敏化通路时，必 须考虑到各个通路同时被敏化的各种可能组合。首先我假设在线路a 上出现了 s t u c k a t o ( s t u c k a t 1 ) 这种固定型故障，那么我选择的通路是口后( 如图2 2 ) ，根据 算法我们将g ，和g 中的输入端d 和g 分别赋予相应的非控制值1 和0 。这时我关 心的是当a 发生故障的时候，是否会引起通路中相关线路的变化，如果发生变化 那么证明该通路可以被敏化，然后就可以寻找相应的测试向量，并且查看是否会 产生矛盾。以啦为例，当g 线路为0 则需要d 或者c 中至少有一个为1 ，由于d 是为1 的，那么e 也必须为1 而c 可以任意为1 或者o 。所以测试线路a 中的s t u c k a t 0 故障的测试向量为0 ，抛抛) = ( 1 ，1 ) ，其中x 表示的是任意值都可以。以此测试向量 作为输入向量，电路输出端z 在正常的情况下为1 ，在故障的情况下为0 ，所以该 测试向量可以通过输出端的不同值来查找错误。 通路敏化的方法比起故障表法来说是具有很大的优势的，但是当通路出现矛 盾时，需要找出成对的双通路、三通路等其他通路的时候，既使利用计算机来完 成也需要大量的搜索和计算。所以这种通路敏化方法仍然存在大量的问题，应用 的范围相当有限。但是现在出现了一些把通路敏化法与神经网络结合起来的研究， 1 4 这种方法是相当值得期待的 6 1 。 x 1 x 2 x 3 2 2 2d 算法 图2 2 通路敏化法电路图 f i g u r e2 - 2p a t hs e n s i t i z a t i o nm e t h o di n c i r c u i t z d 算法是经典的自动测试向量生成算法之一，它对于任意非冗余的组合电路 均能找到故障的测试向量，并且该算法很容易被计算机来实现。 假设z = ，是逻辑电路在正常情况下的逻辑功能函数，那么口= 酗是指电路在 无故障时在故障点a 处的输出值。假设z e = f ( x ) 是电路在具有故障情况下实现的逻 辑功能函数，那么a e = f ( x ) 贝t j 表示的是电路有故障时在故障点a 处的输出值。要使 电路中的故障能够在输出端表现出来，那么至少要满足下面的两个条件，这两个 条件也是后面算法的基础。 z o 乙= 1 ao a e = 1 ( 2 2 ) ( 2 3 ) d 算法的基本思想是找到这样的一个测试向量，使得电路中故障点的逻辑值 在电路正常与故障情况下是不同的，并且这个测试向量还能够将这种不同传递到 电路的输出端。 电路中的任何一个元件功能都可以用一个与或表达式组成的逻辑功能函数进 行表示，例女1 ：i f = x t x 3 + x t x e x 3 + 叫胞呻。对于具有n 个变量的逻辑功能函数可以表 示在一个n 维空间里，而上面的式子还可以表示成厂 门，五砂+ 一，砂+ 以j ，砂，这就 是用奇异立方表示的逻辑函数。所谓的奇异立方就是使用0 、1 以及石( 取值未确 定) 表示的简化的真值表。奇异立方分为两类，一类是使厂一d ，一类是使厂一j 。两 个奇异立方在同一个信号线上的相容赋值运算称为交运算。 电路中线路的状态是由该线路的正常值与故障值做与运算而产生的，它分为 四中状态：o = ( 0 0 ) ，- - - , d = ( 0 1 ) ，d = ( 1 0 ) ，1 = ( 1 1 ) 。这四种状态会贯穿整个d 算法的 执行过程中，下面介绍4 个重要的概念： 故障原d 立方：它是指对一个故障的元器件，为了在它的输出端产生d 或者 啪，所必须赋给该元器件输入端的最小输入条件的立方表示，简记为p d c f 。 传播d 立方：它是指对于一个无故障的元器件，为了使d 或者一d 传播到该 元器件的输出端，而必须赋给该元器件输入端的最小输入条件的立方表示，记为 p d c 。 d 驱赶：它指的是将元器件的某个输入端有故障信号d 或者叼，而输出端的 值未定的情况下使用传播d 立方的规则，以至使故障信号能够传递到该器件的输 出端。 蕴涵：它是指在应用故障d 立方和传播d 立方规则的时候，会确定其他线上 的一些值，对确定值的线路所对应的元器件再使用奇异立方会再确定另一些值， 这个过程就叫做蕴涵。 蕴涵分为前蕴涵和后蕴涵，前蕴涵是指确定值在元器件的输入端，利用奇异 立方确定该元器件的输出端的值，后蕴涵则正好相反，它是指确定值在元器件的 输出端，利用奇异立方确定该元器件输入端的值。 d 算法的可以使用下面的三个步骤进行描述： 1 故障激活，就是将故障显示出来。例如如果一个线路的故障是 s t u c k a t 0 ( s t u c k a t 1 ) ，那么我们就应该将该线路赋值为1 ( o ) ，以区别该故 障值，具体做法就是选择故障的一个原立方，作为初始测试d 立方。 2 d 驱赶，就是将当前测试的d 立方与有关元件的传播d 立方进行d 交， 以使d 或者1 d 信号向前推进，并且将d 交的结果作为新的测试d 立方， d 前驱要进行到输出端出现d 或者1 d 为止。 3 d 算法克服了一维敏化法的局限，它采用了多维敏化思想，即同时敏化从 故障线路到电路的所有输出端的全部通路。 d 算法采用了5 值来对电路进行敏化，该5 值即 0 ，1 , x , d ，加) 。d 算法在执行 的过程中存在着大量的返回操作，为了减少返回操作的次数，缩短计算的时间， 又产生了各种改进的算法，例如p o d e m ( p a t h o r i e n t e dd e c i s i o nm a k i n g ) 算法和 f a n ( f a no u t o r i e n t e d ) 算法。因此，d 算法对于数字电路故障测试向量生成算法 具有重大的意义。 1 6 2 2 3 布尔差分法 布尔差分法的基本思想是将两个布尔函数进行异或操作，其中一个布尔函数 表示的是正常电路，另一个表示的是故障等价电路，因此当布尔差分等于1 的时 候，就说明了电路中存在故障。 在这里假定一个组合电路，其原始输入布尔变量记为工，, x 2 而，它的输出布尔 函数记为f ( x j , x 2 劫，并且假定具有故障的线路使用布尔函数表示为伍 x 2 列。 那么如果在组合电路的某一条通路中存在一个固定故障s t u c k a t o ( s t u c k a t 1 ) 的时 候，我们将存在固定故障s t u c k a t o ( s t u c k a t 1 ) 的组合电路的输出函数表示为 f ( x x 2 , ，x 4 - 1 ，n 规+ 列( 撒 x 2 , ，x i - i ，x i 训) 。所以这两个不同的输出布尔函数 的异或运算称为布尔差分，记为： 纱( 五) 如= 厂( 五，x 2 ，薯一1 ，l ，气+ l ，吒) o 厂( 五，x 2 ，丐一l ，0 ，毛+ l ，矗) = 厂( 五，x 2 ，薯一i ，毛+ l ，x n ) o f ( x a ，x 2 ，薯一l ，薯，薯+ l ，吒) ( 2 4 ) 上面的公式是布尔差分算法的基础，根据布尔差分的定义可以知道，如果故 障线路柏的正确值和故障值不同而导致组合电路输出函数的函数值不相同，则此 布尔函数对尬的布尔差分等于l ，那么就说明这个故障可以被测试。如果这两个输 出函数的函数值相同，则此布尔函数对而的布尔差分等于0 ，则说明该故障是无法 测试的。接下来介绍3 个重要的定义： 定义2 1 ：当且仅当x i 取反的时候，布尔函数脚逻辑值不变，则称为布尔函 数f i x ) 与而无关，记为： 乜，恐，丐_ 1 ，丐，再十l ，吃) = 隔，恐，再- l ，丐，丐h ，) ( 2 5 ) 定义2 2 ：布尔函数f ( x ) 对于x i 和x 1 的双重布尔差分，记为： d 2 f ( x ) d ( x , ，吩) = ，“，恐，毛，毛) 0 岛，x 2 ，毛，“- x j ，x n ) ( 2 6 ) 定义2 - 3 ：当且仅当规和x j 同时取反时，布尔函数删的逻辑值不变，则布尔 函数f ( x ) - 与n 个变量而和而是无关的，记为： 厂( 五，x 2 ，蕾，吒) = 厂( _ ，x 2 ，而，毛) ( 2 7 ) 如果f ( x t ，x 2 , ，x i 以o , x i + ，一列可商 x 2 , ，x i 小，x i + ，列则d f ( x ) d x f = o 。如果布尔 差分为0 ，则说明在x i 处无论是具有s t u c k a t 0 还是具有s t u c k a t 1 故障，输出的布 尔函数都是相同的，也就是说x i 处不管有什么类型的故障对输出都无影响。所以 当布尔差分为0 的时候，而处的故障无论是s t u c k a t 0 还是s t u c k a t 1 都是不可测试 1 7 的。 如果当f ( x l ，x 2 , ，x m ，x i , x i + ，x n ) = f ( x x 2 , ，矩 一x i , x i + ，列的时候， 则 d f ( x o d x r = l 。那么如果布尔差分为l ，说明在x i 处有s t u c k a t 0 或者s t u c k a t 1 处的 布尔函数输出是不相同的，也就是说在x i 处的故障对电路最终的输出是有影响的， 且x i 处的故障是可以被检测出来的。 下面就介绍求单故障测试向量的差分公式，假设m j ，口2 , - - - , 口是向厶x 2 列 故障线路在s t u c k a t 0 上的测试向量，则该公式表示为： 置( 五，x 2 ，) 矽( x i ，) 2 l ( 2 8 ) 反之，假设t ( a t ，a 2 , ，酬是x x ，x 2 列故障线路在s t u c k a t - 1 上的测试向量， 则该公式表示为： 置( 而，恐，x ) d i ( x ) a x , i r ( 懈。，) 2 1 ( 2 9 ) 根据上面介绍的布尔差分的性质可以知道被测线路上的s t u c k a t 0 故障或 s t u c k a t - 1 故障是否可以被测试。使用公式2 8 可以求出测试线路伍厶x 2 列在 s t u c k - a t - 0 故障类型的测试向量，将求得的测试向量代入到测试电路中，如果在输 出端发现输出值为0 的话，那么说明假设的测试线路中存在s t u c k - a t - 0 故障，反之 如果在输出端发现输出值为1 ，那么说明该测试通路中不存在s t u c k - a t 0 故障。使 用公式2 9 可以求出被测线路x x x 2 列中是否存在s t u c k a t 1 故障的测试向量， 同上面一样将求得的测试向量r ( a ，a 占，口j 代入到原电路中，如果在输出端中得到 的值为1 ，则说明该电路中存在着s t u c k 。a t 1 故障，反之，如果输出端中得到的值 为o ，则说明该电路中不存在s t u c k - a t 1 故障。 在这里假设砌出现故障，测试电路图如图2 3 ，使用布尔差分法求出该故障的 测试向量。我在这里将使用3 个步骤，来具体解释如何使用布尔差分法来求某个 故障的测试向量。 首先判断该故障在s t u c k a t 0 和s t u c k a t 1 中是否可测，将电路中的逻辑表达 式求出来，该表达式如下： z = 五，x 4 = x 2 + x 3 d z ( x ) f i 3 c 4 = ( o 五) o ( 1 一) = 0 0 五= 毛0 ( 2 1 0 ) f 2 1 1 ) 根据上面介绍的知识可以知道，当公式2 1 1 的值为1 的时候，说明该线路故 障存在s t u c k a t 0 或s t u c k a t 1 ，可以使用布尔差分公式求出测试向量。 其次求出x 4 在s t u c k a t 0 固定型故障的测试向量，在这里使用上面介绍的公式 2 8 来求出测试向量。根据公式2 8 可知： _ d z 妃( x ) i i t ( a l , a 2 a n ) = x 4 x 1 = ( 屯+ 恐) 五2 五恐+ 五恐= 1 ( 2 1 2 ) 根据公式2 1 2 可以知道，当x i = j 并且砣和幻中至少有一个为1 ，才能保证公 式2 1 2 的最终值为1 ，所以该测