数字电路测试向量自动生成技术

《数字电路测试向量自动生成技术》由会员分享，可在线阅读，更多相关《数字电路测试向量自动生成技术（12页珍藏版）》请在装配图网上搜索。

1、数字电路测试向量自动生成技术摘要数字电路测试向量自动生成一直是电子测试领域关注的焦点，是开发电路板模块测试程序的难点，也是困扰我军如何高效合理利用现有自动测试设备和开发测试程序组合软件构成具有实用性的故障诊断系统的关键点。测试向量生成最关键的技术是测试向量实用化算法的实现，通过对G-F二值算法的分析和研究，设计了一种新的方法和策略，采用正向敏化模式按有限回溯策略推导，凡在回溯次数内未能判明目标故障不可测的测试生成过程所产生的测试码都进行故障模拟。这种有限回溯策略加速测试生成，对提高系统效率起到了决定性的作用。在G-F算法确立正反向驱动经过各类功能块和反馈线的时帧变化的基础上，把推导组合电路目标

2、故障测试码的方法按迭代组合模型推广到同步时序电路，且用反向追踪中的时帧迭代实现迭代组合模型中的空间迭代。通过对同步时序电路的分析和研究，结合数字电路的特点，建立其电路模型和故障模型，生成了电路的器件库，并可对电路进行故障模拟，生成故障字典，生成的故障字典供测试系统使用。数字电路测试向量自动生成的实现主要以提高数字电路测试向量自动生成算法的通用性和效率为主，力争解决电路板的故障测试向量生成问题。关键词：测试向量集自动生成电路板，自动测试设备测试程序集故障模型故障字典 1绪论11研究目的1绪论本课题主要针对数字电路测试程序组合(XPS，Test Program Set)开发过程中，人工分析电路结构

3、，手工推导测试向量造成的开发难度大、周期长、质量无法评估的问题，开发出一套测试向量自动生成软件该软件能自动生成测试向量、故障字典等数据，提供给测试设备使用。12研究背景在一些测试过程中，出现了数字电路测试程序开发难度大、周期长、质量无法评估的问题，问题的根本在于需要人工进行分析电路，手工生成测试激励、响应数据，诊断信息完全根据测试开发人员的经验编制。在此背景下迫切需要研制一套数字电路自动测试向量生成软件来代替人工分析方法，自动生成测试所需的数据，降低测试程序开发难度，提高开发速度与质量，最大限度发挥测试系统的效能，最终提高军队的战斗保障力。13国内外研究现状现代战争发生突然，战场情况瞬息万变，

4、战争环境条件更加复杂严酷，机动性及快速反应能力要求高，这一切都更加迫切要求在装备发生故障时能迅速检测、隔离故障，及时修复，使战斗力保持和再生。同时，现代战争投入大量复杂的电子装备或含有电子系统的装备，而自动测试设备(ATE，Automatic Test Equipment)技术的高度发展，为满足迅速检测、隔离、修复，使战斗力很快再生提供了技术保证，现已成为世界各军事强国电子设备维修测试的主要方法和手段【。美国陆、海、空三军为适应现代战争快速保障的需要，分别组织实旅了“通用自动测试设备”计划，所有主要武器装备都装备了自动测试设备。我军也已开始研制和装备自动测试设备ATE用于武器装备的测试。其“硬

5、件”已达到和接近世界先进水平，但测试软件的使用仍受到一定限制，首先是对操作人员要求高，其次要求对装备设计的电路非常熟悉，同时，人工生成测试向量难度太大，造成开发一块电路板的TPS相当复杂，部队进行二次开发难度相当大，形成了所需的测试“软件”的“瓶颈”问题。如开发一块中等规模(几百个功能器件)电路板TPS为例，在技术资料齐全的情况下，专业技术人员约需2-3个月，成本约为23万元人民币。例如C一300地空导弹武器系统共有2700多种电路板，需投入的硬件费用约为1000万元左右，而测试软件开发周期，在1人l台ATE设备上要工作200多年，开发费用约为5400万元，开支费用惊人。无论是开发时间方面，还

6、是经费方面都严重制约了自动测试设备的广泛使用。但系统二次开发的能力不够，即TPS开发难。对使用者要求较高，开发效率急需大大提高。TPS开发难的问题，实质上是数字电路测试向量生成的问题如果不采用任何对输入激励的选择技术，则对有n个输入的数字系统，需加2n组不同的输入激励方可实现对系统的完全测试，但当n较大时，这是不现实的。如一个32位加法器，有65个输入，如果要加2舒组输入激励，即使是lns加一组，也要1000年，这是不可能实现的由此提出了一个如何加最少的输入激励也能达到同样的检测效果的问题，这也正是多年来人们利用各种算法来生成所需输入激励的问题。也是现有ATE，开发数字电路板TPS的难点12】

7、。自1966年罗思(Roth)发表的著名的D算法以来，数字电路测试理论得到了迅速发展研究者们提出了各种基于用门级描述数字电路ATPG的方法。特别是为了较好地解决时序电路的测试问题，相继提出了逻辑函数的多值模拟法，其中比较成功的有五值和九值布尔模拟。多值布尔模拟中所引入的新的布尔变量，主要是为了时序电路中状态变量的初值设置，以及在测试过程中某些元件的未知状态或随意状态的表达问题，目前常见的有基于九值逻辑运算的九值算法0-41。D算法从理论上解决了组合逻辑电路的测试生成问题，即任何一非冗余的组合逻辑电路中任何单故障都可用D算法来找到测试它的测试向量，但在实际应用中因其计算量十分浩大，对大型电路很难

8、实施。时序逻辑电路的测试主要有三个方面的难题：一是时序逻辑电路中存在反馈，给故障检测和诊断带来困难；二是时序逻辑电路中有存储元件，因此电路中存在着状态变量初态的随机性问题；三是时序逻辑电路中有时序元件，尤其是异步时序元件，对竞争现象是异常敏感，因此产生的测试序列，不仅在逻辑功能上要满足测试要求，而且要考虑到期竞争对测试电路的影响。无论组合逻辑电路，还是时序逻辑电路，虽然至今已有部分解决方案来测试它们，但工作量和测试费用都是很大的，尤其是现代装备的规模越来越大，测试的矛盾也日益尖锐。据美国有关公司的统计，当今一些PCB板的测试费用已占整个生产过程费用的500,6以上。我国学者提出的G-F二值算法

9、以简便的G-F值分开的二值运算实现了九值算法功能，使进行相容性运算时需要执行的运算规则由九值算法的45条减少为12条，大大提高了算法速度。G-F二值算法对于有n个输入的功能块，可以把功能块的pdc表压缩为n行，而且它只需存储相当于初始立方(pc,primitive cube)表的功能块的c立方表达式，即根据需要动态生成，因此，处理复杂功能块的大型电路比较方便。所以与D算法、PODEM和FAN算法、九值算法相比，G-F二值算法便于处理较复杂的功能块构成的电路，便于处理多故障和时序电路5-71。国际上如Teradyne、Synopsys等大公司研制出了一些用门级描述的数字电路测试向量自动生成(AT

10、PG，AutomaticTestPatternGeneration)商用软件，都是针对规模、复杂度不十分大的数字电路，也主要用于集成电路的设计中。据调研，国内外都没有成熟的ATPG商用软件。80年代后，人们对测试研究的战略思想发生了重要变化，最有代表性的观点是可测试性设计，认为边界扫描技术使门级的ATPG问题变得相对容易。但边界扫描等技术针对时序电路的测试有效，还需要额外增加20甚至300,6的硬件开销，增大了芯片的面积和电路的复杂性，而且测试时间变长，在一定程度上限制了这些技术的适用范围。但现有的装备中，由于种种原因，很多引进设备，没有提供维修的详细维修资料，有的甚至连电原理图都没有，大部分

11、的电路并不符合可测试性标准(1149，1)，国产电子装备出于成本和性能(主要是速度)的考虑，在批量不大的情况下，多数还是选择非扫描设计。所以，本项目不以可测试性设计为基础，而是从2提高数字电路ATPG算法的通用性和效率为主，力争解决电路板的故障测试向量生成闯题。测试向量自动生成一直是电子测试领域关注的焦点，是开发电子电路板模块测试程序的难点，也是困扰我军如何高效合理利用现有自动测试设备ATE和开发测试程序组合TPS软件构成具有实用性的故障诊断系统的关键点。测试诊断能否达到所期望的故障覆盖率和故障分辨率，主要取决于测试向量生成系统所提供的测试向量和故障字典的质量。人工开发澳I试向量的方法已无法满

12、足需要，如果不及早研究测试向量的自动生成，并在短时间内将其实用到已装备的ATE，势必会严重影响电子装备的作战能力及装备的技术保障。我军电子装备现有的大部份电路板由于没有有效的测试手段作保证，一方面大部分只能靠返回生产厂家(有的到国外生产厂)修理；另一方面是同一种电路板为防止短缺，占用大量资金，加大器材备件储备量。这种保障方式，战时既满足不了快速保障需要，技术保障工作还时时处于被动的局面，平时也容易使器材备件大量积压，造成了经费的紧张和资源的浪费。该课题从提高数字电路ATPG算法的通用性和效率为主，力争解决电路板的故障测试向量生成问题。14研究工作本课题主要功能块数字电路测试生成算法，建立数字电

13、路组合电路和同步时序电路的电路模型和故障模型，并对电路进行故障模拟，生成故障字典主要研究内容如下：1)完成数字电路测试向量生成软件的总体设计；2)完成测试向量生成算法理论实用化研究；3)开发出数字电路测试向量自动生成软件，具备自动生成测试码，故障模拟，故障覆盖率统计以及故障字典建立等功能；4)利用现有的ATE利用生成的数据文件对被测电路进行故障检测和诊断。42数字电路自动测试生成系统模型本测试生成系统的系统模型，是从被测对象的基本特征中抽象出来的，主要包括数字电路模型和故障模型。21数字电路模型211组合电路模型和时序电路模型1)两种模型的主要区别如果被测电路(CUT。Circuit Unde

14、r Test)中没有任何存储状态元件，也没有反馈回路，则可采用组合电路模型；反之，如果CUT中有任何一种存储状态元件，或者有反馈回路，则需要采用时序电路模型。由于组合电路的输出状态唯一地由当前的输入状态决定，因此，对组合电路的测试生成来说，在进行正反向驱动时，归根结底只考虑不同变量之间的逻辑关系，不需考虑它们之问的时间关系。对时序电路则不然，由于时序电路当前的输出状态不仅与当前时帧的输入有关，还与前一时帧电路的状态有关；前一时帧的状态又与前一帧的电路输入及再前一帧的电路状态有关，因此，在生成时序电路的测试时，既要考虑不同引线在同一时帧的逻辑关系，又要考虑不同引线变量在不同时帧的状态转换关系，也

15、要考摩同一引线变量在不同时帧的状态变化关系。总之，对时序电路生成测试时，既要考虑逻辑关系，又要考虑时间(帧)关系。因此比生成组合电路的测试要复杂得多。另一方面，由于生成组合电路测试时所遇到的各种问题，在求时序电路测试时也会出现，所以用于测试生成的时序电路模型实际上将包含组合电路模型。2)组合电路模型中的特殊情况由于电路类型和所用元件的不同，组合电路中也有许多需要专门处理的特殊情况：(1)三态门：它使一条引线具有0，l和高阻三个逻辑状态，如不进行特殊处理，只用传统的(ol，)三值逻辑是描述不了的。(2)双向端：一条引线既能作输出，又能作输入，当然，一次只起一种作用。但当它分别被用做输入和输出时，

16、对电路的逻辑关系是有不同影响的。有的双向端是对功能块而言的，有的是对整个CUT而言。(3)线逻辑：在电路的同一个或者不同的基本逻辑单元(门功能块，宏单元，组件)中，有两条以上的输出线直接相连，便形成线逻辑。对正逻辑为线与，对负逻辑为线或。这是一种不需要基本逻辑元件，仅通过连线直接实现的逻辑变换。(4)PLA：可编程逻辑阵列PLA虽然也是一种组合逻辑，但又不能象一般组合逻辑那样可化成门级电路来处理，因此它是一个不可分割的整体。此外，PLA中具有的触点消失和触点增生故障，也是一般组合电路中所没有的。(5)CMOS组合电路：由于CMOS电路中存在使组合门变成时序元件的固定开路故障SOP，因此，对CM

17、OS电路来说，完全的组合电路模型已经不存在了。3)时序电路模型的一般处理方法欲生成大型时序电路的测试序列，比较可行的方法是采用迭代组合模型。这是因为，第一，迭代组合模型既能如实地描述时序电路中信号线之间的逻辑关系，又能描述它们之间的时间关系；第二，该模型便于把组合电路中成熟的各种算法推广到时序电路中去。GF二值算法通过用时帧布尔表达式描述时序电路中的功能块，并对反馈线进行适当处理之后，可以把迭代组合模型中的空间迭代自动变化成测试生成过程中的时序迭代。这种变换不仅给测试生成带来方便，而且更符合迭代的实际情况网。22故障模型221门级单固定故障模型假设cur,-次只有一个门的一个输入或输出发生s一

18、口一o,一a一1故障，不考虑门内部晶体管的故障这是实际应用中所能考虑的最细的故障模型。分析表明，门级的一个单故障可以代表实现该门的晶体管电路中的多个故障。对于ECL和TTL电路来说，晶体管电路中的短路和开路故障，除少部分属于延迟故障外，一般都可6等效为门的输入，输出的s一口一osa一1故障。这种事实说明门级单固定故障模型具有很高的真实性。-由于在集成电路工艺中，门是最小的逻辑单元，因此，芯片级测试一般都要求考虑门级故障，采用门级故障模型19。222功能块级单固定故障模型假设CUT中一次只有一个功能块的一条输入或输出引腿发生jao,一al故障，不考虑功能块的内部故障。此故障模型有时也叫功能块引腿

19、故障模型，它适合于插件级测试。此模型的前提是组件内部的故障应在IC测试中解决，组件在装入插件之前已经过严格筛选。23本章小结本章主要主要阐述数字电路模型研究和故障模型。自动测试生成的系统模型，应从应用且标，即被测对象的基本特征中抽象出来。建立模型的基本出发点是：在满足对被测对象故障检测要求的前提下，应尽可能地使测试生成系统得到简化。3数字电路自动测试生成系统结构一个完整的自动测试生成系统，至少包括以下五个模块：诊断数据库、电路描述、预处理、测试生成、故障模拟。自动测试生成系统的系统流程图如图31所示31诊断数据库图31自动测试生成流程图311标准单元库标准单元库存放着构成cur的硬件最小单元和

20、软件定义的基本逻辑单元功能块的联系和对应信息。主要包括：11硬单元信息(1)硬单元名称、功能、引腿总数、输出数、输出引腿号、输入数、输入引腿号。(2)硬单元特殊引腿说明给出正、负脉冲端、电源端、接地端、三态输出端、三态控制端、双向端等特殊引腿的引腿号。(3)硬单元划分说明一个硬单元，例如一块组件，常由几个功能独立的逻辑块构成。2)功能块信息(1)功能块结构信息结构信息的图形表示功能块信息可以用图形表示，图形表示比较直观，于程序设计师查询.结构信息的文本描述把一个组件划分成几个功能块所得的功能块结构信息，可以用文本描述出来。(2)结构信息的功能信息功能信息主要是指描述功能块逻辑功能的布尔表达式。

21、在内存中用C立方形式存储。312 CUT信息库CUT信息库中存放着CUT的逻辑图、连线表和可供自动测试生成的测试生成、故障模拟直接访问的链表结构的拓扑电路。逻辑图一般mCAD系统的逻辑图输入程序提供，亦可从连线表自动生成。连线表可以在逻辑图输入过程中自动提取，也可以从CAD系统的布线结果加工得来，还可以由用户按照描述语言要求人工写成并输入机器。拓扑电路是自动测试生成的电路描述程序对Cul链线表编译的结果，要不要存入CUT信息库应根据具体情况决定。313库操作程序库操作程序完成库信息的自动产生和数据格式的自动转换。9数据库中有的信息时需要人工形成的，例如硬单元信息、功能块划分和结构信息等。但数多

22、信息是可以用库操作程序自动产生和转换的。32电路描述电路描述的任务是把用逻辑图或连线表或某种机器内部表格描述的被测电路的结构信息，转换成机器内部链表结构的拓扑电路，并对不同性质的引线变量给出不同的标记。电路描述程序既可以归到库操作程序中，也可以作为一个独立模块受自动测试生成系统调用。321面向结构的电路描述语言电路描述程序的输入信息是描述CUI逻辑结构的连线表。如果输入信息是CUT的逻辑图，则电路描述程序要从逻辑图中自动提取连线表；如果CUT的结构信息来flCAD系统的自动布线结果，则电路描述要把布线用的工程化信息加工成逻辑结构信息，这些信息供测试生成使用【lIl。一般采用面向结构的电路描述语

23、言描述CUT的逻辑结构信息，这种语言用结构描述语言(sDL，Structural Descdption LaIlg蚰ge)就够了。从满足需要考虑，电路描述语言至少要包括以下几方面的语言：11描述CUT物理信息的语句(1)电路名语句；(2)硬单元名称与物理位置对照语句21描述CUT的IO信息的语句(1)初级输入语句；(2)初级输出语句；(3)脉冲IO语句；(4)接地IO语句；(5)电源IO语句。3)描述CUr内部特殊信号线语句(1)反馈线语句；(2)特殊测试点语句；(3)固定电平线语句；“)线逻辑语句；(5)三态线语句；(6)双向线语句。4)描述CUT基本硬单元互连关系的连线表语句322电路描述

24、语言编译器电路描述语言编译器一般采用多遍扫描方式。第一遍专门进行语法规则检查。对于非自动产生的连线表，这一遍至关重要。第二遍按随机顺序把CUT中各个硬单元连接起来，初步形成CUT的链表结构。第三遍扫描通过处理反馈线给功能块定级，按自动测试生成系统要求标志某些引线变量的特殊属性等操作，最后形成以功能块为基本逻辑单元的、按逻辑级从低到高顺序排列的链表结构的拓扑电路协141。323 CUT的链表拓扑结构CUT的链表结构要设计得紧凑，使用方便，既要省内存，又要查询速度快。下面给出的TB，T取的链表结构经实际证明效果较好，可以作为一种参考结构。1)TB，TB是CUT的总信息说明和链表目录。具体包括以下信

25、息：(1)CUT名称；(2)TB：记录名称及记录数；(3)T臣记录名称及记录数；(4)TB4记录名称及记录数；(5)TB，记录名称及记录输；(6)CUT总信息记录。包括PI总数、PO总数、反馈线总数、功能块总数、引线变量总、最高逻辑级数、最高时序级数2) B2TB，是CUT的引线变量表。自动测试生成给引线编号的规则是：对每个功能块的每条输出线编一个号，此号称为引线号或引线变量号。输入线不另编号，与其先行输出线共用一个变量号。PI线按虚拟功能的输出对待。虚拟功能块是指虚设的、输出个数为l、输入个数为0的功能块，在TB2中一个引线变量占一个记录，记录号与变量号相同。一个记录包括以下信息：(1)引线

26、所属硬单元的位置及引线的引腿号；(2)引线在功能块中的输出端号；(3)引线扇出个数；(4)引线所属功能块的说明信息在TB：中的记录号；(5)引线的后继说明信息在TB。的记录号；(6)引线特殊属性标志位。3)TB3TB，是CuT的功能块说明信息表。每个功能块在TB，中占一个记录，记录号即是功能块在CUT中的序号。一个记录包括以下信息；(1)功能块类型编码；(2)功能块输出个数和输入个数；(3)功能块逻辑级别；(4)功能块的输出说明：按输出端号从小到大顺序，逐个说明功能块每个输出的引线变量号，并给出每个输出的后继信息在TB4的记录号；(5)功能块输入说明：按输入端号从小到大顺序，逐个说明功能块每个

27、输入的引腿号及对应的引线变量号。在功能块输出，输入说明栏目中，每个输出，输入后面都附加一个标志域。标志域中动态记录树标记和引线跳变标记信息。输入标志域中还给出该输入是否反馈线的标记。4)TB,TB4是CUT的后继信息说明表。一个引线变量的后继说明占一个记录。一个记3) 录包含下列信息：(1)引线毛的后继功能块在TB3中的记录号；(2)后继功能块与鼍相连的输入端号。鼍有几个后继，在TB4中便有几个记录。最后给出记录结束标志。5)TB5TB。是CUT的初级输出列表。表中把可做为测试回收点的特殊测试点也做为PO给出。每+PO在TB5中占一个记录。一个记录包括下列内容：(1)初级输出的引线变量号；(2

28、)初级输出的插脚名或管腿号；(3)初级输出的特殊属性标志，是否脉冲输出和特殊测试点等。33预处理随着自动测试生成系统功能的日趋完善，处理能力的不断提高，预处理技术的地位显得越来越重要。它不仅可为加速测试生成提供启发引导信息，而且，许多在测试生成过程中要反复用到的信息，在预处理阶段一次性生成，有利于提高自动测试生成的执行效率。331生成CUT的目标故障表之所以把生成CUT的目标故障表归到预处理技术中，是因为它既涉及把自动测试生成采用的故障模型具体化的问题，又涉及到根据故障等价原理对模型故障进行等价归并得技术。既要达到故障模型要求，又要尽量精简目标故障数，以减小自动测试生成的计算量是本程序的目标。

29、1)模拟故障的等价归并(1)基本门的等价故障与(与非)门用输出的0(1)故障代替所有输入的0故障；或(或非)门用输出的1(O)故障代替所有输入的1故障非门和驱动门只需设输出的墨一a一0肛一口一l故障。(2) 电路中的等价故障如图32所示。功能块BI的输出与B2的输入的0，1故障是不可区分的，只需设B1的输出线葺j一口一0，Jal二个故障即可【1卦。 图32等价故障示意图1如图33所示，B1的输出扇出到B2和B3，这3条线要设6个模型故障。但由于这34k线与地短路的故障是不可区分的，只需设1个即可，因此共设4个故障就够了。具体来说，功能块B1的输出属于扇出源，要设Sa一0，Ja一1两个故障，B：

30、和B，的输入属于扇出分线，只需各设一个开路故障，对TTL电路设ja一1，对ECL电路设$-a-0故障。 图33等价故障示意图2统计结果表明，进行上述等价归并之后，CUT中的目标故障大约只有模型故障数的三分之二。当然，还可以根据电路的逻辑关系做进一步的精简，但要从性能价格比的角度考虑是否合算。2)目标故障的表示方法目标故障在内存中有两种表示方法：位表示法和字符表示法(1)位表示法这种表示法是：一个功能块的故障表在内存中占一个单元。功能块的输出Os口一1及输入故障分别用该单元不同的位表示，该位为1，表示该故障存在，为0表示该故障不存在这种表示法便于自动测试生成系统从目标故障表中取故障和根据故障模拟

31、结果对目标故障表进行故障覆盖，即把已被检测的故障从目标故障表中删除。(2)字符表示法与位表示法相对应的还有一种用字符表示法存储的目标故障表，它给出了每个目标故障在CUT中的物理位置。具体格式是：硬单元坐标，引腿号故障值。332从简到繁对CUT的测试树头排序确定性测试生成的一般做法是按测试树头(即测试回收点，它包括PO和特殊回收点)把CUT划分成若干测试区，按从简到繁原则逐个测试区地生成测试码、覆盖故障。对各测试区重迭部分的故障不搞重复覆盖，这样可以较大地降低自动测试生成的计算复杂性。这里的关键是对测试区从简到繁排序，也就是对测试树头排序。实践表明，如果把树头顺序搞反了，则测试生成时间将成倍甚至

32、按数量级增长f”。333生成树标记及各引线的树头级距上h1)树标记得作用用于自动测试生成对大型CUT的处理一般都是按树或者说按测试区进行的，因此，首先对当前测试树所含的功能块和引线变量给出树标记，将后续程序带来许多方便。(1)生成树故障表树故障表是当前树的测试生成和故障模拟所用的目标故障表它是从CUT的总目标故障表中，把那些有树标记得功能块的输出和输入引线所对应的故障位分离出来构成的。(2)生成模拟功能块表把有树标记得功能块按级别从低到高排列或者按故障模拟自行规定的顺序排列起来，便形成模拟功能块表。故障模拟只需对表内功能块依次驱动计算，这样可以避免对树外进行的无效计算。(3)打跳变标记即给出从

33、故障线到当前树头所经过的所有引线可能发生的跳变标记。有了树标记之后，只需分析有树标记得引线可能发生的跳变。(4)确定故障敏化路径测试生成需要确定敏化路径，DRFM测度计算中需要确定从故障线到树头的所有敏化路径上的必要敏化条件，上述操作都是限制在当前树内进行的。有了树标记，可以防止敏化路径向树外延伸。(5)识别会聚型扇出点电路中的扇出点有会聚型和发散型两类，许多测试生成算法和可测性分析方法都考虑了会聚型扇出点的影响。要区分这两类扇出需要进行复杂的搜索判断。但是，有了树标记就方便得多了。一个扇出源只要有两个以上扇出分支有树标记，则一定是会聚型扇出源，否则就是发散型扇出源【1s-20l。2)生成树标

34、记的方法给出树标记的基本做法是反复查询TB表和DB中的功能块连通矩阵。先从树头开始，由TB，中的树头变量号找到TB：相应的记录，查出树头所属功能块在TB，中的记录号，从TB3中查得树头功能块的类型编码，由类型编码可至IJDB中找到有关的连通矩阵，从中可确定与树头有逻辑连通关系的功能块的所有的输入，再回到TB3中确定这些输入的变量号，然后根据每个变量号重复上述1B，一TB3-DBTB，的查询过程，一直NPI为止对上述过程中查到的TB，中的功能块及其有关输出、输入线都在TB，的标志域中给出树标记。3)引线的树头级距k(1)引线的树头级距的定义电路中引线墨按信号传播方向到达树头Y所经功能块的最少级数

35、，称为薯的树头级距，记为k“)(2)引线的树头级距的计算法则引线的树头级距的初值是：当置是故障线，其值为0；否则其值为一。如果功能块的输出为x，与x逻辑相关的输入是，屯，则k(力=Inink)+1(i=1，2，哟如果毛，吃，是x小的扇出分线，则k(功=minLh(x，)+10=1,2，”)(3)引线的树头级距的用途引线的树头级距是选择最短敏化路径的极好的引导函数，它具有计算简便、引导准确的特点。用CUT的链表TB，TB；中的现成信息，例如功能块级别进行引导行不行呢?答案是否定的。因为即使在组合电路中，级别高的功能块也不一定就离PO近，时序电路就更不用说了。对于反馈线较多的时序电路，特别是闭环电

36、路，选择敏化路径的矛盾十分突出，而用三。引导，可以保证每次都能选择较短的敏化路径。4)生成引线跳变标记和各引线的故障级距三。(1)何谓引线跳变标记引线苫，的跳变标记指的是目标故障确定之后，分析如果要从x，传播故障信号的话，z，可能发生的跳变。跳变标记分0-1，l一0，0-11-0(双跳变)和0-0(无跳变)四类，在TB，的标志域中分别用01lO，1001，1111和0000表示。(2)引线跳变标记得作用从测试生成角度看，在一个电路中设定了目标故障鼍sao之后，它中间的引线可以分为两类：一类在逻辑上受薯的影响，一类不受葺的影响。前者称为故障相关线，后者称为故障无关线不管采用那种算法求测试，故障无

37、关线都只需要(o，1，)三个值即可描述。因此，把故障无关线区分出来有利于简化求测试的运算过程。另一方面，对故障相关线，通过跳变分析，排除不可能产生的故障信号，也可以简化相容性操作。(3)引线跳变标记得生成方法方法流程a)从CUT的目标故障标中取一位；b)把此位翻译成拓扑电路的故障，对功能块输出端故障，给出故障引线变量号和故障值；对功能块输入故障，给出故障功能块在TB3的记录号及故障线的输入端号；c)查故障功能块(对输入故障)的连通矩阵，确定与故障输入端有逻辑连通关系的输出端的端号及其跳变；d)从TB，中确定上述输出端的引线变量号及其后继TB。的记录号；e)由TB。中查后继功能块TB，记录号及相

38、应的输入端号；0逐个查上述后继功能块的连通矩阵，由输入跳变确定有逻辑连通关系的输出端的跳变：g)重复d)f)，直到PO为止。从输入跳变确定输出跳变的算法设输入跳变A=100I0110，连通矩阵中描述输出与输入逻辑连通关系的两位B=(hi,b2)，其中6l，b2(o，1)，把占扩展成逻辑字C和D，其中C=(blblblbl),D=(b2626262)则描述输出跳变的逻辑运算都是按位操作。(4)引线的故障级距工。引线的故障级距的定义电路中引线五按信号传播的逆方向到达故障线，所经功能块的最少级数，称为薯的故障级距，记为k(薯)。引线的故障级距的计算法则a)引线的故障级距的初值是：当薯是故障线，其值为

39、0；否则其值为oo。b)如果功能块的输出为x，与x逻辑相关的输入是毛，X2，则k(功=mint_，(五)+l O=l，2，按上述法则完成计算之后，凡与故障线逻辑无关的引线的k=一，其他线k是一个有限的正整数。引线的故障级距的用途a)当采用从PO至t故障线，或者说从上到下的反向故障敏化策略时，工。可做为建立最短敏化路径的引导函数。b)当采用GF二值公式，用纵向回推法求测试时，通过工。引导，可以保证尽快回推到故障线。做法也是从树头的一种DRFM测度较低的跳变开始，每次都从(3-F二值公式的积之和展开式中优先选取k较小的输入变量的跳变向下展开，直到故障线为止c)上。可作为从目标故障选择距离最近的树头

40、的引导函数。测试生成的实践表明，一个目标故障，总是在离它较近的PO上被检测的可能性较大当已知电路中各引线的k之后，可把所有的PO按三。从4,N大排序，以保证每次总是向离得较近的PO驱动目标故障。这种从故障定树头的控制方法与传统的按树头划分测试区，或者叫做重树头定故障的方法比较起来，对于反馈线很多的闭环电路，具有明显得优越性，可使自动测试生成获得较多的时间效益。(5)计算D】iFM测度，识别不可测故障可测性分析方法给出的电路引线的测度值，是测试生成正、反向驱动过程中重要的引导函数。静态测度分析，例如SCOAP方法，对每个CUT只需在预处理期间计算一次电路引线的可控制性和可观察性值，计算过程相对来

41、说是很简单的。但它对测试生成的引导有时很不合理的。动态测度分析，例如DRFM方法，由于把测度值看成是目标故障及其必要检测条件的动态函数，因此，要对每个目标故障计算一次电路引线的动态约束四值测度值。此项计算也纳入预处理程序。DRFM的计算复杂度比SCOAP增大了，但它的精确性有了很大提高。它能对测试生成的搜索树进行有效修剪，使自动测试生成对难测故障的回溯尽可能少；并能根据每个故障的测度值得大小，识别包括冗余故障在内的不可测故障。从而有效地避免CPU时间的无谓消耗t22-231。(6)功能块表达式的预代真测试生成的正反向驱动过程，一般是按功能块逐个进行的。因此无论是求敏化条件还是某个变量值得回推条

42、件，首先要处理的都是功能块的ca-7_方表达式。由于每个功能块在电路中都与其他功能块有一定的结构上的连接关系和功能上的逻辑关系。因此，要解决正反向驱动过程中一致性问题，就必须用统一的电路引线变量号描述各个功能块的表达式。这就要求把用各自的输入，输出端号表示的功能块的c立方表达式转换成拓扑电路内部引线变量号表示的形式。一般把表达式数据结构的这种转换叫做代真。34测试生成测试生成是自动测试生成的核心部分，是决定自动测试生成效率的主要因素，从某种意义上来说，它是自动测试生成的关键所在。前面介绍的数据库、电路描述和预处理三个模块中提供的各种信息，绝大部分是为提高测试生成的效率服务的。341 G-F二值

43、算法该算法的主要特点是：采用布尔差分的数据描述形式，D算法的立方体运算方式，并用G-F值分开的二值逻辑运算实现了九值逻辑运算的功能，从而简化了算法的程序实现，提高了算法效率。该算法的另一个特点是首次实现了门级和功能块级电路、组合电路和时序电路测试生成的统一处理。1)从五值逻辑到九值逻辑(1)五值逻辑与信号线的逻辑状态对于正常电路，用O，1，)三个值描述信号线在某时刻的逻辑状态是完整的。其中(0，1)表示信号线的不定状态。当电路中产生故障时，为了描述故障对电路信号线状态的影响，三值逻辑己不够用，所以D算法引进了0,1，D，D)五个值，称为五值逻辑。(2)五值逻辑与故障敏化条件引进九值逻辑可以弥补五值逻辑在描述引线逻辑状态、处理故障敏化条件方面的缺陷由于九值逻辑能准确描述信号线逻辑状态，包括故障对逻辑状态的影响，能把一个故障的多个充分敏化条件综合成一个充分必要的敏化条件，因此能避免D算法驱赶中所做的许多重复工作，提高算法效率。以九值逻辑运算为基础的D算法称为九值D算法Dlr11241。2)九值逻辑的G-F-值表示法(1)数字电路的G-F-值描述