边界扫描测试算法的分析与优化

杨迪珂，颜学龙

(桂林电子科技大学 电子工程与自动化学院，广西 桂林 541004)

边界扫描测试算法的分析与优化

杨迪珂，颜学龙

(桂林电子科技大学 电子工程与自动化学院，广西 桂林 541004)

伴随着电子技术和边界扫描测试技术的飞速发展，新的边界扫描测试算法也在不断涌现；而边界扫描测试的算法，一般都是指在互联模型的基础上，边界扫描测试向量的生成算法；生成合理的测试向量集可以以最短的测试时间来覆盖尽可能多的故障；从对一些常用的边界扫描测试算法进行了粗略的分析，到后来对等权值算法和二进制计数算法进行了详细的分析，通过引入和分析边界扫描测试算法的定理、公式以及推论等，分别提出了等权值优化算法和权值递加算法；与优化前的算法作为比较，等权值优化算法降低了征兆混淆出现的概率，而权值递加算法同时降低了征兆误判率和征兆混淆率；综合分析，新的算法更好的权衡了测试向量集的完备性指标和紧凑型指标。

边界扫描；测试算法；测试矢量；优化

0 引言

伴随着高密度、大规模集成电路的迅速发展，传统的测试手段已经很难满足测试的要求[1]，边界扫描技术的出现很大程度上解决了这一技术难题。由于测试时间、故障覆盖率以及故障定位精度的要求, 测试生成算法也存在优化的问题[2]。测试矢量集的大小及其故障覆盖率直接影响测试的时间和效果、故障覆盖率高、诊断准确的测试矢量，一直是算法测试研究的目标和方向[3]。

目前相关的算法很多，各有其优缺点[2]。本文在分析了多个常用测试算法的基础上，提出了等权值算法和二进制计数算法的优化，优化后的算法权衡了紧凑型指标和完备性指标，并降低了故障可能出现的概率，具有一定的实际意义。

1 故障模型介绍

在介绍和分析测试算法之前需要了解电路和系统中可能存在的故障模型，一般电路中可能存在的典型故障模型包括四种：

1.1 固定逻辑故障

也称呆滞故障，表现为电路或系统中某一个或多个网络的不可控制性，即网络的逻辑状态不受输出节点的控制，系统在运行过程中始终固定在“1”或“0”电平上。

1.2 短路故障

也称桥接故障，即两个或多个网络之间的连接造成短路故障。短路故障的原理很简单反而情况很复杂，如果一个电路或系统中发生了短路故障，则很有可能改变整体电路的结构，导致电路或系统的基本功能发生根本性质的变化，所以对电路中短路故障的检测与诊断也变得十分困难和关键。

1.3 时滞故障

电路或系统中信号的动态故障变化，也就是电路中各元件的延时变化，脉冲信号的边沿参数的变化等等。

1.4 暂态故障

暂态故障包括两种类型：瞬态故障和间歇性故障。瞬态故障是由电源干扰和粒子辐射等原因造成的。间歇性故障是由元件参数的变化、温度和湿度等其它外部环境原因等。

由于种类和数目的不同，各种故障模型在实物电路中都是千变万化的。根据有关资料统计，在可能产生的故障中，固定逻辑故障产生的概率占故障总数的90%以上，因此研究针对这两者的测试算法变得非常有必要[4]。

2 一些基本概念

边界扫描测试技术：测试实质上是在芯片管脚和内部逻辑电路之间增加由移位寄存器构成的边界扫描单元，实现对芯片管脚状态的设定和读取，使管脚具有可控性和可观测性[5]。

(1)

(2)

向量的权值(H)：对于向量vi={v1,v2,...}，若向量中第一个为“1”的位为vl，则定义权值：HW(vi)=l[10]。

紧凑型问题：测试向量的个数(P)，也就是测试的时间。完备性问题：测试向量集的故障诊断能力，也就是故障定位的精度以及故障覆盖率等问题。

3 测试算法

边界扫描测试算法也就是测试向量集的生成算法，测试向量集的选择会直接影响边界扫描测试结果的输出，我们把测试向量集检测故障的能力称为故障分辨力[6]。那么怎样判断一个测试算法的故障分辨力？这就需要引入两个概念。

当故障征兆存在时，影响测试向量集对所有故障进行准确定位的原因主要是由于存在两类问题:征兆误判问题和征兆混淆问题，所以征兆误判率γa和征兆混淆率γc是测试故障诊断能力的重要指标。

3.1 测试向量生成算法

最常见的算法是基于STV的测试向量生成算法，一般情况下这一类的算法能够快速发现线路故障，但是出现征兆误判率和征兆混淆率的概率还是比较高。

二进制计数算法(CSA算法)于1974年Kautz在IEEE计算机学报上首次提出，但是存在比较严重的误判和混淆而且无法覆盖开路故障。于是后来在1982年Goel和McMahon提出了改良计数序列算法(MCSA算法)，算法在单一故障模型下更够检测故障，但是也存在一定的误判和混淆问题[8]。

在1987年Wagner提出计数补偿算法，Wagner算法在MCSA算法的基础上增加了互补向量集，提高了定位故障的能力，但是无法避免故障混淆等问题。包括后来提出的走步算法(Walk算法)，算法能够检测所有短路故障和呆滞故障，但明显的缺点是需要大量的测试向量导致测试时间过长，在一些测试中很难直接应用。

3.2 自适应测试算法

自适应测试算法的思想是：首先用快速算法较快发现电路中可能存在的故障；然后追加少量的测试向量集准确判断故障的类型和位置。

One-Step自适应算法由NajmiJarwala和C.W.Yau提出，算法第一步生成一个测试向量集(比如MCSA)，快速发现故障问题，第二步在可能认为被误判的网络上加载“1”，其他网络加载“0”，不过此算法只能检测故障误判，不能检测故障混淆。

W自适应算法同样是由P.Goel和M.T.McMahon提出，第一步与One-Step算法相同，第二步则改为用走步算法在可能出现故障的网络上进行测试。W算法能够检测所以故障误判和混淆，但是算法需要的PTV较大，紧凑型指标不理想。

NajmiJarwala和C.W.Yau等人后来提出C自适应算法。算法对所有可能发生混淆的网络采用走步算法进行测试，而对所有可能发生误判的网络采用One-Step算法进行测试，C算法是对W算法的改进。

4 算法优化

影响算法精度最主要的原因是征兆误判和混淆。根据相关资料的统计，在实际的应用中，误判出现的几率明显大于混淆出现的概率，而且单一故障出现的概率明显大于多故障出现的概率，因此我们的思想是希望能够构造一个紧凑型指标最优并且能够明显减少误判出现的一组测试向量集。

4.1 等权值算法的优化

以MCSA算法为例，征兆误判率和混淆率的计算根据公式(1)和公式(2)，这里可以采用固定的故障模型，利用计算机对所有可能出现的固定逻辑故障进行模拟得出结果。

抗误判定理：测试向量集V不出现征兆误判的充分条件是：存在vi∈V，而且测试向量集V最多只能包含一个不同于vi的向量vj[7]。推论：某个测试向量集不出现征兆误判的充分条件是，测试向量集中的任何一个向量均不能包含另一个向量[7]。

根据抗误判定理的推论，而对于任何布尔向量vi和vj，如果vi被vj所包含，则vi的权值大于vj的权值。那么如果权值q相同的两个向量，它们一定不存在相互包含的关系。由此可以构造一个测试向量集，测试向量集中的向量具有相同的权值，而且他们各不相同，可以选定向量的权值q=p/2。等权值算法测试向量集如下表1所示。MCSA算法和等权值算法的征兆误判率和征兆混淆率如表2所示[4]。

表1 等权值算法的测试向量集(N=10，p=5)

表2 MCSA和等权值算法的误判率和混淆率

等权值算法在一定程度上消除了征兆误判的出现，但是征兆混淆的概率还是比较高，而征兆混淆主要发生在相似的STV之间。根据表1，网络N3、网络N7短路与网络N4、网络N6短路的SRV完全相同(都是11011)，因此不能准确判断到底是N3和N7发生故障还是N4和N6发生故障。为了减少可能出现混淆的概率，可以选择通过牺牲测试向量集的紧凑型来提高它的完备性[7]。

因此可以在STV里面增加不同的补充向量来减少混淆出现的情况。为了尽可能的区分相似的STV和满足向量的紧凑性指标要求，补充向量的个数不能太多，在这里可以将补充的向量个数选定为p/2。测试向量集的权值越小，发生故障混淆的可能性越低[7]。根据此推论可以选择将走步“1”算法作为补充的向量。改进后的等权值算法测试向量集如表2所示，其中n=10，p=7。

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

4.2 二进制计数算法的优化

二进制计数算法(CSA算法)的测试向量集是由从0开始递加的一系列二进制数字序列组成，CSA算法可以检测出线网故障，但是存在过多的相似测试向量集从而导致误判率和混淆率都比较高[6]。算法的优化可以考虑将递加加载到权值上，构成新的权值递加算法，具体方法如下：

一般情况下，征兆误判率和征兆混淆率的发生主要是在相似的测试向量之间，为了避免相似测试向量之间的误判和混淆可以将相似的测试向量进行分组，选择分组个数m=p/2+1(p为二进制计数算法的紧凑性指标)，每个组之间具有相同的权值，第一个组中的所有向量权值都为1，第二个组中的所有向量权值都为2，以此类推。而相同组之间的测试向量集可以根据如下对角独立性原则和相异性概念来确定。

测试向量集的对角独立性原则：矩阵本身经过多次行/列变换后可以得到对角独立矩阵的测试向量集能够检测所有故障。

相异性指标的计算根据上述公式，相异性的概念是指相异性指标越大的测试向量集出现征兆误判和征兆混淆的概率越低。因此所构造的同一组向量之间的向量需尽可能具备对角独立性而且相异性指标尽量够大。

表4 二进制计数算法和权值递加算法的测试向量集

5 算法分析

5.1 等权值优化算法

等权值优化算法的测试向量集如上表3所示，新的算法的紧凑型指标为p+p/2，与等权值算法相比，紧凑型指标虽然提高了，但是也明显低于走步算法。表格5是比较在不同网络数下走步算法、等权值优化算法和等权值算法的紧凑性指标。

表5 三种算法的紧凑型比较

表6 等权值优化算法的征兆误判率和征兆混淆率

表格6是采用固定的故障模型，进行模拟得出的征兆误判率和征兆混淆率。与表2相比较，新的算法继承了等权值算法的低征兆误判率，并在一定程度上降低了征兆混淆率。

5.2 权值递加算法

权值递加算法的测试向量集如上表4所示，算法的紧凑性为p+1，紧凑性略大于二进制计数算法，但明显低于走步“1”算法。算法紧凑性的比较如下表7所示。

表7 三种算法的紧凑型比较

算法征兆误判率和征兆混淆率同如表8所示。根据表8可以看出，与二进制计数算法相比新的算法在一定程度上可避免征兆误判的出现，而且降低了征兆混淆率。

表8 权值递加算法的征兆误判率和征兆率

6 结语

本文首先通过对电路中故障模型和一些基本概念的介绍从而引入边界扫描测试算法。对一些常见的边界扫描算法进行了介绍和分析，并选择了两种常用算法对其进行详细的分析和优化，对比之前的算法，优化后的两种算法更好的权衡了测试向量集的紧凑性指标和完备性指标。

工艺的提升使得集成电路与芯片朝着超微型化、超复杂化的方向发展[11]。随着边界扫描硬件与系统的升级，新的标准和新的算法也在层出不穷的出现，更加优质的的算法将是下一步的研究方向。

[1]ZhangZhaobo，WangZhanglei，GuXinli，etal.Board-levelfaultdiagnosisusinganerror-flowdictionary[A].ProceedingsInternationalTestConference[C]． 2010: 1-10．

[2] 陈圣俭,等.边界扫描测试生成算法优化问题[J].电子测量与仪器学报,2006,20(4):73-76.

[3] 徐 丹，杨新环，晏新晃. 边界扫描测试优化算法[J]. 计算机工程, 2009,35(20):255-257.

[4] 孙媛媛.FPGA的边界扫描测试方法研究[D]. 哈尔滨: 哈尔滨工程大学, 2004.

[5] 徐建洁，李 岳，胡 政.边界扫描测试系统软件设计与实现[J].计算机测量与控制,2006(7):975-977.

[6] 谭剑波, 尤 路, 黄 新,等. 边界扫描测试技术[M].北京：国防工业出版社, 2013.

[7] 刘 静.边界扫描测试算法和BIST技术的研究与实现[D]. 南京: 南京航空航天大学, 2010.

[8]P.Goel,M.T.McMahon.ElectronicChip-in-placeTest[A].ProceedingsInternationalTestConference[C].IEEE.1982:126-137.

[9] 胡 政, 温熙林. 边界扫描测试生成的数学基础[J]. 工程数学基础, 2008,25(2):204-210.

[10] 段军棋. 基于边界扫描的测试算法和BIST设计技术研究[D].成都: 电子科技大学, 2004.

[11] 潘金海,颜学龙.基于1149.7标准的测试生成方法研究[J].计算机测量与控制,2016,24(8):5-8.

Analysis and Optimization of Boundary Scan Test Algorithm

Yang Dike，Yan Xuelong

(School of Electronic Engineering and Automation, Guilin University of Electronic Technology, Guilin 541004, China)

Along with the rapid development of electronic technology and boundary scan test technology, some new boundary scan test algorithms have emerged.The boundary scan test algorithm generally refers to the test vector generation algorithm of boundary scan test technology which is on the basis of the interconnection model. Generate reasonable test vector set can cover the failure as much as possible in the shortest time.Some commonly used test algorithms are analyzed,And then analyzed two kinds of commonly used algorithm: Equal Weight Algorithm and CSA.Through the analysis of boundary scan test algorithm, formula and theorem inference, then proposed two kinds of algorithms:Equal Weight Optimization Algorithm and Weight Increment Algorithm.Compared with the pre-algorithm,the Equal Weight Optimization Algorithm reduces the probability of the appearance of the symptom confusion; and The Weight Increment Algorithm reducing confusion rate and error rate of the symptoms and signs.Generally,the new algorithm improves the completeness and compactness of test vectors.

boundary scan; test algorithm;test vector;optimization

2016-10-31；

2016-12-19。

杨迪珂(1990-)，男，硕士研究生，主要从事可测型设计与测试应用方向的研究。

颜学龙(1964-)，男，硕士研究生导师，教授，主要从事可测性设计与故障诊断、测试信号处理等方向的研究。

1671-4598(2017)05-0004-03DOI：10.16526/j.cnki.11-4762/tp

TP

A