集成电路测试生成算法研究

蒋焕

摘要：集成电路测试，实则对集成电路或是整个模块作出测量，将输出回应对比我们的预期输出，从而判断元器件的性能优劣及其功能。目前，已成为检验设计、生产控制、分析失效的可靠手段。本文介绍了测试的基本原理、过程，阐述了成算法的具体性能，最后展望今后的发展走向。

关键词：集成电路；测试；生成算法

1 集成电路测试原理

1.1基本原理

被测电路DUT，假设为已知实体：原始输入x、网络功能集F（x），计算出输出回应y，同时判断y能否代表电路上的具体输出，如图。对测试来说，其目的在于测试输入，但测试系统重点是将测试输入投放于整个被测器件中，以原始输出管脚为起点，经采样后作出输出回应，以得到最后的结果。

1.2测试过程

(1)测试设备

测试设备，其功能在于面向测试器件提供一定的输入，检测它的输出。根据相关指标，如服务能力、编程难度，其费用也不一样。

(2)测试接口

对测试插座进行选择，制作一份测试负载。

(3)测试程序

程序软件，涵盖了指令序列，如上电、向量以及检测输出引脚，同时包括输出信号、预期响应二者的对比等。

(4)数据分析

判定被测器件究竟是否达标；

为生产制造提供有价值的信息；

指出设计方案中存在的某些薄弱点；

2测试算法性能分析

2.1布尔差分法

布尔差分法，最早的提出者为Sellers。根据布尔方程式，得出测试集相应的表达式，计算故障的各个测试矢量。当布尔差分(df(x))/(dx_(n+1));f(x_1,…,x_n,x_(n+1))+f(x_1,…,x_n,(?)=1时，对数字逻辑电路进行敏化这一特性。它将电路看做是一个数学式，以完成缜密的逻辑推导。布尔差分法中，主路径法是极具典型的一种，将通路敏化融合至布尔差分法中，使其效率得到了大幅度的提升。不过，该法也有如下短板：针对LSI、VLSI这些复杂的电路，在测试生成前应当反复接受高强度的布尔差分运算，难度非常大。

2.2PODEM算法

1981年Goel对D算法进行改进提出了PODEM算法。大致思路：故障在被激活后，继续追踪至它的原始输入，对原输入赋值进行搜索，仅需找到其中一条满足条件的，就可纳入测试图形。该算法属于典型的隐式枚举算法，有清晰的分支限界。它保留了穷举法的特点，通过逐个地输入赋值，对给定故障进行测试，减少试探的盲目性，省去了回退的次数。和D算法相比，PODEM算法在生成速度上要快的多，不过回退现象仍旧少不了。

2.3FAN算法及其扩充和发展

为提高生成速率，Fujiwara等又引申出一种FAN算法。对于回溯次数、时间包括扇出点，该算法均作出了较好的改进。FAN算法对现有的测试理念作了延伸，如Tops算法，就是最终的一种扩充结果。在FAN算法的整个历史上，Michael等首推的SOCRAT ES算法尤为典型。它将测试生成看做是对判决树进行搜索的整个过程，对FAN算法作了改良，使蕴涵比原来更完善。一组关于10个电路展开的实验得知，该算法下，回溯次数不超出10次，其故障覆盖率达到100%。同时，能够查找各条电路上的所有冗余故障。为此，SOCRAT ES 算法已成为行业中性能最优的一种算法。

2.4 TREE和 SPOG算法

TREE算法一开始是由Chow dhary等人引出，该法可以将单输出的模板予以成功提取。同时，利用2个假设（1：图G中，假设子图集S仅限于某些子图，该类子图并不属于S中的任何子图；在S中，频数＞1。2：在G中，假设每个结点v均有f条入边 ，它的前驱结点依次是Hl~ll ⋯u，且索引号都是唯一的，k[u,v]=i，l≤i≤f)将树形模板控制为v(v-1)/2。大致步骤：

1 )对G的各个结点，分别完成拓扑排序v⋯v。

2)X,j于任意2个结点Vi，Vj(1≤i,j≤n)，以2个结点为根，生成一个最大子图，将其看做是模板Sm。

3）在模板库中，分析有没有和Sm功能完全等价的其他模板。若无，则需要再模板库中补充Sm；若有，则放弃Sm。SPOG算法，实则是对TREE算法作出的一种延伸，将模板增加了多输出。SPOG子图，其区间同样也是v(v-1)。

TREE、SPOG算法均属于代表性的模板提取算法，基于2个假设能够对其中的全部模板进行提取，对模板覆盖有极大的益处。

2.5 CONTEST算法

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

2.6 GA-BP算法

遗传算法(GeneticAlgorithm，GA)的理论是根据达尔文进化论而设计出来的，是一种通过模拟自然进化过程搜索最优解的方法。大体意思是生物是朝着好的方向进化的，在进化的过程中会自动选择优良基因淘汰劣等基因。向好的方向进化就是最优解的方向，优良的基因是符合当前条件的样本基因。遗传算法主要分为选择、交叉和变异这三类操作完成淘汰机制，使训练后的自我进化按照条件朝着有力的方向进行，最终取得最优个体和解集合。一种算法的形成，需要编码、解码等。根据遗传算法，我们可以BP神经网络来对最优个体作出预测，同时对网络设定好初始权值以及阈值。经过训练，输出最后的预测样本。

3电路测试的发展趋势

在集成电路生产行业，测试的地位日渐突出。近些年，学者们屡次对测试算法作出了改动、优化，同时提出几种其他的生成算法．如层次式、专家系统以及BDD测试。为解决测试生成眼前的难题，有必要从IC CAD的视角，对设计、测试问题作出统筹把握，重点对可测性设计进行研究。关于测试生成，其后续的发展走向有：

（1）提高生成算法的运行效率。缩小搜索空间；探索新的搜索策略；增加电路单元的现有级别，由门级转向于模块甚至功能级。

（2）研发专家系统，探索相关的并行处理。测试生成，必须要借鉴过往的专家经验，结合被测电路上得到的结构信息，对专家系统进行研发。考虑到被测电路中包括不少故障，它们彼此是独立的。借助并行系统，能够将故障、测试两项任务交由若干处理机负责，以便对测试生成作出并行处理。

（3）可测性设计。关于电路可测性，泛指测试简便性，也可以是测试能力。有如下2层不同的理解：一是在有限的激励或是点位上，电路中的故障能否被成功地定位或是检测出来；二是假设故障是可测的，但其测试矢量要耗费很久的生成时间，在现实中难以做到。为设计一种可测性较高的电路，特定、构造设计法是行业中被公认的选择。特定设计法，即面向给定设计，对测试问题进行处理。然而，有不少设计不能选择该方法。该技术属于典型的试探性，并非系统性，其原则是用便捷、节约的方式，让给定设计变得更加的可测。而构造设计法，是面向一些通用的可测性问题，有自己成套的设计规则。如内建自测试（BIST），就是十分典型的一种构造设计法。

结束语

伴随电路结构的复杂化，集成度的持续提升，电路测试的难度在增加。尽管人类在这方面做了不少的付出与努力，但电路测试至今仍是全球公认的难题。除探索精准度更高的测试算法外，研发可测性设计技术，节省电路在制造、使用以及维护方面的成本，同样也是人们需要关注的方向。

参考文献

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

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

[3]罗汉青，梁利平，叶甜春.基于遗传算法的随机测试生成技术探讨[J].电子测试，2013,45(13):75-78