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

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

———————————————————————————————— 作者：
———————————————————————————————— 日期：

14

个人收集整理 勿做商业用途
数字电路测试向量自动生成技术
摘要
数字电路测试向量自动生成一直是电子测试领域关注的焦点，是开发电路板／
模块测试程序的难点，也是困扰我军如何高效合理利用现有自动测试设备和开发测
试程序组合软件构成具有实用性的故障诊断系统的关键点。
测试向量生成最关键的技术是测试向量实用化算法的实现,通过对G-F二值算
法的分析和研究，设计了一种新的方法和策略，采用正向敏化模式按有限回溯策略
推导，凡在回溯次数内未能判明目标故障不可测的测试生成过程所产生的测试码都
进行故障模拟.这种有限回溯策略加速测试生成，对提高系统效率起到了决定性的
作用。在G-F算法确立正反向驱动经过各类功能块和反馈线的时帧变化的基础上，
把推导组合电路目标故障测试码的方法按迭代组合模型推广到同步时序电路，且用
反向追踪中的时帧迭代实现迭代组合模型中的空间迭代。
通过对同步时序电路的分析和研究，结合数字电路的特点,建立其电路模型和
故障模型，生成了电路的器件库，并可对电路进行故障模拟，生成故障字典,生成
的故障字典供测试系统使用.数字电路测试向量自动生成的实现主要以提高数字电
路测试向量自动生成算法的通用性和效率为主，力争解决电路板的故障测试向量生
成问题。
关键词：测试向量集自动生成电路板，自动测试设备测试程序集
故障模型故障字典

1绪论
1．1研究目的
1绪论
本课题主要针对数字电路测试程序组合（XPS，Test Program Set)开发过程中，人工
分析电路结构，手工推导测试向量造成的开发难度大、周期长、质量无法评估的问
题，开发出一套测试向量自动生成软件．该软件能自动生成测试向量、故障字典等
数据，提供给测试设备使用。
1．2研究背景
在一些测试过程中，出现了数字电路测试程序开发难度大、周期长、质量无法
评估的问题,问题的根本在于需要人工进行分析电路，手工生成测试激励、响应数
据，诊断信息完全根据测试开发人员的经验编制.在此背景下迫切需要研制一套数
字电路自动测试向量生成软件来代替人工分析方法，自动生成测试所需的数据,降
低测试程序开发难度，提高开发速度与质量，最大限度发挥测试系统的效能，最终
提高军队的战斗保障力。
1．3国内外研究现状
现代战争发生突然，战场情况瞬息万变,战争环境条件更加复杂严酷，机动性
及快速反应能力要求高，这一切都更加迫切要求在装备发生故障时能迅速检测、隔
离故障，及时修复，使战斗力保持和再生。同时，现代战争投入大量复杂的电子装
备或含有电子系统的装备，而自动测试设备(ATE，Automatic Test Equipment）技术的
高度发展，为满足迅速检测、隔离、修复，使战斗力很快再生提供了技术保证，现
已成为世界各军事强国电子设备维修测试的主要方法和手段【¨。
美国陆、海、空三军为适应现代战争快速保障的需要,分别组织实旅了“通用
自动测试设备”计划,所有主要武器装备都装备了自动测试设备.我军也已开始研
制和装备自动测试设备ATE用于武器装备的测试。其“硬件”已达到和接近世界先
进水平,但测试软件的使用仍受到一定限制,首先是对操作人员要求高，其次要求
对装备设计的电路非常熟悉,同时,人工生成测试向量难度太大，造成开发一块电
路板的TPS相当复杂，部队进行二次开发难度相当大，形成了所需的测试“软件”
的“瓶颈”问题.如开发一块中等规模（几百个功能器件)电路板TPS为例，在技
术资料齐全的情况下，专业技术人员约需2——3个月，成本约为2—3万元人民币。
例如C一300地空导弹武器系统共有2700多种电路板，需投入的硬件费用约为1000
万元左右，而测试软件开发周期，在1人l台ATE设备上要工作200多年，开发费
用约为5400万元，开支费用惊人.无论是开发时间方面，还是经费方面都严重制约
了自动测试设备的广泛使用。但系统二次开发的能力不够，即TPS开发难。对使用
者要求较高，开发效率急需大大提高。
TPS开发难的问题，实质上是数字电路测试向量生成的问题．如果不采用任何
对输入激励的选择技术，则对有n个输入的数字系统,需加2n组不同的输入激励方
可实现对系统的完全测试，但当n较大时,这是不现实的.如一个32位加法器，有
65个输入,如果要加2舒组输入激励，即使是lns加一组，也要1000年，这是不可
能实现的．由此提出了一个如何加最少的输入激励也能达到同样的检测效果的问题，
这也正是多年来人们利用各种算法来生成所需输入激励的问题。也是现有ATE，开
发数字电路板TPS的难点12】。
自1966年罗思（Roth）发表的著名的D算法以来,数字电路测试理论得到了迅
速发展．研究者们提出了各种基于用门级描述数字电路ATPG的方法.特别是为了
较好地解决时序电路的测试问题，相继提出了逻辑函数的多值模拟法,其中比较成
功的有五值和九值布尔模拟。多值布尔模拟中所引入的新的布尔变量，主要是为了
时序电路中状态变量的初值设置，以及在测试过程中某些元件的未知状态或随意状
态的表达问题，目前常见的有基于九值逻辑运算的九值算法0-41。
D算法从理论上解决了组合逻辑电路的测试生成问题,即任何一非冗余的组合
逻辑电路中任何单故障都可用D算法来找到测试它的测试向量，但在实际应用中因
其计算量十分浩大,对大型电路很难实施。时序逻辑电路的测试主要有三个方面的
难题:一是时序逻辑电路中存在反馈，给故障检测和诊断带来困难;二是时序逻辑
电路中有存储元件，因此电路中存在着状态变量初态的随机性问题；三是时序逻辑
电路中有时序元件，尤其是异步时序元件,对竞争现象是异常敏感，因此产生的测
试序列,不仅在逻辑功能上要满足测试要求，而且要考虑到期竞争对测试电路的影
响。无论组合逻辑电路，还是时序逻辑电路，虽然至今已有部分解决方案来测试它
们，但工作量和测试费用都是很大的，尤其是现代装备的规模越来越大，测试的矛
盾也日益尖锐.据美国有关公司的统计,当今一些PCB板的测试费用已占整个生产
过程费用的500，6以上。
我国学者提出的G-F二值算法以简便的G-F值分开的二值运算实现了九值算法
功能，使进行相容性运算时需要执行的运算规则由九值算法的45条减少为12条，
大大提高了算法速度.G-F二值算法对于有n个输入的功能块，可以把功能块的pdc
表压缩为n行，而且它只需存储相当于初始立方（pc,primitive cube)表的功能块的c立
方表达式，即根据需要动态生成,因此，处理复杂功能块的大型电路比较方便。所
以与D算法、PODEM和FAN算法、九值算法相比,G-F二值算法便于处理较复杂
的功能块构成的电路,便于处理多故障和时序电路[5—71。
国际上如Teradyne、Synopsys等大公司研制出了一些用门级描述的数字电路测
试向量自动生成（ATPG，AutomaticTestPatternGeneration)商用软件,都是针对规模、
复杂度不十分大的数字电路，也主要用于集成电路的设计中。据调研,国内外都没
有成熟的ATPG商用软件。
80年代后，人们对测试研究的战略思想发生了重要变化，最有代表性的观点是
可测试性设计,认为边界扫描技术使门级的ATPG问题变得相对容易.但边界扫描
等技术针对时序电路的测试有效,还需要额外增加20%甚至300,6的硬件开销，增大
了芯片的面积和电路的复杂性,而且测试时间变长，在一定程度上限制了这些技术
的适用范围.但现有的装备中，由于种种原因，很多引进设备,没有提供维修的详
细维修资料，有的甚至连电原理图都没有，大部分的电路并不符合可测试性标准
（1149，1），国产电子装备出于成本和性能(主要是速度)的考虑,在批量不大的情
况下,多数还是选择非扫描设计。所以，本项目不以可测试性设计为基础，而是从2
提高数字电路ATPG算法的通用性和效率为主，力争解决电路板的故障测试向量生
成闯题。
测试向量自动生成一直是电子测试领域关注的焦点，是开发电子电路板／模块
测试程序的难点,也是困扰我军如何高效合理利用现有自动测试设备ATE和开发测
试程序组合TPS软件构成具有实用性的故障诊断系统的关键点。测试诊断能否达到
所期望的故障覆盖率和故障分辨率,主要取决于测试向量生成系统所提供的测试向
量和故障字典的质量。人工开发澳I试向量的方法已无法满足需要，如果不及早研究
测试向量的自动生成，并在短时间内将其实用到已装备的ATE，势必会严重影响电
子装备的作战能力及装备的技术保障.
我军电子装备现有的大部份电路板由于没有有效的测试手段作保证，一方面大部分只能靠返回生产厂家（有的到国外生产厂）修理;另一方面是同一种电路板为
防止短缺，占用大量资金，加大器材备件储备量。这种保障方式,战时既满足不了
快速保障需要，技术保障工作还时时处于被动的局面，平时也容易使器材备件大量
积压,造成了经费的紧张和资源的浪费。
该课题从提高数字电路ATPG算法的通用性和效率为主,力争解决电路板的故
障测试向量生成问题。
1．4研究工作
本课题主要功能块数字电路测试生成算法，建立数字电路组合电路和同步时序
电路的电路模型和故障模型,并对电路进行故障模拟，生成故障字典．主要研究内
容如下：
1）完成数字电路测试向量生成软件的总体设计;
2）完成测试向量生成算法理论实用化研究；
3）开发出数字电路测试向量自动生成软件，具备自动生成测试码，故障模拟,
故障覆盖率统计以及故障字典建立等功能；
4)利用现有的ATE利用生成的数据文件对被测电路进行故障检测和诊断.
42数字电路自动测试生成系统模型
本测试生成系统的系统模型，是从被测对象的基本特征中抽象出来的，主要包
括数字电路模型和故障模型。
2．1数字电路模型
2．1．1组合电路模型和时序电路模型
1)两种模型的主要区别
如果被测电路（CUT.Circuit Under Test）中没有任何存储状态元件，也没有反馈回
路,则可采用组合电路模型;反之，如果CUT中有任何一种存储状态元件，或者有
反馈回路，则需要采用时序电路模型。
由于组合电路的输出状态唯一地由当前的输入状态决定,因此，对组合电路的
测试生成来说，在进行正反向驱动时，归根结底只考虑不同变量之间的逻辑关系，
不需考虑它们之问的时间关系。对时序电路则不然，由于时序电路当前的输出状态
不仅与当前时帧的输入有关，还与前一时帧电路的状态有关；前一时帧的状态又与
前一帧的电路输入及再前一帧的电路状态有关，因此，在生成时序电路的测试时，
既要考虑不同引线在同一时帧的逻辑关系，又要考虑不同引线变量在不同时帧的状
态转换关系，也要考摩同一引线变量在不同时帧的状态变化关系。总之，对时序电
路生成测试时,既要考虑逻辑关系,又要考虑时间(帧）关系。因此比生成组合电
路的测试要复杂得多。另一方面，由于生成组合电路测试时所遇到的各种问题，在
求时序电路测试时也会出现，所以用于测试生成的时序电路模型实际上将包含组合
电路模型。
2)组合电路模型中的特殊情况
由于电路类型和所用元件的不同,组合电路中也有许多需要专门处理的特殊情
况：
(1)三态门：它使一条引线具有0,l和高阻三个逻辑状态,如不进行特殊处理，只用传统的(o’l，×)三值逻辑是描述不了的。
(2）双向端：一条引线既能作输出，又能作输入，当然,一次只起一种作用。但
当它分别被用做输入和输出时,对电路的逻辑关系是有不同影响的.有的双向端是
对功能块而言的，有的是对整个CUT而言。
(3）线逻辑：在电路的同一个或者不同的基本逻辑单元(门／功能块，宏单元，组件）
中，有两条以上的输出线直接相连，便形成线逻辑.对正逻辑为线与,对负逻辑为
线或。这是一种不需要基本逻辑元件，仅通过连线直接实现的逻辑变换。
(4)PLA：可编程逻辑阵列PLA虽然也是一种组合逻辑,但又不能象一般组合逻辑
那样可化成门级电路来处理，因此它是一个不可分割的整体。此外，PLA中具有的触点消失和触点增生故障，也是一般组合电路中所没有的。
（5）CMOS组合电路：由于CMOS电路中存在使组合门变成时序元件的固定开路
故障S．OP,因此,对CMOS电路来说，完全的组合电路模型已经不存在了。
3)时序电路模型的一般处理方法
欲生成大型时序电路的测试序列,比较可行的方法是采用迭代组合模型。这是
因为,第一，迭代组合模型既能如实地描述时序电路中信号线之间的逻辑关系，又
能描述它们之间的时间关系；第二,该模型便于把组合电路中成熟的各种算法推广
到时序电路中去。G—F二值算法通过用时帧布尔表达式描述时序电路中的功能块，
并对反馈线进行适当处理之后，可以把迭代组合模型中的空间迭代自动变化成测试生成过程中的时序迭代。这种变换不仅给测试生成带来方便，而且更符合迭代的实
际情况网。
2．2故障模型
2．2．1门级单固定故障模型
假设cur,—次只有一个门的一个输入或输出发生s一口一o／,一a一1故障,不考
虑门内部晶体管的故障．这是实际应用中所能考虑的最细的故障模型.分析表明，
门级的一个单故障可以代表实现该门的晶体管电路中的多个故障。对于ECL和TTL
电路来说，晶体管电路中的短路和开路故障，除少部分属于延迟故障外,一般都可
6等效为门的输入,输出的s一口一o／s-a一1故障。这种事实说明门级单固定故障模型具
有很高的真实性。—由于在集成电路工艺中,门是最小的逻辑单元，因此，芯片级测
试一般都要求考虑门级故障，采用门级故障模型19]。
2．2．2功能块级单固定故障模型
假设CUT中一次只有一个功能块的一条输入或输出引腿发生j-a-o／,一a—l故
障，不考虑功能块的内部故障。此故障模型有时也叫功能块引腿故障模型,它适合
于插件级测试。此模型的前提是组件内部的故障应在IC测试中解决，组件在装入插
件之前已经过严格筛选。
2．3本章小结
本章主要主要阐述数字电路模型研究和故障模型。自动测试生成的系统模型，
应从应用且标，即被测对象的基本特征中抽象出来。建立模型的基本出发点是:在
满足对被测对象故障检测要求的前提下，应尽可能地使测试生成系统得到简化。
3数字电路自动测试生成系统结构
一个完整的自动测试生成系统，至少包括以下五个模块：诊断数据库、电路描述、
预处理、测试生成、故障模拟。自动测试生成系统的系统流程图如图3．1所示·

3．1诊断数据库
图3．1自动测试生成流程图
3．1．1标准单元库
标准单元库存放着构成cur的硬件最小单元和软件定义的基本逻辑单元～功能块的联系和对应信息。主要包括：
11硬单元信息
（1）硬单元名称、功能、引腿总数、输出数、输出引腿号、输入数、输入引腿号。
（2)硬单元特殊引腿说明
给出正、负脉冲端、电源端、接地端、三态输出端、三态控制端、双向端等特
殊引腿的引腿号.
(3）硬单元划分说明
一个硬单元，例如一块组件，常由几个功能独立的逻辑块构成。
2）功能块信息
(1)功能块结构信息
①结构信息的图形表示
功能块信息可以用图形表示，图形表示比较直观，于程序设计师查询.
②结构信息的文本描述
把一个组件划分成几个功能块所得的功能块结构信息，可以用文本描述出来。
(2）结构信息的功能信息
功能信息主要是指描述功能块逻辑功能的布尔表达式。在内存中用C立方形式存
储。
3．1．2 CUT信息库
CUT信息库中存放着CUT的逻辑图、连线表和可供自动测试生成的测试生成、
故障模拟直接访问的链表结构的拓扑电路。
逻辑图一般mCAD系统的逻辑图输入程序提供，亦可从连线表自动生成。连线
表可以在逻辑图输入过程中自动提取，也可以从CAD系统的布线结果加工得来，还
可以由用户按照描述语言要求人工写成并输入机器。拓扑电路是自动测试生成的电
路描述程序对Cul链线表编译的结果，要不要存入CUT信息库应根据具体情况决定.
3．1．3库操作程序
库操作程序完成库信息的自动产生和数据格式的自动转换.
9数据库中有的信息时需要人工形成的，例如硬单元信息、功能块划分和结构信
息等。但数多信息是可以用库操作程序自动产生和转换的。
3．2电路描述
电路描述的任务是把用逻辑图或连线表或某种机器内部表格描述的被测电路的
结构信息，转换成机器内部链表结构的拓扑电路，并对不同性质的引线变量给出不
同的标记.电路描述程序既可以归到库操作程序中，也可以作为一个独立模块受自
动测试生成系统调用.
3．2．1面向结构的电路描述语言
电路描述程序的输入信息是描述CUI逻辑结构的连线表。如果输入信息是CUT的逻
辑图，则电路描述程序要从逻辑图中自动提取连线表；如果CUT的结构信息来flCAD
系统的自动布线结果，则电路描述要把布线用的工程化信息加工成逻辑结构信息，这些
信息供测试生成使用【lIl。
一般采用面向结构的电路描述语言描述CUT的逻辑结构信息,这种语言用结构
描述语言(sDL,Structural Descdption LaIlg蚰ge）就够了。从满足需要考虑,电路描述
语言至少要包括以下几方面的语言：
11描述CUT物理信息的语句
（1）电路名语句;
(2)硬单元名称与物理位置对照语句．
21描述CUT的I／O信息的语句
(1)初级输入语句;
(2)初级输出语句；
(3）脉冲I／O语句；
(4）接地I／O语句；
(5）电源I／O语句。
3）描述CUr内部特殊信号线语句
（1）反馈线语句；
（2)特殊测试点语句；
(3）固定电平线语句；
“）线逻辑语句；
（5)三态线语句;
(6）双向线语句。
4)描述CUT基本硬单元互连关系的连线表语句
3．2．2电路描述语言编译器
电路描述语言编译器一般采用多遍扫描方式。第一遍专门进行语法规则检查。
对于非自动产生的连线表，这一遍至关重要。第二遍按随机顺序把CUT中各个硬单
元连接起来,初步形成CUT的链表结构。第三遍扫描通过处理反馈线给功能块定级，
按自动测试生成系统要求标志某些引线变量的特殊属性等操作，最后形成以功能块
为基本逻辑单元的、按逻辑级从低到高顺序排列的链表结构的拓扑电路‘协141。
3．2．3 CUT的链表拓扑结构
CUT的链表结构要设计得紧凑，使用方便,既要省内存，又要查询速度快。下
面给出的TB，～T取的链表结构经实际证明效果较好,可以作为一种参考结构。
1）TB,
TB．是CUT的总信息说明和链表目录.具体包括以下信息：
（1）CUT名称；
（2)TB：记录名称及记录数；
（3）T臣记录名称及记录数；
（4）TB4记录名称及记录数；
(5）TB，记录名称及记录输；
(6）CUT总信息记录。包括PI总数、PO总数、反馈线总数、功能块总数、引线变
量总、最高逻辑级数、最高时序级数．
2) B2
TB，是CUT的引线变量表。自动测试生成给引线编号的规则是：对每个功能块
的每条输出线编一个号,此号称为引线号或引线变量号。输入线不另编号，与其先
行输出线共用一个变量号。PI线按虚拟功能的输出对待.虚拟功能块是指虚设的、
输出个数为l、输入个数为0的功能块，在TB2中一个引线变量占一个记录，记录号
与变量号相同。一个记录包括以下信息：
（1)引线所属硬单元的位置及引线的引腿号；
(2)引线在功能块中的输出端号;
(3）引线扇出个数；
(4)引线所属功能块的说明信息在TB:中的记录号;
（5)引线的后继说明信息在TB。的记录号；
(6）引线特殊属性标志位.
3)TB3
TB，是CuT的功能块说明信息表。每个功能块在TB,中占一个记录,记录号即是
功能块在CUT中的序号.一个记录包括以下信息；
（1)功能块类型编码；
(2)功能块输出个数和输入个数；
(3)功能块逻辑级别；
（4）功能块的输出说明：按输出端号从小到大顺序，逐个说明功能块每个输出的
引线变量号，并给出每个输出的后继信息在TB4的记录号；
（5)功能块输入说明：按输入端号从小到大顺序，逐个说明功能块每个输入的引
腿号及对应的引线变量号。
在功能块输出，输入说明栏目中，每个输出，输入后面都附加一个标志域。标志域
中动态记录树标记和引线跳变标记信息。输入标志域中还给出该输入是否反馈线的
标记。
4)TB，
TB4是CUT的后继信息说明表。一个引线变量的后继说明占一个记录.一个记
3) 录包含下列信息：
（1)引线毛的后继功能块在TB3中的记录号；
(2）后继功能块与鼍相连的输入端号。
鼍有几个后继，在TB4中便有几个记录.最后给出记录结束标志。
5)TB5
TB。是CUT的初级输出列表。表中把可做为测试回收点的特殊测试点也做为PO
给出。每+PO在TB5中占一个记录。一个记录包括下列内容：
（1)初级输出的引线变量号；
(2)初级输出的插脚名或管腿号；
（3)初级输出的特殊属性标志,是否脉冲输出和特殊测试点等。
3．3预处理
随着自动测试生成系统功能的日趋完善,处理能力的不断提高，预处理技术的
地位显得越来越重要.它不仅可为加速测试生成提供启发引导信息,而且，许多在
测试生成过程中要反复用到的信息,在预处理阶段一次性生成，有利于提高自动测
试生成的执行效率。
3．3．1生成CUT的目标故障表
之所以把生成CUT的目标故障表归到预处理技术中，是因为它既涉及把自动测试生成采用的故障模型具体化的问题，又涉及到根据故障等价原理对模型故障进行
等价归并得技术。既要达到故障模型要求，又要尽量精简目标故障数,以减小自动
测试生成的计算量是本程序的目标。
1)模拟故障的等价归并
（1）基本门的等价故障
与（与非）门用输出的0(1)故障代替所有输入的0故障;或(或非)门用输出
的1（O）故障代替所有输入的1故障．非门和驱动门只需设输出的墨一a一0肛一口一l故
障。
(2) 电路中的等价故障
①如图3．2所示。功能块BI的输出与B2的输入的0，1故障是不可区分的，只需设
B1的输出线葺j一口一0，J—a—l二个故障即可【1卦。

图3．2等价故障示意图1
②如图3．3所示，B1的输出扇出到B2和B3，这3条线要设6个模型故障。但由于这
34k线与地短路的故障是不可区分的，只需设1个即可，因此共设4个故障就够了.具
体来说，功能块B1的输出属于扇出源，要设S—a一0,J-a一1两个故障,B：和B，的输
入属于扇出分线,只需各设一个开路故障，对TTL电路设j—a一1，对ECL电路设
＄—a-0故障.

图3．3等价故障示意图2
统计结果表明，进行上述等价归并之后，CUT中的目标故障大约只有模型故障
数的三分之二。当然，还可以根据电路的逻辑关系做进一步的精简，但要从性能价
格比的角度考虑是否合算.
2)目标故障的表示方法
目标故障在内存中有两种表示方法：位表示法和字符表示法．
（1)位表示法
这种表示法是：一个功能块的故障表在内存中占一个单元.功能块的输出O／s口一1及输入故障分别用该单元不同的位表示，该位为1，表示该故障存在,
为0表示该故障不存在．这种表示法便于自动测试生成系统从目标故障表中取故障和
根据故障模拟结果对目标故障表进行故障覆盖，即把已被检测的故障从目标故障表
中删除。
(2)字符表示法
与位表示法相对应的还有一种用字符表示法存储的目标故障表，它给出了每个
目标故障在CUT中的物理位置。具体格式是：硬单元坐标，引腿号／故障值。
3．3．2从简到繁对CUT的测试树头排序
确定性测试生成的一般做法是按测试树头(即测试回收点，它包括PO和特殊回
收点）把CUT划分成若干测试区，按从简到繁原则逐个测试区地生成测试码、覆盖
故障.对各测试区重迭部分的故障不搞重复覆盖，这样可以较大地降低自动测试生
成的计算复杂性。这里的关键是对测试区从简到繁排序，也就是对测试树头排序。
实践表明，如果把树头顺序搞反了,则测试生成时间将成倍甚至按数量级增长f”。
3．3．3生成树标记及各引线的树头级距上h
1)树标记得作用
用于自动测试生成对大型CUT的处理一般都是按树或者说按测试区进行的，因
此,首先对当前测试树所含的功能块和引线变量给出树标记，将后续程序带来许多
方便。
(1)生成树故障表
树故障表是当前树的测试生成和故障模拟所用的目标故障表．它是从CUT的总
目标故障表中，把那些有树标记得功能块的输出和输入引线所对应的故障位分离出
来构成的。
(2)生成模拟功能块表
把有树标记得功能块按级别从低到高排列或者按故障模拟自行规定的顺序排列
起来，便形成模拟功能块表。故障模拟只需对表内功能块依次驱动计算,这样可以
避免对树外进行的无效计算.
（3)打跳变标记
即给出从故障线到当前树头所经过的所有引线可能发生的跳变标记。有了树标
记之后,只需分析有树标记得引线可能发生的跳变。
（4）确定故障敏化路径
测试生成需要确定敏化路径，DRFM测度计算中需要确定从故障线到树头的所有
敏化路径上的必要敏化条件，上述操作都是限制在当前树内进行的。有了树标记，
可以防止敏化路径向树外延伸.
（5）识别会聚型扇出点
电路中的扇出点有会聚型和发散型两类，许多测试生成算法和可测性分析方法
都考虑了会聚型扇出点的影响.要区分这两类扇出需要进行复杂的搜索判断。但是,
有了树标记就方便得多了。一个扇出源只要有两个以上扇出分支有树标记,则一定
是会聚型扇出源,否则就是发散型扇出源【1s—20l。
2)生成树标记的方法
给出树标记的基本做法是反复查询TB表和DB中的功能块连通矩阵。先从树头开
始，由TB，中的树头变量号找到TB：相应的记录,查出树头所属功能块在TB，中的记
录号，从TB3中查得树头功能块的类型编码，由类型编码可至IJDB中找到有关的连通
矩阵，从中可确定与树头有逻辑连通关系的功能块的所有的输入,再回到TB3中确定
这些输入的变量号，然后根据每个变量号重复上述1B，一TB3-DB．TB,的查询过程，
一直NPI为止．对上述过程中查到的TB,中的功能块及其有关输出、输入线都在TB，
的标志域中给出树标记.
3）引线的树头级距k
（1)引线的树头级距的定义
电路中引线墨按信号传播方向到达树头Y所经功能块的最少级数，称为薯的树
头级距，记为k“)．
（2）引线的树头级距的计算法则
①引线的树头级距的初值是:当置是故障线，其值为0；否则其值为一.
②如果功能块的输出为x，与x逻辑相关的输入是‘，屯,．．，%，则
’k(力=Inin｛k@））+1（i=1，2，¨．，哟
③如果毛，吃，．．，‘是x小的扇出分线，则
k（功=min｛Lh（x，））+10=1，2，．．．,”）
(3)引线的树头级距的用途
引线的树头级距是选择最短敏化路径的极好的引导函数，它具有计算简便、引
导准确的特点。用CUT的链表TB，～TB；中的现成信息，例如功能块级别进行引导行
不行呢？答案是否定的。因为即使在组合电路中，级别高的功能块也不一定就离PO
近，时序电路就更不用说了。对于反馈线较多的时序电路，特别是闭环电路，选择
敏化路径的矛盾十分突出,而用三.引导，可以保证每次都能选择较短的敏化路径。4)生成引线跳变标记和各引线的故障级距三。
（1）何谓引线跳变标记
引线苫，的跳变标记指的是目标故障确定之后，分析如果要从x，传播故障信
号的话,z，可能发生的跳变。跳变标记分0—-1，l一0,0—-1／1-—0（双跳变)和0--0
（无跳变)四类,在TB，的标志域中分别用01lO，1001，1111和0000表示。
(2)引线跳变标记得作用
从测试生成角度看，在一个电路中设定了目标故障鼍s．a．o之后,它中间的引线
可以分为两类：一类在逻辑上受薯的影响，一类不受葺的影响。前者称为故障相关
线,后者称为故障无关线．不管采用那种算法求测试，故障无关线都只需要(o，1，×）三
个值即可描述。因此，把故障无关线区分出来有利于简化求测试的运算过程.另一方面，
对故障相关线，通过跳变分析，排除不可能产生的故障信号，也可以简化相容性操作.
(3）引线跳变标记得生成方法
①方法流程
a)从CUT的目标故障标中取一位；
b）把此位翻译成拓扑电路的故障，对功能块输出端故障，给出故障引线变量号和故障值；对功能块输入故障，给出故障功能块在TB3的记录号及故障线的输入端号；
c)查故障功能块(对输入故障）的连通矩阵，确定与故障输入端有逻辑连通关
系的输出端的端号及其跳变；
d)从TB，中确定上述输出端的引线变量号及其后继TB。的记录号;
e）由TB。中查后继功能块TB，记录号及相应的输入端号；
0逐个查上述后继功能块的连通矩阵，由输入跳变确定有逻辑连通关系的输出
端的跳变：
g)重复d）～f)，直到PO为止。
②从输入跳变确定输出跳变的算法
设输入跳变A=100I／0110，连通矩阵中描述输出与输入逻辑连通关系的两位
B=(hi，b2），其中6l，b2∈(o，1），把占扩展成逻辑字C和D,其中
C=（blblblbl）,D=(b2626262）
则描述输出跳变的逻辑运算都是按位操作.
(4)引线的故障级距工。
①引线的故障级距的定义
电路中引线五按信号传播的逆方向到达故障线,所经功能块的最少级数，称为薯
的故障级距,记为k（薯).
②引线的故障级距的计算法则
a)引线的故障级距的初值是：当薯是故障线，其值为0；否则其值为oo.
b）如果功能块的输出为x,与x逻辑相关的输入是毛，X2，．．．,‘，则
k(功=min｛t_，(五））+l O=l，2，⋯，按上述法则完成计算之后，凡与故障线逻辑无关的引线的k=一，其他线k是
一个有限的正整数。
③引线的故障级距的用途
a)当采用从PO至t]故障线,或者说从上到下的反向故障敏化策略时，工。可做为
建立最短敏化路径的引导函数。
b)当采用G—F二值公式，用纵向回推法求测试时，通过工。引导，可以保证尽快回推到故障线。做法也是从树头的一种DRFM测度较低的跳变开始，每次都从(3-—
F二值公式的积之和展开式中优先选取k较小的输入变量的跳变向下展开，直到故
障线为止．
c)上。可作为从目标故障选择距离最近的树头的引导函数.测试生成的实践表
明,一个目标故障，总是在离它较近的PO上被检测的可能性较大．当已知电路中各
引线的k之后，可把所有的PO按三。从4，N大排序，以保证每次总是向离得较近的
PO驱动目标故障。这种从故障定树头的控制方法与传统的按树头划分测试区，或者
叫做重树头定故障的方法比较起来，对于反馈线很多的闭环电路，具有明显得优越
性，可使自动测试生成获得较多的时间效益。
(5）计算D】iFM测度，识别不可测故障
可测性分析方法给出的电路引线的测度值，是测试生成正、反向驱动过程中重
要的引导函数.静态测度分析，例如SCOAP方法，对每个CUT只需在预处理期间计
算一次电路引线的可控制性和可观察性值,计算过程相对来说是很简单的。但它对
测试生成的引导有时很不合理的。动态测度分析，例如DRFM方法,由于把测度值看
成是目标故障及其必要检测条件的动态函数，因此，要对每个目标故障计算一次电
路引线的动态约束四值测度值。此项计算也纳入预处理程序.DR．FM的计算复杂度比
SCOAP增大了，但它的精确性有了很大提高。它能对测试生成的搜索树进行有效修
剪，使自动测试生成对难测故障的回溯尽可能少；并能根据每个故障的测度值得大
小，识别包括冗余故障在内的不可测故障。从而有效地避免CPU时间的无谓消耗
t22-231。
(6)功能块表达式的预代真
测试生成的正反向驱动过程,一般是按功能块逐个进行的。因此无论是求敏化
条件还是某个变量值得回推条件，首先要处理的都是功能块的ca—7_方表达式.由于每个功能块在电路中都与其他功能块有一定的结构上的连接关系和功能上的逻辑关
系。因此，要解决正反向驱动过程中一致性问题,就必须用统一的电路引线变量号
描述各个功能块的表达式。这就要求把用各自的输入，输出端号表示的功能块的c立
方表达式转换成拓扑电路内部引线变量号表示的形式。一般把表达式数据结构的这
种转换叫做代真。
3．4测试生成
测试生成是自动测试生成的核心部分，是决定自动测试生成效率的主要因素，
从某种意义上来说，它是自动测试生成的关键所在。前面介绍的数据库、电路描述
和预处理三个模块中提供的各种信息，绝大部分是为提高测试生成的效率服务的。
3．4．1 G—F二值算法
该算法的主要特点是：采用布尔差分的数据描述形式,D算法的立方体运算方式，
并用G-F值分开的二值逻辑运算实现了九值逻辑运算的功能，从而简化了算法的程序
实现，提高了算法效率.该算法的另一个特点是首次实现了门级和功能块级电路、
组合电路和时序电路测试生成的统一处理。
1）从五值逻辑到九值逻辑
(1）五值逻辑与信号线的逻辑状态
对于正常电路,用｛O，1，×）三个值描述信号线在某时刻的逻辑状态是完整的。其
中×∈(0,1）表示信号线的不定状态。当电路中产生故障时,为了描述故障对电路信号
线状态的影响,三值逻辑己不够用,所以D算法引进了｛0,1，×，D,D)五个值，称为五
值逻辑.
(2)五值逻辑与故障敏化条件
引进九值逻辑可以弥补五值逻辑在描述引线逻辑状态、处理故障敏化条件方面
的缺陷．由于九值逻辑能准确描述信号线逻辑状态,包括故障对逻辑状态的影响，
能把一个故障的多个充分敏化条件综合成一个充分必要的敏化条件，因此能避免D算
法驱赶中所做的许多重复工作,提高算法效率.以九值逻辑运算为基础的D算法称为九值D算法Dlr／11241。
2)九值逻辑的G—F—-值表示法
(1）数字电路的G—F——值描述