数字电路测试生成算法综述于功敬，魏蛟龙（北京航天测控技术公司，北京 100830）摘要:随着数字电路的规模和复杂性不断增加，自动矢量生成技术己日益成为数字电路测试与诊断的瓶颈环节。本文主要讨论了电路的测试及故障检测的一些基本问题，并对数字电路测试生成的主要算法进行了分析和比较。最后预测了测试矢量自动生成技术的发展趋势。关键词:故障检测；测试矢量；数字电路；测试生成算法1 引言数字电路测试与故障诊断包括四个步骤：建立故障字典、加载激励、回收响应和分离故障，即选择激励通道和响应通道并建立激励矢量和故障模式之间的映射关系，然后向被测对象施加激励矢量，并采集其响应矢量，最后通过故障字典来分离故障。故障字典先于实际测试而建立，并直接用于测试结束后的故障分析，包含了被测对象故障征兆的全部信息，是贯穿四个测试诊断步骤的关键数据。而故障字典对于故障图样分辨能力和覆盖程度的优劣，完全取决于测试激励矢量的生成质量，这就是数字电路测试矢量自动生成技术所要研究的中心问题。自从1966年Armstrong提出一维通路敏化法以来，数字电路测试矢量自动生成理论的研究课题经历了一个从雏型到成熟、从理论到应用、从实用到完备的发展历程。可以从不同的角度对不同的生成算法进行划分，如按时间跨度可分为传统算法和现代算法；按其是否引入随机策略可分为确定性方法和随机性方法；按其使用的分析工具可分为代数方法和结构性方法；而按其生成调度策略可分为串行算法和并行算法等。本文主要介绍了布尔差分法、D算法系列、临界路径法以及G-F算法等，着重阐述其算法思想及其相互之间的性能比较，然后对现代ATPG理论中引入的新方法、新思路和前景等进行了简要的介绍。2 布尔差分法布尔差分法由Sellers等人提出，是组合电路测试生成的一种方法。其主要特点是将电路描述抽象为数学表达式模型，从而可进行严密的数学推导，因而具有较高的理论研究价值。这种方法通过对数字电路的布尔方程模型进行差分运算，能获得测试矢量集的一般表达式，并能求出所给故障的全部测试矢量，因此具有理论上的完备性。考虑实现函数的组合电路C，若以a表示输入的s-a-0的故障，则故障电路对应的函数，我们用来表示这个函数。同样，若是s-a-1故障则故障对应的函数为3。用布尔差分法求故障的测试矢量集的本质是求满足条件=1的测试矢量T，检测故障a s-a-0的测试组对应的矢量集为： T= 其中因子叫做f对布尔差分，用表示，它给出f值单独对值敏化的全部条件。因为把与故障输入值相反的信号值加到出故障的输出上，而保证这个信号能影响f的值，则表示s-a-0故障的全部测试组。同样，检测s-a-1故障的全部测试组由布尔表达式确定。布尔差分法能获得测试集的一般表达式，可以求出所给故障的全部测试矢量。由于它将电路描述抽象为数学表达式，从而可进行严密的数学推导, 因此有较高的理论价值。布尔差分法仅适用于组合逻辑电路。而且对于复杂性较高的电路，特别是对L S I、VL S I 电路，用它进行测试生成时需要做大量的布尔差分运算，复杂度高。3 D算法及其改进算法D算法是由Roth等人提出的，它克服了一维敏化法的局限，采用多维敏化思想的同时敏化从故障位置到电路的所有输出端的全部通路它用5个值（0，1，X, D,）来描述电路中的各节点的状态算法由故障激活、故障驱赶和线相容等步骤组成只要所考虑的故障可测，用D算法就一定能求得故障的测试4。D算法的基本步骤分为三大部分：1）故障激活，即使故障的影响能反映出来。某线s-a-0故障的激活条件是使该线出现1值的原始输入矢量；某线s-a-1故障的激活条件是使该线出现0值的原始输入矢量。具体做法是：选择故障的一个原D立方作为初始测试D立方。2）正向驱赶，也称D驱赶，即将当前测试D立方与有关元件的传播D立方进行D交，目标是使D或信号向电路输出端推进。D交的结果为新的测试D立方，可表示为。D驱赶要进行到输出端出现D或为止。3）反向跟踪，也叫一致性操作，即将当前的测试D立方与有关元件的奇异立方进行D交，目标是求得电路中尚未确定的信号值。可表示为。一致性操作要进行到求得电路原始输入端的一组无矛盾的值为止，这组输入值就是所求的一个测试。D算法的特点是具有通路敏化的能力，即它能在几条扇出重会集的路径上传播故障，这是一维通路敏化方法所不具有的。但D算法在选择敏化通路时其随意性太大，尤其是考虑多通路敏化时各种组合的情况太多，然而真正有效的选择往往较少。因此在做D算法时，做了大量的返回操作，所以很难付诸实际应用。为了尽可能减少返回操作的次数，大大缩短计算时间，使D算法能真正付诸实践，又产生了各种改进的算法。如 PODEM（PathOriented Decision Making）算法和FAN（Fan outOriented）算法。PODEM算法是一个直接搜索过程，它的决策仅由PI赋值所组成，即只要找到一个满足要求的矢量作为测试矢量，算法过程即告结束。若不存在任何输入矢量可以作为测试，则该故障是不可测试的。PODEM算法主要解决的问题是按什么变量次序未穷举输入矢量才能较快地得到所需要的测试矢量。PODEM算法由于不能及早地发现不存在解的情况，因此无效的选择和返回的次数还是很多。FAN算法对PODEM的回溯运算做了两点主要的扩充：1）在FAN中，回溯可以停止在内部线（主导线），而不只是停止在PI端线上；2）FAN使用多回溯过程试图同时满足一组目标，而不是试图满足单一的目标。4 临界路径法前面所讨论的测试产生方法都是面向故障的，即针对特定的故障推导测试。另一种方法是推导能检测许多故障的测试（测试推导不依赖故障），这种方法称为临界路径测试产生法。它类似于LASAR(逻辑自动激励和相应)系统中所用的方法，可用来检测固定型故障。从直观可知，沿敏化路径有一半固定型故障是可用同一个测试检测。用于组合电路的临界路径测试产生算法如下：1）选择一条输出线，规定其临界值为0，利用敏化立方朝着输入向后驱动该临界值。当驱动存在选择可能性时，可任选一种条件，以后通过后退考虑所有其它选择的可能性。2）最初所选的输出线规定其临界值不为1，重复上述过程。3）对其余的输出线重复1，2过程。这个算法对于要求多路径敏化的故障可能找不到测试。为了节省计算时间，当存在选择可能性时，不一定考虑所有的选择，而采用每个测试一经产生后立即进行模拟，然后仅对以前还没有求得测试的s-a-1(0)故障，在信号线S上产生规定临界值0(1)并进行处理，这就减少计算时间，并可以产生较少的测试码。但是，可能对某些故障找不到测试。临界路径法类似于D算法中的线合理性过程。不同的是，在临界路径法中，首先试图利用敏化立方使信号满足合理性，而D算法则不区分敏化立方和其他原始立方。5 GF二值算法GF二值算法采用布尔差分的数学描述形式，结合D算法的立方体运算方式，用GF二值分开的二值逻辑实现了九值逻辑的功能，简化了实现，提高了效率。GF算法首次实现了门级和功能块级电路、组合电路和时序电路测试生成的统一处理。把电路y=f(X)描述成yG=f(XG)和yF=f(XF)两个电路，即一个是正常电路，输入、输出变量均冠以上标G，即yG=f(xG1,x02,xGn)。另一个是故障电路，输入、输出变量均冠以上标F，即yF=f(xF1,xF2, ,xFn)。对任何一个逻辑实现函数为y=f(x1,x2,L,xn)的电路，如果有一组输入激励(x1,x2,L,xn)能检测其中的某个故障或者某种多故障，则根据测试码的定义，应有yG yF f(xG1,xG2,L,xGn) f(xF1,xF2,L,xFn)这就是电路的输出变量y（或者输出函数f）关于输入变量x1，x2，xn的G-F二值公式。G-F二值算法求解测试矢量的步骤为：1）故障激活：求故障功能块的激活条件表达式；2）故障传播：构造敏化路径，并求出路径上各敏化功能块的传播条件表达式；3）按1）、2）中得出结果建立测试码方程；4）方程求解；G-F算法首次实现了门级和功能块级电路、组合电路和时序电路测试生成的统一处理。如果将G-F二值公式中的每个变量都带上时帧标记，即可将组合逻辑测试码生成的GF算法应用于时序电路。与D算法、PODEN算法和FAN算法相比，G-F算法善于处理较复杂的功能块构成的电路，便于处理多故障和时序电路。6 前景当今测试模式自动生成研究领域颇具远景的几个重要方向是：6.1基于扫瞄链方法的内置测试中测试矢量生成理论的研究内置自测试（BIST）是一种在设计时即将专用测试电路嵌入被测时序电路内部的测试方法，其基本思想是将时序电路的所有时序元件串接在一起形成一条扫瞄链，便于在测试时通过该扫瞄链实现对时序元件状态的直接控制。BIST的ATPG利用线性反馈移位寄存器(LFSR )生成测试向量，利用多输入特征寄存器(MISR )提取测试响应。如何构造具有最大自治性的多条扫描链，克服不同扫描链间的结构相关性，提高BIST测试的故障分辨精度和覆盖率，是该研究方向的核心课题。6.2非确定性理论方法在测试生成领域的应用比较具有潜力的有粗糙集理论、混浊算法、小波理论、神经网络以及遗传算法等，为ATPG理论的研究开辟了新的思路，并可望在未来形成新的边缘交叉学科。6.3并行生成方法随着现代计算机应用网络的飞速发展，分布计算理论已渗透到测试生成领域中，并与本领域中的传统技术实现了无缝结合，继而形成了新的研究热点。将数字系统的目标故障集按其内部相关性强弱进行子集分割，并将各子集分别分配给分布式网络中的不同站点进行生成，以实现多机并行、分布处理，从空间上有效地缓解了VLSI电路测试生成在时间上的NP完全问题。6.4可测性分析(TA)理论在ATPG中的应用研究可测性研究的初衷是在设计时提高电路的可测试性（Testability），以降低对最终产品进行测试诊断时的故障分离难度。由于能够在测试生成过程中为构造敏化路径提供高度精确的启发信息，TA理论的研究成果能够大幅提升ATPG系统的时间和空间效率。DRFM（动态约束四值测度）方法是比较成熟的经典TA方法，而BIST(内置自测试)则是TA理论应用于ATPG领域的新成果。参考文献1郑崇勋.数字系统诊断与综合.西安：西安交通大学出版社，19872 Roth JP. Diagnosis of automata failures :a calculus and method. IBM Journal of Research and Development ,1966 ,10(July):278-291.3Fujiwara H Shimono T, On the acceleration of test generation algorithm. IEEE trans. Compute,1983,C-32(3);215-222.4 Friedman A D ,Mennan P. Fault detecting in digital circuits. Englewood Cliff ;Prentice Hall Inc ,1978.5陈延愧等.数字系统测试与容错.南京：东南大学出版社，1990.6Cox H, Rajski j.Avemethod of fault analysis for test generation and fault analysis .IEEE Trans .Computer Aided Design ,1988,7(7):813-833. 7曾芷德.数字系统测试与可测性.长沙：国防科技大学出版社，1992