理论计算机科学电子笔记174（2007）83-93www.elsevier.com/locate/entcs功能测试生成在同步时序电路Irith Pomeranz伊里斯·波梅兰兹1，2普渡大学美国印第安纳州西拉斐特，邮编47907苏达卡湾Reddy雷迪3，4爱荷华大学美国爱荷华州爱荷华市52242摘要我们研究了门级故障模型的诊断测试生成，这是用于生成诊断测试集的制造缺陷，和功能测试生成的高层次故障模型之间的关系。一般来说，功能性故障可能部分地代表一个门级故障的某些后果，而不是另一个。然后，生成用于功能故障的测试序列可能检测到一个门级故障而不是另一个门级故障，从而区分这两个故障。 这种关系指向使用功能测试生成过程（以功能故障检测为目标）作为生成门级故障的诊断测试序列的方式的能力。 我们以两种方式使用这种观察。 更直接的方法是定义对应于门级故障对之间的差异的功能故障。 第二种方法是使用功能测试序列作为诊断测试序列，而不显式地考虑门级故障。我们支持使用由此产生的程序与实验结果。关键词：诊断测试产生，功能测试产生，状态转移故障，同步时序电路。1介绍诊断测试生成过程[1]-[7]生成测试集或测试序列，用于区分目标故障模型中的故障对，通常是固定故障。1研究部分由SRC资助编号2005-TJ-12822电子邮件：pomeranz@ecn.purdue.edu3部分由SRC资助的研究编号：2005-TJ-12434电子邮件：reddy@engineering.uiowa.edu1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2006.12.03184I. Pomeranz，S.M.Reddy/Electronic Notes in Theoretical Computer Science 174（2007）83zL这样的测试集对于诊断制造缺陷是有用的，即使缺陷不完全表现为目标故障。诊断测试生成过程基于尚未被测试集区分的故障对（或更大的故障子集）执行测试生成。它们的目标是生成额外的测试或测试序列（或扩展现有的测试序列），以便区分尚未区分的额外故障对。考虑故障对的需要使得诊断测试生成过程与用于故障检测的测试生成过程不同，并且比用于故障检测的测试生成过程更复杂。测试生成过程可以显式地容纳故障对，或者通过修改电路描述来分别注入每一个故障[6]。在后一种情况下，可以在修改后的电路上进行故障检测的测试生成，并且测试保证将区分两个故障。然而，需要针对每个故障对分别修改电路。在这项工作中，我们研究了门级故障的诊断测试生成和高级别故障的功能测试生成之间的关系。这种关系指向使用功能测试生成过程（其以功能故障检测为目标）作为在不修改电路的情况下生成用于同步时序电路中的门级故障的诊断测试序列的方式存在几种功能测试生成程序和故障模型[8]-[15]。我们在这项研究中考虑的状态转换故障是在电路的状态表中中断下一个状态或状态转换的输出向量的故障。可以以类似的方式使用其他功能故障模型。我们考虑单一固定故障作为诊断测试生成的目标从下面的例子中可以看出使用状态转换故障（或一般的高级故障）进行诊断测试生成的优点考虑一个状态转换器，它是由一个静态输入向量和一个预处理输入向量组成的，提供了主输出向量z1。假设固定型故障fj1将该状态转换的下一个状态改变为SJk，而固定型故障fj2不改变该状态转换。考虑一个检测状态转换故障的测试序列T，其中下一个状态是sJk而不是sk。由于f j1引起与状态转换故障相同的电路状态表变化，因此T很可能检测到f j1。由于fj2不会引起状态表的这种变化，因此它不太可能被T检测到。 如果T检测到fj1而不是fj2，则T区分这两个故障。一般来说，功能性故障可能部分地代表一个固定故障的某些后果，而不是另一个。然后，生成功能故障的测试序列可能检测到一个固定故障而不是另一个，从而区分这两个故障。这一观察可以用两种方式之一，这两种方式都在这项工作中进行了探索。(1) 使用这种观察的更直接的方法是定义对应于固定故障对（或固定故障的子集）之间的差异的通过将代表两个（或更多个）固定故障之间的差异的功能故障作为目标，测试序列可能检测到一对故障中的一个故障而不是另一个故障，从而区分两个故障。两者之间的差异I. Pomeranz，S.M.Reddy/Electronic Notes in Theoretical Computer Science 174（2007）8385固定故障是状态转换的子集，其中两个固定故障如下所述那样不同。我们注意到，每个固定故障f等效于单个或多个状态转换故障（即，以一种或多种方式影响一个或多个状态转换的故障）。 我们用ST（f）表示与f等价的状态转移故障。 ST（f）由一个或多个单状态转换故障组成，这些故障是由荷兰盾状态之间的微分方程ST（fj1）−ST（fj2）和ST（fj2）−ST（fj1）对应于两个固定故障Fj1和Fj2的转换故障也构成单个或多个状态转换故障。故障被认为是在诊断测试生成过程中使用功能测试生成程序。我们首先考虑（多重）故障ST（f j1）− ST（f j2）和ST（f j2）− ST（fj1）。Thenn，if|ST（fj1）−ST（fj2）|>1时，我们可以在ST（fj1）-ST（fj2）中定义一个相同的静态结构。如果你愿意，|ST（fj2）−ST（fj1）|>1时，我们分别考虑ST（fj2）-ST（fj1）中包含的每个单状态转移故障。(2) 通过扩展，检测电路中的所有单状态转换故障或作为固定故障的组件的所有单状态转换故障的功能测试序列可能用作诊断测试序列。诊断测试生成问题的这种观点允许在不考虑门级实现的情况下生成诊断测试序列它还支持使用功能测试序列进行缺陷诊断。在第2节中，我们描述了使用单个或多个状态转换故障来表示固定故障。在第3节中，我们描述了在诊断测试生成过程中要针对的状态转换故障的推导，并且我们描述了基于状态转换故障的功能测试生成的诊断测试生成过程。诊断测试生成的实验结果在第4节中给出第5节给出了使用功能测试序列对单状态转换故障进行测试的结果。2用状态转移故障为了证明固定故障具有等效的状态转换故障，我们在表1中显示了有限状态机基准序列4的状态表。状态表是从门级实现中获得的。该电路有两个状态变量和四个状态，状态向量为00、01、10和11。 它有两个主要输入，四个输入向量a= 00，01，10和11，以及一个主要输出，输出向量z= 0和1。PS代表当前状态，NS代表下一个状态。在表2中，我们示出了在电路的状态表上的列4的门级实现中的三个固定故障f0、f2和f12的影响对于每个固定故障fj，我们在每个当前状态s∈ {00，01，10，11}下模拟电路，主输入向量a∈ {00，01，10，11}。如果故障的下一个状态或输出向量分别与无故障下一状态或输出向量不同，我们包括86I. Pomeranz，S.M.Reddy/Electronic Notes in Theoretical Computer Science 174（2007）831/0表14列状态表NS，zPSa= 00a= 01a= 10a= 110000,010,110,111,10100,001,101,111,11011,110,110,111,11111,101,101,111,1状态表中斜线后面的错误条目。 例如，列车4的固定故障f0导致输入向量10下的状态00的下一个状态为00而不是10，并且它导致输出为0而不是1。我们代表这个有缺陷的国家转换为0010 10/ 00。它由单状态转换故障0010 10/ 00组成0010 101/ 0 1表24列固定故障f0PSa= 00NS，za= 01a = 10a= 110000,010，1 10/00，1/011/10,10100,001/00，1/011/01,11011,110.1 10/11.111/10,11111,101.1 01/11.111/01,1F2NS，zPSa= 00a= 01a = 10a= 110000,010/00，1/0 10，111/10,10100,001/00，1/0 01，111/01,11011,110/11，1 10，111/10,11111,101/11.1 01.111/01,1F12NS，zPSa= 00a= 01a= 10a= 110000,010,110,111/10,10100,001,101,111/01,11011,110,110,111/10,11111,101,101,111/01,1表2中的故障f0导致单状态转换故障0010 10/ 00、0011 11/ 10，1 10110 01/ 00、0111 11/ 01、1010 10/ 11、1011 11/ 10、1110 01/ 11、1111 11/ 01、0010 10和1 1 1 1 1 1 1/ 0I. Pomeranz，S.M.Reddy/Electronic Notes in Theoretical Computer Science 174（2007）83871/0011001. 因此，f0等效于由上面列出的单状态转换故障组成的多状态转换故障。可以以类似的方式获得与其他固定故障等效的状态转换故障等效于固定故障f的状态转移故障可以通过com-88I. Pomeranz，S.M.Reddy/Electronic Notes in Theoretical Computer Science 174（2007）83f的二元测试生成组合测试生成只考虑电路的组合逻辑。该方法对主输入和当前状态变量赋值，并观察主输出和下一个状态变量的故障效应。 故障f的组合测试t定义单个状态转换故障siajsk/sJk和/或单个状态转换故障siajJsk，其中si是状态zlzl/zl矢量填充，即实际输入矢量填充，也就是说，t下的主输出向量，zJl是t下的故障主输出向量，sk是t下的无故障下一状态，并且sJk是t下的有故障下一状态。我们用ST（f）表示单状态转换故障的集合，它定义了等价于f的（单或多）状态转换故障。为了我们的目的，对于每个故障f使用所有单个状态转换故障的子集是足够的，因为从两个故障之间的差异中检测单个状态转换故障通常对于区分故障是足够的。因此，可以使用组合n-检测测试生成以便计算目标故障的集合ST（f），而不是导出完整的集合ST（f）（n-检测测试生成尝试为每个目标故障生成n个测试，导致大小为n或更大的集合ST（f））。这一观察结果使得所提出的测试生成过程适用于状态表不可用或不能有效地导出完整集合ST（f）的大型电路。为了诊断测试生成的目的，我们将定义一组状态转换故障STTARG。ST_T_ARG的元素ST_i将是单个或多个状态转换故障。诊断测试生成将包括生成STTARG定义的故障测试。可以使用功能测试生成程序，如[10]或[11]中描述的程序或者，状态转换故障的测试生成可以在门级完成，如下所示。最初 ，测试 序列T 是空 的，并 且电路 处于其 复位 状态。 对于每 一个故 障STi∈STTARG，使用顺序测试生成过程来生成测试子序列T，使得当T被添加到T时，TT检测STi。如果可以找到T，则将其连接到T。顺序测试生成过程类似于针对固定故障的测试生成过程，具有以下区别。 (1)从初始状态以及STi中的状态转换的主输入向量。(2)每次经过STi中包括的状态转换时，故障被激活。最终状态和输出值从STi获得。3诊断测试生成给定一组固定故障F和对于每个f∈F的等价的单状态或多状态转换故障ST（f），f∈F的集合ST（f）提供作为诊断测试生成的目标的功能故障，如本节所述。考虑两个故障fj1，fj2∈F，它们分别具有对应的状态转移故障ST（fj1）和ST（fj2）.集合ST（f j1）ST（f j2）由f j 1和f j 2共有的单状态转换故障组成。考虑子集ST（f j1）-ST（f j2）。 该子集由单个状态转换故障组成，I. Pomeranz，S.M.Reddy/Electronic Notes in Theoretical Computer Science 174（2007）8389从fj1开始，但不从fj2开始。 SupposethatST（fj1）−ST（fj2）<$. Atestequence在时间单位u检测到ST（fj1）-ST（fj2）的可能性在时间单位u检测到fj1u（除非ST（fj1）中剩余的单状态转换故障中的一些消除了由于ST（fj1）-ST（fj2）引起的故障效应，并防止在时间单位u检测到fj1）。另外，在时间单元u检测ST（fj1）-ST（fj2）的测试序列不太可能在时间单元u检测到fj2，因为单个状态转换目标是由fj2我们得出结论，在时间单位u检测ST（fj1）−ST（fj2）的测试序列可能在时间单位u区分fj1和fj2。以类似的方式，可以论证如果ST（fj2）-ST（fj1）/= 1，则在时间单元u检测ST（fj2）-ST（fj1）的测试序列可能区分fj1以及在时间单位u处的fj2。为了说明，考虑表2中所示的列4的f0和f2ST（f0）−ST（f2）={ 0010 10/ 00，0110 01/ 00，10 1010/ 11，1110 01/ 11，0010 10，0110 01}。 的1 1111/01/ 0输入序列10检测由ST（f0）−ST（f2）定义的故障相同的输入序列检测到f0，但不检测到f2。 因此，它区分了两个错误。f0和f12维的方程可以由ST（f12）−ST（f0）=π来表示。 在这种情况下，在诊断测试生成期间只能使用ST（f0）-ST（f12）。通过使用ST（fj1）−ST（fj2）和ST（fj2）−ST（fj1），我们对每对需要区分的固定故障执行最多两个状态转换故障的功能测试生成。ST（fj1）−ST（fj2）和ST（fj2）−ST（fj1）都可以是多重故障。还可以通过考虑每个st∈ST（fj1）-ST（fj2）和每个st∈ST（fj2）-ST（fj1）。需要的状态转换故障数在这种情况下要考虑的故障的数量更高;然而，每个功能故障由单个状态转换故障组成。在提出的诊断测试生成过程中，我们首先考虑两个功能故障ST（fj1）-ST（fj2）和ST（fj2）-ST（fj1）的每对固定故障fj1，fj2需要区分。然后，我们考虑包含在ST（fj1）-ST（fj2）和ST（fj2）-ST（fj1）中的单状态转移故障，但仅当|≤N且|ST（f j 2）|对于常数N ≤ N。| ≤ N for a constant N . 这一限制是以便限制所考虑的功能故障的数量。它的合理性在于，如果ST（fj1）和ST（fj2）之间的差异很大，则故障很可能通过基于其他故障对生成的测试序列来区分整个诊断测试生成过程在下面的过程1中给出。过程1：基于状态转换故障(1) 设F是单固定故障的集合。设ST（f）是与f等价的状态转移故障，对任意f∈F.设P是定义在F上的故障对的集合。 SetT=0。(2) 多个状态转换故障设置PTARG=P。(3) 选择fj1，fj2∈PTARG.从PTARG中删除fj1、fj2。(4) 如果ST（fj1）−ST（fj2）≠：(i) Generate testsubs enceT f orST（fj1）−ST（fj2）. 如果Tisgenneratd：(a) 将T连接到T。(b) 执行T和丢弃区分故障对的诊断故障模拟90I. Pomeranz，S.M.Reddy/Electronic Notes in Theoretical Computer Science 174（2007）83从P和PTARG。(c) 如果没有一个文件已分发，请从T中删除T。(5) 若fj1，fj2∈P且ST（fj2）−ST（fj1）/=π：(i) Generate testsubs enceT f orST（fj2）−ST（fj1）. 如果Tisgenneratd：(a) 将T连接到T。(b) 执行诊断故障模拟的T和下降区分故障对从P和从PTARG。(c) 如果没有一个文件已分发，请从T中删除T。(6) 如果PTARGG，请转到第3页。(7) 单状态转换故障设置PTARG=P。(8) 选择fj1，fj2∈PTARG.从P T ARG中删除f j1、f j2。(9) 如果|ST（f j1）|≤ N且|ST（f j2）|≤ N，对于每个st ∈ ST（f j1）− ST（fj2）：(i) Generate te s Tencet e t e st e t et 如果Tisgenneratd：(a) 将T连接到T。(b) 执行诊断故障模拟的T和下降区分故障对从P和从PTARG。(c) 如果没有一个文件已分发，请从T中删除T。(10) 如果|ST（f j1）|≤ N，|ST（f j2）|≤ N且f j1，f j2∈ P，对于每个st ∈ ST（f j2）−ST（fj1）：(i) Generate te s Tencet e t e st e t et 如果Tisgenneratd：(a) 将T连接到T。(b) 执行诊断故障模拟的T和下降区分故障对从P和从PTARG。(c) 如果没有一个文件已分发，请从T中删除T。(11) 如果我是PTARG，请到8号线。4实验结果程序1的有限状态机基准测试结果如表3和表4所示我们在程序1中使用N= 100。我们假设存在无故障的硬件复位到全零状态。在表3中，在电路名称之后，我们显示了主要输入的数量、主要输出的数量和状态变量的数量。 柱下flts我们展示了ST（f）的子集。这张照片是这样的目标断层组F. 然后我们给出定义在F上的故障对的数目。在表4中，在列multst flts下，我们显示了在考虑ST（f j1）-ST（f j2）形式的故障和ST（f j2）-ST（f j1）形式的故障之后的过程1的结果。在列single stflts下，我们显示了在考虑ST（f j1）−ST（f j2）和ST（f j2）−ST（f j1）的单状态转移故障后，过程1的结果。在每种情况下，我们显示了对功能测试生成产生状态转换故障的测试子序列的过程、由过程1生成的测试序列T的长度、由T检测到的固定故障的数量、由T区分的固定故障对的数量以及由T区分的固定故障对的百分比。I. Pomeranz，S.M.Reddy/Electronic Notes in Theoretical Computer Science 174（2007）8391表3电路参数电路InP 出来SV布雷茨对巴拉4241389453英国广播公司77423828203巴卜塔斯223631953蜜蜂计数3431105995CSE77435562835dk1435320721321dk1535215111325dk16235530140185dk172331288128dk27123672211dk5121341247626EX222531248516EX322415311628ex459417615400EX52231389453EX658322926106EX722415912561keyb725470110215狮子21240780狮子9213591711标记1414420320503MC352732628Opus56418116290shiftreg11328378Tav442642016火车112141045356列车421234561从表4可以看出，基于多个状态转换故障的诊断测试生成区分了大多数可区分的故障对。单状态转换故障的考虑增加了可分辨故障对的数量，代价是增加了对功能测试生成过程的调用数量。5单状态转换故障第4节的结果表明，对于形式为siajsk/sJk和siajJsk的单状态转换故障的功能测试生成将产生测试序列zlzl/zl这对于故障诊断是有用的。 这是一个事实的结果，状态转换故障可以潜在地包括在相当于两个固定故障的状态转换故障之间的差异中。 因此，瞄准它可能会导致 区分固定故障的序列92I. Pomeranz，S.M.Reddy/Electronic Notes in Theoretical Computer Science 174（2007）83表4诊断测试生成电路电话透镜穆尔特代圣伯多禄Dist%dist电话透镜单端检波器圣伯多禄Dist%dist巴拉10786130921197.4402345114130924997.842英国广播公司501562352816799.87210891802352817699.904巴卜塔斯125262163883.87144715762164083.973蜜蜂计数1139109596999.56625852110597899.716CSE512173546277899.9093292403546278399.917dk1426562062131499.967205562062131499.967dk1515371501131299.88566421501131699.921dk164416652914017099.98924217552914017499.992dk171345127810899.7545350127811099.779dk2752167219899.412252167219899.412dk5121657122760999.7777669122761299.816EX2321643114848799.9406242173114850099.967EX315571521162199.940182571521162199.940ex452951711536899.7929481011711536999.799EX51555138940899.52410867138941999.640EX625592282609599.958158642282609699.962EX7131701491249399.459699731491249499.467keyb8536646811015199.94223339246811016599.955狮子30144069388.846470174070189.872狮子9422853159393.10311053353159593.220标记146611972046699.820934821972047299.849MC62073261699.5431252573261799.581Opus38651801626799.85963731801627199.883shiftreg3142832385.450443142832385.450Tav121964196797.56919781964196797.569火车113536100528598.674130958100529498.842列车412143347985.383436203348185.740平均34771662154897.268703881662155397.369我们定义ST=<${ST（f）：f∈F}。ST是对应于所有单固定故障的所有单状态转换故障的集合（当关于固定故障的信息不可用时，可以使用所有单状态转换故障）。我们执行功能测试生成针对每个单一的状态转换故障ST∈ST。我们进行故障模拟和诊断故障模拟固定故障后，测试生成过程完成。的结果在表5中以与表4中使用的格式类似的格式示出了过程从表5中可以看出，以单一状态转换故障为目标通常会增加对功能测试生成过程的调用次数和测试长度。然而，它也增加了区分故障对的数量。这表明功能测试序I. Pomeranz，S.M.Reddy/Electronic Notes in Theoretical Computer Science 174（2007）8393列作为固定故障的诊断测试序列是有用的。更一般地，预期这样的序列对于以下方面是有效的：94I. Pomeranz，S.M.Reddy/Electronic Notes in Theoretical Computer Science 174（2007）83表5所有单状态转换故障电路电话全透镜单端检波器圣伯多禄Dist%dist巴拉11791274130924397.778英国广播公司7912125172352818299.926巴卜塔斯9315062174889.503蜜蜂计数156293110597999.733CSE3749172123556278199.914dk142062702072131499.967dk15501461511131699.921dk1636231452914017599.993dk1739159128811099.779dk27202367219799.367dk51261125122761499.843EX27646233124849799.961EX32301801531161699.897ex4217628611711536999.799EX539162138942499.693EX6101211142292609899.969EX73721661491249599.475keyb266482020646811017899.966狮子18654070790.641狮子95213753162594.974标记119448441972047099.839MC268673261699.543Opus285020161801624999.748shiftreg8482832084.656Tav7225464196497.421火车11178441100526198.226列车421783448786.809平均186122881662155797.642缺陷诊断6总结发言我们研究了使用功能测试生成的状态转换故障的一部分，诊断测试生成过程中的固定故障的可能性。固定故障f具有等效的单状态或多状态转换故障ST（f）。因此，可以通过与ST（fj1）和ST（fj2）之间的差异相对应的状态转换故障来表示两个固定故障fj 1和fj 2之间的差异。为这样的功能故障生成测试序列可能检测到一个固定故障而不是另一个，从而区分这两个故障。我们直接使用这一观I. Pomeranz，S.M.Reddy/Electronic Notes in Theoretical Computer Science 174（2007）8395察结果来定义对应于成对的96I. Pomeranz，S.M.Reddy/Electronic Notes in Theoretical Computer Science 174（2007）83固定的错误针对诊断程序的功能测试生成导致诊断测试序列。我们还使用了一个功能测试序列的单状态转换故障作为诊断测试序列，而不考虑固定故障明确。我们支持使用这些程序作为诊断测试生成程序的实验结果。引用[1] P. Camurati ，D. Medina ， P. Prinetto 和M. Sonza Reorda ，“A Diagnostic Test Pattern GenerationAlgorithm”，in Proc. Intl.测试确认，1990，pp. 52比58[2] T.格鲁宁Mahlstedt和H. Koopmeiners，国际机场Conf. 计算机辅助设计，十一月。1991，pp.194-197.[3] F. Corno，P. Prinetto，M. Rebaudengo和M. Sonza Reorda，欧洲设计测试会议，1995年3月，pp.267-271。[4] I. Hartanto，V. Boppana，J. H. Patel和W. K. Fuchs，“时序电路的诊断测试模式生成”，Proc.VLSITest Symp.，1997年4月，pp. 196-202.[5] I. Pomeranz和S. M. Reddy，国际机场测试确认，十月1998，pp.1074-1083.[6] V. Boppana和W. K. Fuchs，国际机场Conf. 计算机辅助设计，十一月。1998，pp.第147-154页。[7] Y. Xiaoming ， J.Wu 和 E. M. Rudnick ， “时序 电路 的诊断 测试 生成”， Proc.Intl 。 测试 确认， Oct.2000，pp. 225-234[8] K. Sabnani和A. T. Dahbura，“一种协议测试生成过程”，计算机网络，1988年，pp. 285-297。[9] H.- K. T. 马，S.Devadas，A.R. Newton和A.李文，计算机辅助设计，10月1988，pp.1081-1093.[10] K.- T. Cheng和J.Y. Jou，“Functional Test Generation for Finite State Machines”，Proc. Intl.测试确认，1990，pp. 162比168[11] I. Pomeranz 和 S. M. Reddy ， “On Achieving Complete Fault Coverage for Sequential Machines” ， IEEETrans. 计算机辅助设计，1994年3月，pp。378-386.[12] A. Fin和F. Fummi，2000年3月，pp。390-395.[13] M. B. 桑托斯角，澳-地M. 贡萨尔维斯岛C. Teixeira和J.P. Teixeira，欧洲测试研讨会，2000年5月，pp。99比104[14] F. Ferrandi，G. Ferrara，D. Sciuto，A. Fin和F. Fummi，“行为顺序模型的功能测试生成”，在欧洲会议的设计、自动化和测试过程中，2001年3月403-410.[15] V. M. Vedula和J.A.亚伯拉罕，“因素：功能测试生成和可测试性分析的分层方法”，在欧洲会议的设计、自动化和测试过程中， 2002年3月，pp. 七三零七三四
我的内容管理
收起
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助 
