1.引言

　　随着电子技术的飞速发展，集成电路的规模不断扩大，而引脚数却有一定的限制，许多电路被封装在芯片内部，外部可达到的测试点、原始输入、原始输出所占的比例越来越少，导致集成电路的测试和故障诊断越来越困难。故障诊断中最重要的是要找到故障的测试矢量，即测试生成。集成电路的测试生成问题是数学上公认的难题——NP完全问题，在过去几年中，国内外的一些学者虽然提出了许多新的测试生成算法，但是到目前为止还没有一种算法适用于所有的电路，集成电路的测试生成问题己经严重地影响了微电子技术的发展。

　　2.集成电路测试生成算法的分类

　　(1)按照被测电路来分可以分为组合电路测试生成算法和时序电路测试生成算法两类。组合电路测试生成算法的研究对象是组合电路，时序电路测试生成的研究对象是时序电路。

　　(2)按照获取测试矢量集的方法来分可以分为确定性测试生成算法和非确定性测试生成算法。非确定性测试生成主要是伪随机测试和加权随机测试算法。确定性测试生成算法是通过算法确定出测试矢量或测试序列。

　　(3)按照故障模型来分可以分为高级测试生成算法和低级测试生成算法两大类。高级测试生成算法的故障覆盖率一般不如低级测试生成算法的高，但是测试时间要比低级的测试生成时间少。

　　(4)按照算法采用的技术或理论来分可以分为层次式的测试生成算法、符号化的测试生成算法、基于遗传算法的测试生成算法、启发式的测试生成算法等。层次式的测试生成算法将电路的无故障部分用功能块表示，有故障的部分用门电路表示;符号化的测试生成算法基于二进制判决图(BBD);基于遗传算法的测试生成算法通过确定能量函数的最小值点求得测试矢量;启发式的测试生成算法使用一些启发式的技术。

　　(5)按照算法给定的条件来分可以分为面向故障的测试生成算法和面向测试的测试生成算法。面向故障的测试生成算法从给定的目标出发，寻找目标故障的测试矢量或测试序列;面向测试的测试生成算法从输入激励出发，寻找它能测试的故障。

　　(6)按照算法的特征来分可以分为基于结构的测试生成算法、基于仿真的测试生成算法等。基于结构的算法主要利用电路的结构信息;基于仿真的测试生成算法需要逻辑仿真器作为辅助工具。

　　3.电路测试生成算法的发展和现状

　　(1)路径敏化法。组合逻辑电路是数字电路测试的研究基础，1959年Eldred提出第一篇关于组合电路的测试方法，但是该方法不能解决两级以上组合电路的故障测试问题，是一种比较简单的测试生成算法。随后D.B.Armstrong根据Eldred的基本思想提出了一维通路敏化的方法，即路径敏化法，其主要思想是：从故障源处到原始输出之间寻找一条路径，这条路径就称为敏化路径，沿着这条路经，故障效应可从源处传播到原始输出，也就是故障效应可观。

　　(2)布尔差分法。布尔差分法由1968年seners等人提出，它将电路描述为数学表达式，从而可进行严密的数学推导，因此有较高的理论价值。在布尔差分法的发展中具有代表性的是主路径法，主路径法将通路敏化的概念引入到布尔差分算法中，提高了布尔差分法的效率。近年来发展起来的二元判定图(BDD)测试生成方法，也利用了布尔差分法的原理。布尔差分法的优点是可以求得给定故障的全部测试，但是对复杂性较高的电路，用它进行测试生成时需要做大量的布尔差分运算，而在计算机上对这些运算的处理是一件困难的工作。

　　(3)D算法。Roth等人于1966年提出了基于集合理论的多路径算法——D算法，主要思想是同时敏化从故障源到电路输出的所有全部可能的通路，它克服了一维通路敏化法的局限，采用多维敏化的思想同时敏化从故障位置到电路的所有输出端的全部通路，只要所考虑的故障可测，用D算法就一定能求得故障的测试矢量。D算法是第一个建立在严格理论基础上的组合电路测试生成算法，它具有算法上的完备性，且便于在计算机上实现，是比较成功和目前应用较广的测试生成算法之一。D算法在进行测试生成时把大量时间花费在对许多不同路径的试探上，在组合电路的规模较大时，用该算法计算复杂，效率不高。

　　(4) PODEM算法。1981年Goel对D算法进行改进提出了PODEM算法，该算法思路是：对激活的故障向后追踪到原始输入，搜索所有可能的原输入赋值，只要找到一符合要求的即可作为测试图形，算法即结束。这种算法是一种分支限界的隐式枚举算法，它吸收了穷举法的优点，采用逐个地给原始输入赋值的办法为给定故障生成测试，从而避免了许多盲目的试探，减少了D算法中回退与判决的次数。PODEM算法比D算法的测试生成速度快若干倍，并显著地减少了回退与判决的次数，但仍然存在回退的问题。

　　(5)FAN算法及其扩充和发展。为加速测试生成，Fujiwara等人于1983年提出了FAN算法。该算法在减少回退次数，降低每一次的回退时间以及对扇出点都做了细致处理。FAN算法的运算速度快于PODEM算法，不仅回退次数少，而且故障覆盖率较高。FAN算法丰富和发展了测试生成算法的基本思想，近年来出现的一些较为有效的方法，大都基于它的思想，是它的扩充和发展。在FAN算法的发展中，有代表性的一种算法是Michael等人于1987年提出的SOCRATES算法。这种算法将组合电路的测试生成问题描述成一个对判定树的搜索过程，改进了FAN算法的蕴涵过程，使蕴涵更加彻底，用控制的概念解释唯一敏化现象，使算法在故障传播时对更多的情况赋予确定值，扩展了多路回退策略。

　　(6)FASTEST算法。FASTEST算法是基于PODEM算法的时序电路ATPG算法。FASTEST把测试生成问题当单个问题处理，选择全面的优化决策，所有处理采用时间向前处理，因此不会在确认不可到达的状态上浪费时间，另外测试长度保持最小。FASTEST算法的主要优点是可以快速地确认不能达到的状态，缺点是需要对时序单元的总数和激活故障的时序单元有较准的估计，如果估不正确，会大大浪费时间和存储资源。

　　(7)CONTEST算法。CONTEST算法是对选定的初始矢量在模拟结果的基础上计算成本函数。CONTEST算法对组合及时序电路都有效，可以对一组故障、单个故障生成测试矢量，也可生成电路的初始时序，但三方面应用时成本函数不同。用CONTEST方法进行测试生成要优于其他方法，但有时会生成较多的测试矢量，因为试探时会选择相邻的矢量。CONTEST的另一个应用是寻找初始化矢量序列，使得电路从未知状态转到已知状态。

　　4.结束语

　　随着微电子技术的飞速发展，有些传统的算法已经不再适用，有些方法还存在不足，探索新算法，改进己有算法，是测试生成算法研究的重点。

　　参考文献

　　[1] 于云华，石寅.数字集成电路故障测试策略和技术的研究进展.电路与系统学报，2004，9(3):83一91

　　[2] 向东.数字系统测试及可测性设计.科学出版社，1997:2一11

　　[3] 刘晓东.集成电路测试生成算法的研究.哈尔滨工业大学博士论文，2003:l~20