基于遗传算法的组合电路BF故障Iddq诊断生成研究

关键词：IDDQ；遗传算法；电路诊断生成 中图分类号：TN407 文献标识码：A An Algorithm Based on GA for Generating Diagnostic IDDQ Test Set for Bridging Faults ZHANG LanI, ZENG min2, XU hong-bin2 (1.ZTE,Zijinghua Road 68, Nanjing, Jiangsu 210012,China; 2. School of Automation Engineering, UESTC, Chengdu, Siehuan 610054, China) Abstract: This paper describes a diagnostic generation algorithm for Iddq. This algorithm is based on the GA, some effective technique, such as local - optimization procedure and levered generation, have been em ployed to improve the efficiency of the algorithm. Experimental results for large ISCAS85 benchmark circuits demonstrate its efficiency in comparison with results of previous methods. Key words: Genetic Algorithm; Diagnostic Generation 1 引言 电路的故障诊断包含故障检测和故障定位。电路的故障诊断在大规模集成电路的生产过程中具有重要意义。它有助于分析芯片模板上的各种缺陷从而最终提高芯片的产量和质量。故障诊断包括两种方法：物理检测方法和故障字典诊断方法。物理检测方法往往需要复杂的装备，甚至需要打开集成电路的封装损坏电路。故障字典诊断技术是基于故障字典项与实际故障响应的匹配来进行故障诊断。这种故障字典方法需要精确诊断生成技术来实现。 组输入向量下，观测电路馈电流的响应序列，再采用故障字典或电路结构分析的方法对电路响应序 2 BF故障模型 当电路中两个或两个以上的节点由于各种物理原因连接在一起就形成了桥接故障(bridge fault)。在CMOS技术的电路中，BF模型的故障占所有物理故障的40％ - 50％。[5] 个桥接故障。 这一规则对于非反馈桥接故障是精确的。当桥接故障两端点处于相反电位值时，静态电流必然升高。对存在反馈的桥接故障，则可能使电路产生震荡，这种震荡造成的故障覆盖损失是可以忽略的。[5] 任一CMOS管都有四个节点：Gate(G)、Source(S)、Drain(D)和n - bulk(N)。这样对于任一 CMOS管都存在六种漏电流故障：GS、GD、GN、 SD、SN、DN。这就是所谓的漏电流故障模型。针对BF模型的测试生成算法也能有效的生成漏电流模型的测试向量。[5] 3 故障诊断生成算法 举例说明如下：图1的电路中的候选故障包括：{<1，2>，<3，4>，<5，6>，<6，7>，<8，9>，<9，10>，<10，11>}，给定一组输入向量序列T=(T1，T2，T3，T4，T5)。每一个输入向量下，各个节点都对应着一个电位值。例如假设在T1下12个节点的值依次为：(+，-，-，+，-，+，+，+，-，+，+，+)，则各个故障点对应的电位值依次为：<+，->，<-，+>，<-，+>，<+，+>，<+，->，<-，+>，<+，+>。由JDDo电路检测判定规则可知，对应T1的可检测的故障为<1，2>，<3，4>，<5，6>，<8，9>，<9，10>。不可检测的故障为<6，7>，<10，11>。可记各个故障的响应依次为(1，1，1，0，1，1，0)，其中1表示该故障可检测，0表示该故障不可检测。对输入序列 T中每一个输入向量都模拟之后，我们分析各个故障点在这组输入序列T下的响应序列，例如，在T输入序列下<1，2>对应的输出响应序列为(1，1，0，1，0)。每个故障点都对应着一个测试响应序列。算法的目标就是使得这个输出响应序列在不同故障下对应不同的响应序列。 算法主要分成三个阶段：故障选择、遗传算法和逐级故障集生成。下面将依次介绍。 故障选择主要有三种策略：基于电路的拓扑结构进行故障选择、所有可能的故障以及随机从所有可能的故障中进行选择。在本文中按照电路的拓扑结构选择故障，即电路中各个节点只可能与其位置靠近的节点发生桥接故障。 遗传算法(Genetic Algorithm，GA)是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。故障的诊断生成问题实质也是优化问题。先随机产生一组测试向量序列集合作为基础原始种群。再通过交叉、变异寻求更优的个体。最后，再通过局部寻优过程寻求最优的个体。遗传算法中的代价函数是判定种群中各个个体的适应能力的标准。本算法的代价函数为：所有待测故障的测试响应序列的相同序列的个数。在上例中：假设在输入序列T下，故障<1，2>和<3，4>的故障响应序列都为(1，1，0，1，O)，其他故障的响应序列各不相同，则该序列T的代价函数为1。遗传算法的最终目标就是使得代价函数最小。对通过交叉变异获得的新的个体，因为整个过程具有较大的随机性。因此在获得了新向量序列后，算法加入了一个局部寻优运算。即在对种群中的每个个体的因子进行求反运算。求出其中最优的个体作为新的个体。通过仿真发现，在这种局部寻优算法下，更容易在新个体中形成更优的个体。在初始种群中选用随机产生的方法，但其中加入启发性的个体有助加速整个过程找到最优个体。在初始种群中先加入 [0000．．．．]、[111111111．. . . . .]、[10101010．．．．]等受控个体，这样的选择可以使个体在取值空间中的分布比较均匀，使初始种群中的个体具有一定的代表性。 的故障。通过一组测试向量序列的诊断后，原有的候选故障集合就可以分成若干个较小的候选故障集，再对这些减小了的候选故障集合进一步进行诊断生成，则可以获得良好的诊断精度。 4 仿真结果 为验证算法的可行性和有效性，首先采用 c17，Schneider，全加器电路来验证该算法。仿真实验中选用Matlab编程，在CPU为Celeron1．7G，操作系统为windows xp的计算机上进行仿真。电路仿真结果列在表一中。从仿真结果可知，对这三 从表中可见我们的算法可以有效地检测所有候选故障。并能以较高的精度区分绝大多数的故障。将该算法与文献[1]中所提到的算法进行了仿真比较，在同样的仿真环境下用Matlab编程实现了[1]中的算法。比较结果列在表三中。从表中可以看出我们的算法与[1]生成的诊断精度基本相同，但所提出的算法的诊断生成时间远优于[1]中提到的算法。 5 结论 了电路逐级诊断的方法，有效地提高了电路的诊断精度。采用ISCAS电路来仿真该算法，仿真结果显示算法能生成具有较高故障诊断精度的测试向量序列。文中将算法的仿真结果与已有文献的算法进行了比较，结果表明了所提出算法的有效性。 Faults：表待测故障数。括号中为实际可诊断的故障数。Rem：表生成向量序列不能区分的故障数。括号中为可诊断的故障中剩余不能诊断的故障数。FC：表故障诊断覆盖。TS：表测试序列长度。括号中表示最小的故障测试序列长度。 *根据电路的结构图可知；，说明这两组故障同时可以被检测或不被检测，所以故障<2，8>和<1，9>以及故障<4，10>和<3，11>都是不能区分的故障。 **同理全加器中故障<2，4>和<1，5>以及<1，4>和<2，5>都是不可区分的故障。 参考文献 [1] Tsuyoshi Shinogi, Terumine Hayashi. A Simple and Efficient Method for Generating Compact IDDQ Test Set for Bridging Faults[A]. 16th IEEE VLSI Test Symposium,, 1998, pp. 112～117. [2] Sreejit Chakravarty, M. Liu. Algorithms for Iddq Measurement Based Diagnosis of Bridging faults [J]. Journal of Electronic Testing: Theory and Applieations,3(4) : December 1992 pp. 377～386． [3] Lee，T．，W．Chuang，In Hajj，Wk FUChs．Circuit - Level Dictionan’es of cMOs Bridging Faults[A]．12th IEEE vLsI Test Symp．，Cherry Hm，NJ，April 1994，pp．386～389． [4] sreejit chakravarty，Paul J Tha djkaran．simulation and Generation of lddq Tests for Bridging Faults in CombinatiOilal Circults [J]．IEEE Transactions on Computers 45(10)：(1996)pp． 1131～1140． [5] Paul Thadikaran，sreejit chakravarty．fast algorithms for computing Iddq tests for cornbinational Circuits[A]．9th Internation．al Conference on VLSI Design，1996 PP．103～106．