集成电路转换延迟测试向量精简方法

摘要

本发明公开了一种集成电路转换延迟测试向量精简方法，所述算法包括：结构分析算法、故障点可测试影响锥生成算法、基于故障点可测试影响锥的测试向量精简算法，所述影响锥，是指检测某一故障点，所需要确定PPIs和PIs的最小集合，所述结构分析算法，是指通过电路预设门的后继门和门电位计算影响锥，所述故障点可测试影响锥生成算法，是指通过结构分析算法计算故障点影响锥的方法，本发明能够有效精简测试向量的个数，降低集成电路芯片的测试时间，提高测试效率。

权利要求

1.集成电路转换延迟测试向量精简方法，其特征在于，包括以下步骤：步骤1：电路故障点预处理；

步骤1.1：从转换故障点集合中依次提取故障点标记为f，生成故障点f的影响锥，同时从转换故障点集合中删除该故障点f；

步骤1.2：若转换故障点集合非空，提取下一个故障点，重复执行步骤1.1，直至转换故障点集合为空；

步骤2：从转换故障点集合中找出与故障点f有最小重合的一个或者多个故障点，把这些故障点加入到空集合ST中；

步骤3：从集合ST中提取故障点h，判断故障点h的影响锥是否与故障点f的影响锥重合，如果未有重合，故障点h可以被压缩；如果重合，改用故障点可测试影响锥生成算法计算可测试影响锥，如果计算结果未重合，说明故障点h同样可以被压缩，对故障点h进行测试向量压缩；

步骤1所述故障点f的影响锥结构分析算法生成过程如下：执行对电路的结构分析，计算影响锥，影响锥是指电路中设置某一门为特定值，所需要确定PPIs和PIs的最小集合，所述PPIs指第一帧电路和第二帧电路输入端无关联的门，PIs指电路输入门中除去PPIs的门，计算过程如下：步骤1.1.1：从门L为起点开始以门为单位扫描整个集成电路，RCi（PIs）={PIs}，RCi（PPIs）={PPIs}；i是（0，1）的集合，代表逻辑值；

步骤1.1.2：根据门L的类型和故障点类型，分别做如下计算：若L为AND门输出，

RC1(L)=RC1(A)∪RC1(B)

若L为OR门输出，

RC0(L)=RC0(A)∪RC0(B)

若L为XOR门输出，预先定义P1,P2,P3,P4公式如下，单个值没有真实意义，P1=|RC1(A)∪RC0(B)|P2=|RC1(B)∪RC0(A)|

P3=|RC1(A)∪RC1(B)|

P4=|RC0(A)∪RC0(B)|

若L为扇出源，分支为：B1,B2,B3,…,Bk，RCi(Bj)=RCi(L)；

所述Bj表示扇出源的扇出分支门，j表示扇出门的编号{1,2,3…,k}；

本步骤中所述RCi(X)指X门输出置为i，即所需要确定PPIs和PIs的最小集合；

步骤1.1.3：重复步骤1.1.2，直到出现PPIs或PIs终止，记录所需要确定PPIs和PIs的最小集合。

2.根据权利要求1所述测试向量精简方法，其特征在于，所述步骤2首先从记录的故障点影响锥中，相应提取转换故障点集合中最小影响锥对应的故障点，然后再对剩余的故障点遍历，寻找出与故障点f有最小重合的一个或者多个故障点。

3.根据权利要求1所述测试向量精简方法，其特征在于，所述步骤2及步骤3中判断重合的方法如下：步骤4.1：计算集合中除提取故障点外，其他故障点的影响锥；

步骤4.2：依据当前故障点可测试影响锥为比较基准，逐次提取其他故障点可测试影响锥，对比可测试影响锥占用的PPIs和PIs是否有重合；

步骤4.3：执行步骤4.2，直至集合中所有故障点可测试影响锥均与当前故障点可测试影响锥相比较一次。

4.根据权利要求1所述测试向量精简方法，其特征在于，所述步骤3中用故障点可测试影响锥生成算法计算的步骤如下：步骤3.1：对于测试向量能够检测到的故障点f，依据步骤1.1.1至步骤1.1.3的方法模拟针对第一帧电路找出检测故障需要确定的输入门集合RCj(f)，j是（0，1）的集合，代表故障点的故障类型；

步骤3.2：针对第二帧电路，依据步骤1.1.1至步骤1.1.3的方法模拟找出检测故障需要确定的输入集合RCj(f)，第二帧的j取第一帧相反的值计算步骤3.3：第二帧电路模拟出把门L故障成功传出电路到达输出端时，在输入端需要被置为确定点位所要用到的最少的PPIs和PIs端口集合，标记为RO(f)，计算RCj(f)、和RO(f)的并集，得到转换测试向量det（f）。

5.根据权利要求1所述测试向量精简方法，其特征在于，所述步骤3中用故障点影响锥生成算法计算过程中会出现相同门电位值逻辑冲突情况或者影响锥冲突情况，出现这两种情况时，压缩进程停止，在集合ST取下一个故障点尝试压缩。

说明书

集成电路转换延迟测试向量精简方法

技术领域

[0001] 本发明涉及数字集成电路测试技术领域，特别涉及集成电路测试中的转换延迟测试向量领域，具体涉及一种集成电路转换延迟测试向量精简方法。

[0002] 背景技术

[0003] 在数字电路测试领域，主要有两种的故障模型：跳变故障模型和延迟故障模型。目前集成电路芯片向着高集成度和小尺寸化发展，延迟故障发生概率变大，针对延迟故障的测试算法越来越显得重要，延迟故障模型测试的特点在于产生的测试向量远远大于跳变故障模型，这对测试向量精简算法提出了较高的要求，转换延迟故障是指故障门在跳变过程中产生延迟故障，针对电路的延迟故障目前很多方法被提出，但大部分对时间开销、故障覆盖率、压缩效率三者没有达到较好的平衡，即以损失其中一种或二种指标，达到对其余指标的优化，因此，很有必要提出一种新的算法。

[0004] M.Yilmaz等人提出一个覆盖所有门的最长路径延迟故障测试生成算法，W.Qiu等人提出寻找前K长覆盖所有门的可测路径的算法，但是这些路径的方法普遍存在效率低或者准确度不高，不能有效识别最长路径。Hamzaoglu等人提出基于广播的方式主要通过将一个扫描输入同时送入多个扫描链来实现该方法利用不同触发器的逻辑值没有冲突的属性，如果两个触发器在任何一个测试向量中的值都没有冲突，那么用一个逻辑值来表示他们对测试过程是没有影响的。该方法产生测试向量的时候可以与ATPG整合在一起，相当于在ATPG的时候增加约束。

发明内容

[0005] 为了克服上述现有技术的不足，本发明的目的在于提供了一种集成电路转换延迟测试向量精简方法，其能够减少测试向量的数量，同时能够实现测试向量的高效率压缩，降低集成电路芯片的测试时间，提高测试效率。

[0006] 为了实现上述目的，本发明采用的技术方案是：

[0007] 集成电路转换延迟测试向量精简方法，包括以下步骤：

[0008] 步骤1：电路故障点预处理；

[0009] 步骤1.1：从转换故障点集合中依次提取故障点标记为f，生成故障点f的影响锥，同时从转换故障点集合中删除该故障点f；

[0010] 步骤1.2：若转换故障点集合非空，提取下一个故障点，重复执行步骤1.1，直至转换故障点集合为空；

[0011] 步骤2：从转换故障点集合中找出与故障点f有最小重合的一个或者多个故障点，把这些故障点加入到空集合ST中；

[0012] 步骤3：从集合ST中提取故障点h，判断故障点h的影响锥是否与故障点f的影响锥重合，如果未有重合，故障点h可以被压缩；如果重合，改用故障点可测试影响锥生成算法计算可测试影响锥，如果计算结果未重合，说明故障点h同样可以被压缩，对故障点h进行测试向量压缩。

[0013] 其中，步骤1所述故障点f的影响锥结构分析算法生成过程如下：

[0014] 执行对电路的结构分析，计算影响锥，影响锥是指电路中设置某一门为特定值，所需要确定PPIs和PIs的最小集合，所述PPIs指第一帧电路和第二帧电路输入端无关联的门，PIs指电路输入门中除去PPIs的门，计算过程如下：

[0015] 步骤1.1.1：从门L为起点开始以门为单位扫描整个集成电路，RCi(PI)＝{PI}，RCi(PPI)＝{PPI}；i是(0，1)的集合，代表逻辑值；

[0016] 步骤1.1.2：根据门L的类型和故障点类型，分别做如下计算：

[0017] 若L为AND门输出，

[0018] RC1(L)＝RC1(A)∪RC1(B)

[0019]

[0020] 若L为OR门输出，

[0021] RC0(L)＝RC0(A)∪RC0(B)

[0022]

[0023] 若L为XOR门输出，预先定义P1，P2，P3，P4公式如下，单个值没有真实意义，[0024] P1＝|RC1(A)∪RC0(B)|

[0025] P2＝|RC1(B)∪RC0(A)|

[0026] P3＝|RC1(A)∪RC1(B)|

[0027] P4＝|RC0(A)∪RC0(B)|

[0028]

[0029]

[0030] 若L为扇出源，分支为：B1，B2，B3，...，Bk，RCi(Bj)＝RCi(L)；

[0031] 所述Bj表示扇出源的扇出分支门，j表示扇出门的编号{1，2，3...，k}；

[0032] 本步骤中所述RCi(X)指X门输出置为i，即所需要确定PPIs和PIs的最小集合；

[0033] 步骤1.1.3：重复步骤1.1.2，直到出现PPIs或PIs终止，记录所需要确定PPIs和PIs的最小集合。

[0034] 所述步骤2首先从记录的故障点影响锥中，相应提取转换故障点集合中最小影响锥对应的故障点，然后再对剩余的故障点遍历，寻找出与故障点f有最小重合的一个或者多个故障点。

[0035] 所述步骤2及步骤3中判断重合的方法如下：

[0036] 步骤4.1：计算集合中除提取故障点外，其他故障点的影响锥；

[0037] 步骤4.2：依据当前故障点可测试影响锥为比较基准，逐次提取其他故障点可测试影响锥，对比可测试影响锥占用的PPIs和PIs是否有重合；

[0038] 步骤4.3：执行步骤4.2，直至集合中所有故障点可测试影响锥均与当前故障点可测试影响锥相比较一次。

[0039] 所述步骤3中用故障点可测试影响锥生成算法计算的步骤如下：

[0040] 步骤3.1：对于测试向量能够检测到的故障点f，依据步骤1.1.1至步骤1.1.3的方法模拟针对第一帧电路找出检测故障需要确定的输入门集合RCj(f)，j是(0，1)的集合，代表故障点的故障类型；

[0041] 步骤3.2：针对第二帧电路，依据步骤1.1.1至步骤1.1.3的方法模拟找出检测故障需要确定的输入集合RCj(f)，第二帧的j取第一帧相反的值计算

[0042] 步骤3.3：第二帧电路模拟出把门L故障成功传出电路到达输出端时，在输入端需要被置为确定点位所要用到的最少的PPI和PI端口集合，标记为RO(f)，计算RCj(f)、和RO(f)的并集，得到转换测试向量det(f)。

[0043] 所述步骤3.3中，RO(f)计算的步骤如下：

[0044] 步骤3.3.1：检测f门的类型，如果是PO或PPO端口，RO(f)＝φ

[0045] 步骤3.3.2：根据门f的类型和故障点类型，分别做如下计算：

[0046] 若f为AND门输出，A，B为输入

[0047] RO(A)＝RO(f)∪RO1(B)

[0048] 若f为OR门输出，A，B为输入

[0049] RO(A)＝RO(f)∪RO0(B)

[0050] 若f为扇出源，分支为：B1，B2，B3，...，Bk，RO(f)＝RO(Bi)；

[0051] 所述Bj表示扇出源的扇出分支门，j表示扇出门的编号{1，2，3...，k}；

[0052] 步骤3.3.3：重复步骤3.3.2，直到出现PPIs或PIs终止，记录所需要确定PPIs和PIs的最小集合。

[0053] 所述步骤3中用故障点可测试影响锥生成算法计算过程中会出现相同门电位值逻辑冲突情况或者影响锥冲突情况，出现这两种情况时，压缩进程停止，在集合ST取下一个故障点尝试压缩。

[0054] 所述步骤3中测试向量压缩的过程分为四种情况，按顺序依次尝试压缩：

[0055] 情况1：如果T∩IC(f′)为空，产生已成功压缩的故障点f′的测试向量，并压缩在测试向量T中，生成新的测试向量仍表示为T，持续这一过程直至在集合ST中找出所有此类型的故障点；

[0056] 情况2，如集合ST为空跳出此步骤，若非空，在集合ST中选择剩余的故障点，依据影响锥产生检测算法，生成故障点f′的det(f′)，若T∩det(f′)为空，产生故障点f′的测试向量，并压缩在测试向量T中，生成新的测试向量仍表示为T，持续这一过程直至集合ST中找出所有此类型的故障点，其中det(f′)为对f′产生影响的最少PPIS和PIS端口集合；

[0057] 情况3，如集合ST为空跳出此步骤，若非空，在集合ST中选择剩余的故障点，根据det(f′)与测试向量T重合端口数量由少到多的顺序，针对每个故障点f′，用公式det(f′)∩T，计算重合的输入端口，表示为In，若In对应端口值和测试向量T相应端口值全部相同，产生故障点f′的测试向量，并压缩在测试向量T中，生成新的测试向量仍表示为T，持续这一过程直至在集合ST中找出所有此类型的故障点；

[0058] 情况4，如集合ST为空跳出此步骤，若非空，在集合ST中选择剩余的故障点，根据det(f′)与测试向量T重合端口数量由少到多的顺序，针对每个故障点f′，用公式det(f′)∩T，计算重合的输入端口，表示为In，产生故障点f′的测试向量，更新测试向量T′＝det(f′)∪T，测试新的T′测试向量，是否可以成功检测故障点f′，若成功，更新T为T′，否则保持测试向量T不变，遍历集合ST；

[0059] 以上所述的测试向量T定义是：在转换故障点集合中选取具有最小输入影响集合的故障点，标记为f，并从集合中删去该故障点，产生此故障点的测试码对标记为T。

[0060] 与现有技术相比，本发明以电路结构分析和故障点可测试影响锥计算为基础，设计的故障模型测试向量精简算法，减少了向量生成时间，在保持故障率不变的前提下，提高了ATPG效率。

附图说明

[0061] 图1为本发明实施例中所述时序集成电路示意图。

[0062] 图2为本发明实施例中所述对集成电路进行测试压缩方法示意图。

具体实施方式

[0063] 下面结合附图和实施例对本发明做进一步详细说明。

[0064] 本发明中主要涉及结构分析算法、故障点可测试影响锥生成算法、基于故障点可测试影响锥的测试向量精简算法，下面将分别介绍各种算法的过程。

[0065] 1.结构分析算法，执行对电路的结构分析，计算影响锥，影响锥是指电路中设置某一门为特定值，所需要确定PPIs和PIs的最小集合，所述PPIs指第一帧电路和第二帧电路输入端无关联的门，PIs指电路输入门中除去PPIs的门，计算过程如下：

[0066] 步骤(1)：从门L为起点开始以门为单位扫描整个电路，并记录每个门的后继门和该门的类型；

[0067] 步骤(2)：针对每个门，在扫描之后会形成后继门，通过查询该表可以很快找到该门的后继门；

[0068] 步骤(3)：考虑门L的类型和故障点类型，分情况执行步骤(4)至步骤(7)，所述仅列出部分典型情况，其他未述情况可依规则推导，直至表中无后继门；

[0069] 步骤(4)：若L为AND门输入，

[0070] RC1(L)＝RC1(A)∪RC1(B)

[0071]

[0072] 所述RCi(X)指X门输出置为i，即所需要确定PPIs和PIs的最小集合。

[0073] 步骤(5)：若L为OR门输入，

[0074] RC0(L)＝RC0(A)∪RC0(B)

[0075]

[0076] 步骤(6)：若L为XOR门输入，为方便理解公式，预先定义P1，P2，P3，P4，单个值没有真实意义

[0077] P1＝|RC1(A)∪RC0(B)|

[0078] P2＝|RC1(B)∪RC0(A)|

[0079] P3＝|RC1(A)∪RC1(B)|

[0080] P4＝|RC0(A)∪RC0(B)|

[0081]

[0082]

[0083] 步骤(7)若L为扇出源，分支为：B1，B2，B3，...，Bk，RCi(Bj)＝RCi(L)；

[0084] 所述Bj表示扇出源的扇出分支门，j表示扇出门的编号{1，2，3...，k}；

[0085] 步骤(8)：重复步骤(4)，直到出现PPIs或PIs终止，记录所需要确定PPIs和PIs的最小集合，上述步骤中所述RCi(X)指X门输出置为i，即所需要确定PPIs和PIs的最小集合。

[0086] 2.故障点测试向量生成算法，通过门电位方式计算故障点可测试影响锥，其产生过程如下：

[0087] 步骤(1)：对于测试向量能够检测到的故障f，依据上述结构分析算法模拟针对第一帧电路找出检测故障需要确定的输入集合RCj(f)，j是(0，1)的集合，代表故障点的故障类型；

[0088] 步骤(2)：针对第二帧电路，依据结构分析算法模拟找出检测故障需要确定的输入集合RCj(f)，注意第二帧的j取第一帧相反的值计算

[0089] 步骤(3)：第二帧电路模拟出把门L故障成功传出电路到达输出端时，在输入端需要被置为确定点位所要用到的最少的PPI和PI端口集合，标记为RO(f)，计算RCj(f)、和RO(f)的并集，得到转换测试向量det(f)。

[0090] 3.基于故障点可测试影响锥的测试向量精简算法

[0091] 步骤(1)：如果转换故障点集合为非空时，依次执行步骤(2)至步骤(7)[0092] 步骤(2)：依据基于影响锥的故障点产生生成算法，在故障点集合中选取具有最小输入影响集合的故障点，标记为f，产生此故障点的测试向量标记为T，并从集合中删去该故障点

[0093] 步骤(3)：对转换故障点集合中剩余的故障点遍历，寻找出与f故障点有最小重合的一个或者多个故障点，把这些故障点加入到空集合ST中

[0094] ST集合中数据的个数是基于高压缩率和CPU消耗时间权衡得出，如果希望得到高质量的压缩效果，ST集合中数据的选择条件应该设定较为宽松，尽量收集更多的数据，增加了压缩成功率，理论分析可知，追求高压缩率必然以损失CPU时间为代价，因为在不停的尝试测试码向量是否可以被压缩的过程，测试时间将不断增加，反之亦成立。

[0095] 步骤(4)：测试压缩过程，基于步骤(3)的实现对属于ST集合中的故障点进行测试向量压缩，故障点f′压缩过程分为四种情况，按顺序依次尝试压缩；

[0096] 步骤(5)：如果T∩IC(f′)为空，产生已成功压缩的故障点f′的测试向量，并压缩在测试向量T中，生成新的测试向量仍表示为T，持续这一过程直至在集合ST中找出所有此类型的故障点；

[0097] 步骤(6)：如ST为空跳出此步骤，若非空，在ST集合中选择剩余的故障点，依据影响锥产生检测算法，生成故障点f′的det(f′)，若T∩det(f′)为空，产生故障点f′的测试向量，并压缩在测试向量T中，生成新的测试向量仍表示为T，持续这一过程直至在集合ST中找出所有此类型的故障点，其中det(f′)为对f′产生影响的最少PPIS和PIS端口集合；

[0098] 步骤(7)：如集合ST为空跳出此步骤，若非空，在集合ST中选择剩余的故障点，根据det(f′)与测试向量T重合端口数量由少到多的顺序，针对每个故障点f′，用公式det(f′)∩T，计算重合的输入端口，表示为In，若In对应端口值和测试向量T相应端口值全部相同，产生故障点f′的测试向量，并压缩在测试向量T中，生成新的测试向量仍表示为T，持续这一过程直至在集合ST中找出所有此类型的故障点；

[0099] 步骤(8)：如集合ST为空跳出此步骤，若非空，在集合ST中选择剩余的故障点，根据det(f′)与测试向量T重合端口数量由少到多的顺序，针对每个故障点f′，用公式det(f′)∩T，计算重合的输入端口，表示为In，产生故障点f′的测试向量，更新测试向量T′＝det(f′)∪T，测试新的T′测试向量，是否可以成功检测故障点f′，若成功，更新T为T′，否则保持测试向量T不变，遍历集合ST；

[0100] 步骤(9)：保存测试向量T的值，若转换故障点集合非空，继续步骤(2)，否则结束压缩。

[0101] 在本发明的测试向量精简算法之前，先要对电路进行预处理，电路预处理主要是用可测试影响锥生成算法计算所有故障点的可测试影响锥，包含以下步骤：

[0102] (a)从转换故障点集合中依次提取故障点标记f，基于可测试影响锥的故障点产生生成算法，生成故障点f的可测试影响锥。如图1所示，成功产生故障点f的可测试影响锥的基础在于，f本身是可测的故障点，即在图示中，需要满足区域R1和R2在输入端全部的PPIs和PPI没有重合，另外还要满足路径回溯的过程中相同门的电位没有冲突。第一帧电路中，与门L是单固定1型故障点，如果|RC0(A)|≤|RC0(B)|，|RC0(L)|＝|RC0(A)|，若|RC0(A)|＞|RC0(B)|，|RC0(L)|＝|RC0(B)|，因此计算L门的影响锥，等同于计算A门或者B门的影响锥，依次类推，按故障点类型和门类型的不同，选择合适的结构分析算法计算公式，计算出第一帧电路的RC0(L)。

[0103] 在第二帧电路中，对故障点f′和RO(f)的计算也是类似，在算法执行过程中，遇到门电位冲突的情况将停止运行，表明该故障点不可检测，从转换故障点集合中依次提取下一个故障点，执行步骤(a)。

[0104] (b)记录f的影响锥到一个表格F中，若转换故障点集合非空，提取下一个故障点，重复执行步骤(a)，若转换故障点集合为空，结束电路预处理过程。

[0105] 测试向量精简算法过程示意图如图2所示，对记录可测故障点可测试影响锥的表格F中，提取最小可测试影响锥的故障点，第一个故障点的提取对算法的压缩效率十分关键，最小影响锥可以相对减少不可压缩概率，保证测试向量得到最大限度的压缩，下一步对转换故障点集合中剩余的故障点遍历，寻找出与f故障点有最小重合的一个或者多个故障点，把这些故障点加入到集合ST中，ST集合中数据的个数是基于高压缩率和CPU消耗时间权衡得出，如果希望得到高质量的压缩效果，ST集合中数据的选择条件应该设定较为宽松，尽量收集更多的数据，增加了压缩成功率，理论分析可知，追求高压缩率必然以损失CPU时间为代价，因为在不停的尝试测试码向量是否可以被压缩的过程，测试时间将不断增加，反之亦成立。

[0106] 集合ST中提取故障点，用结构分析算法是否和对比故障点影响锥重合，如果未有重合，该故障点可以被压缩，如果计算结果重合，改用故障点可测试影响锥生成算法计算，如果此次计算结果未重合，说明该故障点同样可以被压缩，计算过程中会出现两类情况：1.相同门电位值逻辑冲突。2.影响锥冲突。出现这两种情况时，压缩进程停止，在集合ST取下一个故障点尝试压缩。

[0107] 采用了本发明的实验：实验平台为Dell precision 690工作站。下表中给出了将本发明应用到ISCAS89和IWLS2005电路的实验结果。

[0108]

[0109] Circuit表示电路类型，faults表示故障点数目，no compaction部分数据表示未压缩前的指标，selfish表示压缩后的指标，FC表示故障覆盖率，vec表示测试向量数，CPU表示测试向量产生耗费的时间。可以看出，采用本发明可以有效的精简测试向量的个数，并有较短的测试向量产生时间。

[0110] 以上实施方式仅用于说明本发明，而并非对本发明的限制，有关技术领域的普通技术人员，在不脱离本发明的精神和范围的情况下，还可以做出各种变化和变型，因此所有等同的技术方案也属于本发明的范畴，本发明的专利保护范围应由权利要求限定。