一种基于互连测试的综合优化算法∗

吴 中 邱卫东 林 明

（1.江苏科技大学电子信息学院 镇江 212000）（2.南理工港世顺有限公司 南京 210000）

1 引言

边界扫描技术是对以往测试技术的一种革新，不需要将器件每个管脚连接到测试设备，只需通过JTAG 端口，发送内部传输数据经过输入输出的比较即可实现对各引脚的测试。解决了其他技术难以解决的问题。而互连测试作为其重要的一环，主要对板级网络互连进行分析，测试覆盖率，测试时间以及故障诊断定位等作为衡量测试优劣指标都需要进行不断优化，寻求较优的测试算法一直是该技术的研究重点。以往大多算法在研究过程中均默认只存在W-O 短路故障，而并不考虑W-A 短路，这也使得该测试技术在这一方面研究较为薄弱，并存在较大的局限性。本文通过边界扫描技术的测试指标对当前相关算法进行有效分析，意图找出能综合考虑此两种短路故障，且紧凑性良好的算法。

2 相关概念和故障模型

2.1 相关概念

1）网络：网络是由通过导线连接的一系列输入、输出节点构成的，记为ni，i=1，2，…，N。

2）串行测试向量（STV）：多次测试循环加载到同一网络的测试矢量，记作VQi，i=1，2，…，N。

3）并行测试向量（PTV）：一次测试循环加载到不同网络的测试矢量，记作Vpj，j=1，2，…，P。

4）测试矩阵（T）：由所有PTV 为列向量组成的布尔矩阵。

5）紧凑性指标：扫描测试的时间决定于测试循环的次数［1］，即PTV 的个数或STV 的维数，用P 表示。

2.2 故障模型

常讨论的故障模型包括固定故障与桥接故障［2］。固定故障包括滞0 故障（S-A-0）和滞1 故障（S-A-1），解释为与地或电源短路。桥接故障包括W-O和W-A短路，如下式：

征兆误判：当测试向量存在STVi同某类桥接故障征兆相同时，无法确定该测试向量所在的网络是否也与故障网络短路。

征兆混淆：当故障征兆S1f与S2f矢量相同时，无法确认S1f与S2f所在网络之间是否短路。

3 当前较优算法的描述分析

算法的优劣主要通过两个指标来进行判定，即紧凑性指标，误判征兆与混淆征兆的检查能力［3］。

从紧凑性方面来看，目前MCSA 算法紧凑性最好，P=log（N+2），但是其对故障网络的检测效果比较差［4］。从完备性来看，走步算法是最完备的算法，然而其紧凑性为N，测试时间过长。综合考虑，当前等权值算法是比较理想的，其生成测试向量STV 最大数为C（P，q），其中q=P/2。当测试N 个网络时，P 需满足C（P，q）≥N，很明显，当网络很多时，P 远小于N。另外等权值算法是一个抗误判的算法，能做到零误判，且一定程度下降低混淆率。因此在等权值算法的基础上进行算法优化，具有一定实用意义。

文献［5］提出了一种紧凑性指标最小的抗误判算法，该算法即是基于等权值算法，通过递归得到的。

该算法能消除W-O 短路故障的误判，不能消除W-A 故障的误判［5］。在紧凑性方面，该文提出的最小紧凑性具有一定局限性，设该算法紧凑性指标为P，则P=n，通过数学推理证明P 需满足，这说明只在网络数较小的情况下，紧凑性低于等权值算法。如当网络数为100 时，等权值算法紧凑性为9，而紧凑性最小算法指标为15，明显大于等权值算法。

文献［6｝中作者介绍了一种较优的W-A 短路故障抗误判算法，与文献［4］一样是通过递归得到的，是目前较少数对线与短路研究分析的算法，能完全消除W-A 短路故障误判，却不能消除W-O 短路故障的误判［6］。

文献［7］提出了一种等权值算法的优化，在STV 矢量后附加了P/2 个走步算法［7］，牺牲了部分紧凑性指标，但有效地降低了混淆率。如表1，当网络数为12 时，等权值算法和优化的等权值算法的测试向量集。和目前大部分算法一样，该算法只考虑了线或短路，而对线与短路情况不作判断。

表1 等权值算法和优化的等权值算法测试向量集

4 算法的综合优化

基于以上分析，本文提出了一种综合考虑线或、线与短路故障的优化算法。算法的主要思路是基于等权值算法的两重优化，由于等权值算法能检测固定故障，且是零误判的［8］，所以这里只需考虑混淆率和紧凑性。首先针对等权值算法，当紧凑性相同时，将权值适当降低，来降低故障率；另外针对线或短路和线与短路，按照走位1 算法在等权值算法STV 矢量后先加载P/2 个矢量，再按走位0 算法施加P/2个矢量。

4.1 等权值算法的优化

在很多情况下，当网络数量一定时，通过等权值算法产生测试矢量，我们发现，权值可以适当的小于|P/2|（这里定义|P/2|≤P/2，且为整数），这种测试矢量也能满足要求。如当网络为N=12 时，P=6，此时权值一般默认为P/2=3，但实际上权值为2 也是可行的。

表2 网络N=12时，两种算法的测试矢量

采用固定故障模型，对两种算法进行模拟仿真，得出表3结果。

表3 等权值算法和降权值的等权值算法权值与混淆率

由表3 可知，降权值的等权值算法在一定程度下降低了故障混淆率，此外从表中也可以看出在某些情况，即当时，权值是不可降低的，如N=16时，两算法权值均为3。

降权值等权值算法实现流程如下：

图1 降低权值的等权值算法实现流程（其中q为权值）

4.2 综合考虑的优化算法

在4.1 节中降低权值的优化算法，其故障率还是比较高。为了继续降低可能出现混淆的概率，按照文献［4］的思路，考虑到走步1与走步0算法原理相同，且是分别针对线或和线与故障的完备算法［9］，在降权值的等权值算法STV后附加|P/2|个走步1算法向量，再附加|P/2|个走步0 算法向量。网络数为12 时，综合考虑的优化算法产生的测试向量集如表4所示。

表4 N=12时，综合考虑的优化算法测试向量集

4.2.1 故障混淆率分析

综合考虑的优化算法同时考虑两种短路混淆故障，依次附加了一定的走步1 和走步0 算法。一方面，附加向量的出现会大幅度降低整体故障率；而另一方面由于附加走步算法向量长度明显小于网络数N，则必然会循环性地施加相同向量，这会降低STV 后面走步算法对混淆故障的检测。表5为等权值算法，文献［6］中优化的等权值算法以及综合优化的等权值算法的混淆率。

表5 三种算法的混淆率比较

由表5 可知，综合优化的等权值算法虽不能做到完全排除混淆故障，但相比较其他算法，也是大幅度地降低了混淆率，而且当网络数越大，抗混淆能力越强。

4.2.2 紧凑性分析

综合优化算法的紧凑性指标为P+2|P/2|，当P为偶数时，指标为2P；P 为奇数时，指标为2P-1。表6为几种算法紧凑性的比较。

表6 不同算法紧凑性指标比较

表6 显示的紧凑性指标，尽管综合优化的等权值算法相比较等权值算法较大，大约为其两倍，为优化的等权值算法的1.5 倍，但是和走步算法相比是非常小的。

5 结语

本文在等权值研究的基础上，相比较传统算法而言，将W-O 短路和W-A 短路同时纳入进去，提出了综合考虑的优化降权值算法，从紧凑性以及混淆率分别进行分析并折衷考虑，得出该算法是一种非常实用的算法。