（电路与系统专业论文）数字电路部分扫描可测性设计方法的研究.pdf

x3 6 2 6 彳8 摘要 f l 随着集成电路规模的增加，测试变得非常困难，测试覆盖率很难满足要 求。因此需要在电路设计中考虑测试，这就是可测性设计。 扫描设计是可测性设计的非常重要的一种方法，它的主要思想是在测试 状态时把电路中的存贮元件链结成为移位寄存器链。在测试状态下，可以将要 求的触发器状态通过移位移入触发器中，又可以将触发器新的状态移出检查。 这样就增加了电路内部可控、可观的节点数，使得本来很难测试的电路转化为 容易测试的电路。但是扫描测试增加了测试时间，对电路的面积和速度等方面有 较大的负面影响。因此就出现部分扫描的方法 ， 本文对部分扫描的触发器选择作了深入的讨论，在原有的基于状态密度的 扫描触发器选择的方法上作了改进，提出了一种改进的基于电路触发器对可控 性贡献的扫描触发器选择方法。同时，本文提出了新的基于故障观察和纽合测 试生成的触发器的两种故障可观性测度，并根据这两种故障可观性测度提出一 种新的扫描触发器选择的方法。我们也分析了扫描触发器对电路时序特性的影 响，并根据对时序特性的影响提出了一种接近全扫描的部分扫描触发器的选择 方法。在以上三种扫描触发器选择方法的基础上，本文提出了一种综合的，根 据故障可控性和可观性的扫描触发器选择的方法f 在对i s c a s8 9 标准电路的模 拟中，该方法对大部分电路可以减少扫描触发器的个数，提高测试效率和测试 覆盖率。 本文还在附录中提出并实现了一种简洁的电路数据结构。并在此基础上 我们实现了一个高效的逻辑和故障模拟器，并给出了模拟器的计算速度， 关键词：部分扫描，可控性，可观性，扫描触发器选择，逻辑模拟，故障模拟 a b s t r a c t w i t ht h ei n c r e a s i n gs i z eo f t h ei cc i r c u i t s ，i ti sg e t t i n gh a r d e ra n dh a r d e rt ot e s t 1 ca n dt h ef a u l tc o v e r a g ei sn o ts a t i s f a c t o r yi nt h em o s tc a s e s s ow es h o u l dc o n s i d e r t e s t a b i l i t yi nt h e c o u r s eo f d e s i g n i n gt h ec i r c u i tt h i si st h ei d e ao f d e s i g nf o rt e s t a m o n g t h ev a r i o u sd f tm e t h o d s ，s c a nd e s i g ni sb yf a rt h em o s tw i d e l yu s e d d f tt e c h n o l o g ya sw ek n o w , i ns c a nd e s i g n st e s tm o d e ，w ec a ns h i f tt h ed e s i r e d s t a t e si n t ot h ef l i p f l o p si nt h ec i r c u i ta n ds h i f to u tt h er e s u l ts t a t e sw i t ht h ea b i l i t yo f d i r e c t l yc o n t r o lt h ei n t e r n a ln o d e so f t h ec i r c u i t s ，s c a nd e s i g nc a nd r a s t i c a l l yi m p r o v e t h ec i r c u i t st e s t a b i l i t yh o w e v e gs c a nd e s i g ni n v o l v e ss p e c i a lf l i p - f l o pa n dc o m p l e x r o u t i n ga n dc l o c k i n g ，i tw i l lg e n e r a l l yi n c r e a s et h ea r e aa n dd e g r a d et h es p e e do f a c i r c u i ts i g n i f i c a n t l y t om a k et h em a t t e rw o r s e ，s c a nd e s i g ni n v o l v e se x t r e m e l yl o n g s c a ni n s c a no u tt i m ea n dg r e a t l yi n c r e a s e st h et e s tc o s t s ot h ep a r t i a ls c a nd e s i g n e m e r g e s i nt h i sp a p e la ni n t e n s i v es t u d yo np a r t i a ls c a nd e s i g ni sm a d e1 i m p r o v e da n e x i s t i n gc o n t r o l l a b i l i t yi m p r o v e m e n tp o t e n t i a lm e a s u r eb a s e do nt h es i m u l a t i o nb a s e d p a r t i a l s t a t e d e n s i t y o ft h e s e q u e n t i a ll o o p s ，i a l s o p r o p o s e dn e wm e a s u r e s o n i m p r o v i n gt h e f a u l t o b s e r v a b i l i t yb a s e d f a u l to b s e r v a t i o na n dc o m b i n a t i o n a lt e s t g e n e r a t i o n w ea l s oc o n s i d e r e dt h ep o s s i b l et i m i n gl o s si nt h ep a r t i a ls c a nd e s i g n n e w p a r t i a ls c a ns e l e c t i o nm e t h o d sb a s e do nt h ea b o v et e s t a b i l i t ym e a s u r e m e n t sa v e p r o p o s e da n ds i m u l a t i o nr e s u l t s a r ep r o p o s e d w ea l s o p r o p o s e dac o m p r e h e n s i v e s c a ns e l e c t i o nm e t h o dw i t ha l lt h et e s t a b i l i t ym e a s u r e m e n t s s i m u l a t i o nr e s u l t sf o r i s c a s8 9b e n c h m a r kc i r c u i t ss h o w si t s p e r f o r m a n c ei ss u p e r i o rt ot h e e x i s t i n g m e t h o d s i nt h ea p p e n d i xo ft h ep a p e r , a s i m p l i f i e da n de a s y t o u s ed i g i t a lc i r c u i tm o d e li s p r o p o s e d a ne f f i c i e n tl o g i c f a u l ts i m u l a t o ri s i m p l e m e n t e da n ds i m u l a t i o ns p e e di s c a l c u l a t e d k e y w o r d s ：p a r t i a ls c a nd e s i g n ，c o n t r o l l a b i l i t y , o b s e r v a b i l i t y ，s c a nf l i p f l o p s e l e c t i o n ， l o g i cs i m u l a t i o n ，f a u l ts i m u l a t i o n 兰! 羔坠一 第一章概述 1 1 可测性设计的背景 随着数字集成电路技术的发展，集成电路技术获得了极其广泛的应用。根 据m o o r e 定律，数字集成电路的规模以每1 8 个月翻一番的速度持续地发展。 从六十年代的一片集成电路只可以集成几个晶体管，到目前i n t e lp e n t i u m1 1 1 处 理器的一千多万个晶体管的规模，c p u 速度从八十年代初的l 兆赫到目前的7 0 0 兆赫左右。集成电路的最小特征宽度也发展到了目前的0 2 5 ，01 8 甚至最新n e c 公司推出的0 1 3 微米的工艺。为了保证集成电路的可靠性，必须对所生产的集 成电路进行彻底的测试图11 就是最终成品集成电路的可靠性( 即通过测试 合格的集成电路没有故障的概率) 与测试向量的故障覆盖率的关系。 电路晶体管数 图1 1 产品可靠性与电路规模的关系 从图中可以看到，对于大的电路而言，只有测试覆盖率达到很高的水平， 并且原始硅片上的故障率很低，才能保证生产所得的合格的集成电路有较高的 无故障率。然而，对于电路的设计者而言，原始故障率是由生产工艺决定而不 可改变的。设计者可以做的，就是要设法提高电路的测试覆盖率。对于一般存 储器等一些规则的电路，很容易通过一些可测性机构实现1 0 0 的测试覆盖率 而对于用户自己设计、综合或者逆向设计所得到的电路，就很难保证其测试覆 笙= 兰塑鲨 盖率。但是对这些电路一般依然要求故障覆盖率至少要达到9 5 以上，才能保 证通过测试的产品的可靠性。不幸的是，随着电路规模的增大，由于电路的内 部节点难以控制和观测，对电路的有效测试也越来越困难。一个大规模的数字 电路，如果不进行有效的可测性设计，测试覆盖率一般很难超过6 0 。而这样 的测试覆盖率是不可接受的。为了达到可以接受的测试覆盖率，我们必须对电 路进行设计，以使之易于测试为了测试对于电路进行改动和设计的方法称为 可型性设盐。 1 2 电路的可测性 数字电路的可测性是一种表示数字电路的故障是否容易被检测的一种度 量。它包含可控性和可观性两个部分。在检测一个故障时，我们必须激励该故 障，使电路达到一个故障点状态与故障相反的状态，这需要电路具有较好的可 控性。然后需要设法把故障传播到电路的输出端，这需要电路具有很好的可观 性。 数字电路测试中电路的可控性非常重要。在测试时初始状态的设定，故障 的激活、传播，都需要保证电路可以达到所需要的状态。对于单固定型故障， 在故障激活时，必须能够把故障点的状态设置到与故障的值相反。如果该故障 为s _ a 1 故障，则必须能够把正常电路的这一点设为0 ，反之，如为s - a _ 0 故障， 则必须设为1 这样就要求电路能够进行这样的控制需要电路有较好的可控 性。 数字电路的可观性对电路的测试也有非常重要的意义。为了检测一个故 障，必须把正常电路的状态和故障电路的状态区分开来因此，我们要设定相 应的状态，使状态可以在输出端检测到( 即正常电路的输出和故障电路的输出 不同) 。如果要使电路的一个节点可以被输出端观测到需要很多输入端和记 乙元 件( 如d f f ) 都设到确定的状态，那这个鲒点就很难观测，反之如果一些节点不 需要设置任何状态就可以观测到状态，如原始输出端节点，其可观性就非常高。 目前已经有很多方法可以计算电路的可控性和可观性。由g o l d s t e i n 3 4 1 提出 的s c o a p 测度，是一种有代表性的电路可控性可观性测度该方法是一种基 2 笙二童塑堕 于电路结构分析的方法。s c o a p 根据电路的逻辑结构，把节点0 和1 的可能性 根据组合器件的性质进行计算。它定义了组合0 1 可控性、可观性，时序o l 可 控性、可观性的计算方法。但是该方法计算0 1 的可达性时，认为所有电路的 状态具有相同的概率，从而计算节点的0 1 可能性的方法，具有一定的局限性。 以后还出现了p r e d i c t l 6 3 i ，t a i r f 4 ”，概率性可测性”1 等算法，提出了对电路可 控性和可观性的不同的计算方法。本文将在后续章节中，讨论提高电路可控性 和可观性的可测性方法。 1 3 数字电路的可测性设计 可测性设盐是指在集成电路设计中对电路的测试加以考虑，进行设计的方 法。一般包括局部可测性方法和结构性可测性方法两大类。局部可测性方法的 是根据电路局部的特性对电路进行修改，使之容易测试，一般有测试点插入等 方法1 2 2 9 1 ；而结构性可测性设计方法则是根据可测性设计的一般规则和基本模 式来进行电路的设计，一般包括扫描设计( s c a nd e s i g n ) i i i 2 1 1 1 4 - 2 0 2 2 - 2 3 3 1 - 3 3 3 6 。4 1j 【5 1 。 5 5 1 1 5 7 6 0 , 虫整自型达( b i s t ) 3 0 l 【4 5 j 【6 。1 ”等a - ；- 去- ，还有针对单芯片系统( s y s t e m o n c h i p ) 的一些综合性测试方法【6 6 i 等这些方法在实际电路设计中得到了广泛的应用。 下面几个小节分别介绍这些方法 1 3 1 局部可测性设计方法( a dh o c 方法) 局部可测性设计方法是根据电路的局部情况选择可测性设计策略，使电路 容易测试。例如在对多位计数器的测试中，测试高位的触发器电路就必须使计 数器运行很长时间才能得到高位的变化，对此我们就可以在这里进行可测性设 计，在测试状态下使外部可以直接对高位触发器置复位，就可以大大提高电路 的可测性。或者在一个很难设置为1 的节点上，加一个或门，使电路在测试状 态下可以把电路的状态设为1 但是由于a dh o c 方法不是一种系统的方法，在实际应用中有很多限制。 一般来说，这种测试点注入( t e s tp o i n ti n s e r t i o n ) 方法1 2 7 1 在实际应用中往往与结构 性方法中的内建自测试( b i s t ) 方法结合起来使用f 3 0 l ，提高电路在随机向量输入 时的故障覆盖率。最近也有把测试点注入方法和部分扫描设计方法结合起来的 3 笙兰塑生一 方法【2 8 2 9 1 ，对电路的测试有较好的效果。 1 3 2 结构性可测性设计方法 结构性可测性设计( s t r u c t u r e dd f t ) 的方法，就是用一种系统性的方法来提 高电路的可测性，如扫描设计，内建自测试等。这些设计方法在实际应用中得 到了非常广泛的应用目前几乎每个实际设计的大规模集成电路都使用了结构 性的可测性设计方法。 1 3 2 1 扫描设计方法( s c a nd e s i g n ) 扫描设计方法的主要思想是把电路中一部分或所有的时序元件链接成为移 位寄存器，移位寄存器链的两端分别是电路的原始输入端和原始输出端。在正 常状态下，这些移位寄存器并不起作用，电路执行着正常的电路功能。而在测 试状态下，测试者可以通过移位寄存器把电路置到所需要的状态，同时也可以 用移位寄存器移出电路的状态，从而可以观测电路的内部状态1 参见图12 。 系统时钟 图l 2 ( a ) 原始电路结构 4 笙二兰塑堕一 图1 2 ( b 1 扫描可测性设计, 后e - j 电路结构 图1 2 是一个典型的基于多路器的扫描设计的实现当s c a n e n a b l e 信号为 低时，电路正常工作，扫描设计电路对电路的功能没有任何影响。而 - 3s c a n e n a b l e 为高时，所有触发器连成了一个移位寄存器。测试时可以首先把s c a n e n a b l e 置 为高，由这个移位寄存器链使电路达到指定的状态然后把s c a n e n a b l e 置为低， 对电路的其他部分进行测试。最后再次拉高s c a n e n a b l e ，把运行过一个或多个 时钟后的电路状态通过移位寄存器输出，检查是否与预先计算的结果相同。 对一个时序电路而言，妨碍电路的可测性的最大障碍是无法对电路内部时 序元件进行有效的控制和观测而扫描设计- j - 以提供一种彻底的解决测试问题 的方法。因此扫描测试在实际电路设计中得到了广泛的使用。几乎每个较大的 数字电路都有扫描可测性设计在其中。 扫描可测性设计分为两种：一种是全扫描设计，即把一个电路所有的时序 元件都链接到扫描链中来。这种方法可以最大程度上提高电路的- j - 钡, j 性和可观 性。这样的扫描可测性设计方法称为全担垫遮盐这种方法可以很容易实现电 路的9 9 以上的可测性而且这种方法在设计时也相对比较简单，m e n t o r g r a p h i c s 【9 1 、s y n o p s y s f l o l 等主流的e d a 厂商都提供直接实现全扫描设计的可测 性设计解决方案，目前是扫描设计的主流。 但是，由于全扫描设计把所有的触发器都链在了扫描链中，对一个大的电 路而言，需要扫描的时序元件数会很多如果这个电路只用一个扫描链的话， 每次输入输出一个测试向量都需要花费很多的时间。由于测试费用的高昂( 一 兰! 坐生一 般可以和制造费用相同) ，较长的测试时间会大大提高电路的测试成本一因此有 一些设计人员选择了多条扫描链的技术但是这种技术需要比较多的输入输出 端供扫描输入输出使用，因此也受到一定的限制 由于全扫描设计把所有的触发器都变成扫描触发器，因此它增大了电路的 关键路径的延时( l s s d 方法除外，但是l s s d 方法只能使用锁存器，不能使 用触发器) 和电路的面积同时由于需要驱动所有触发器上的s c a n e n a b l e 端， 对电路的驱动和布线能力有较大的考验。最后往往使电路的面积增加2 0 4 3 0 。由于每加一个向量就需要把一个向量向扫描链中移位一遍，需要较长的 测试时间，因而也较大幅度的提高了电路的成本 各种实验证明，在可测性设计中，仅扫描一部分触发器，就可以实现电路 的测试覆盖率达到令人满意的水平因此出现了叠金担垫选盐，即在电路中选 择一部分触发器作为扫描触发器的可测性设计方法。这种方法可以在对电路影 响较小的情况下满足电路的可测性要求。在降低额外面积和测试时间的同时相 对全扫描电路可以有效提高电路的速度。根据m m 的研究结果，仅由于电路由 全扫描改为部分扫描，可以提高电路的速度1 0 左右l 。但是由于部分扫描技 术不受主流e d a 公司如c a d e n c e 、s y n o p s y s 、m e n t o r 、a v a n t ! 等主流e d a 软件 厂商的有效支持，在实际设计中应用比较少。目前有i b m 的s - 3 9 0 主机的c p u 等系统使用部分扫描的可测性设计，其他的很多高性能的电路中很多使用的扫 描技术也不是对所有的触发器进行扫描部分扫描可测性设计方法将在14 中 具体介绍 1 3 2 2 内建自测试方法( b u i l d - i ns e l f - t e s t ) 内建自测试的方法就是在电路中加入测试向量生成和测试结果检测的电 路，在电路内部直接实现对电路进行测试的方法内建自测试方法有两种，一 种是对存储器等规则性电路的，另一种则针对一般的逻辑电路 在对一般逻辑电路的内建自测试中，通常在电路中增加一个循环移位的伪 随机测试码生成器。该生成器负责对电路输入随机码。同时在电路的输出端也 输入到一个由带抽头的循环移位寄存器构成的数字签名压缩器( m i s r ) 对输出结 6 兰二童塑垄一 果进行检测。在b i s t 的设计中，由于输入的是随机向量，为了提高电路的随 机向量测试覆盖率，往往在电路中加入一些局部的可测性设计，如测试点插入【3 0 等。也有很多实现中，把b i s t 与扫描路径结合起来。把随机输入加入扫描链， 模拟结束后把扫描输出加入m i s r ，这种方法可以实现较高的时序电路测试覆 盖率。这样的扫描内建自测试方法在主流e d a 厂商中有相当的支持。如s y n o p s y s 和m e n t o rg r a p h i c s 都有相应的b i s tx - 具。 1 4 部分扫描可测性设计( p a r t i a l s c a nd e s i g n ) 本节主要介绍部分扫描可测性设计的方法的分类和其优缺点。部分扫描方 法包括扫描触发器选择、扫描链的最优排列、测试向量的压缩等方面。在根据 其方法主要可以分为几类：基于电路拓扑结构的部分扫描可测性设计【1 l f l 2 】l ”】【2 1 1 1 5 。 ”l m l ；基于电路可测性分析的部分扫描设计；基于测试生成和模拟的部分扫描 设计；基于电路的高层次描述( 如行为级、r t l 级等) 的可测性设计【”4 1 ；基 于系统性能的设计，如基于时延特性的部分扫描设计1 6 、基于重定时的部分扫 描设计陋1 1 “l 和基于版图信息的可测性设计1 6 8 i 等 1 4 1 基于电路拓扑结构的部分扫描设计 由于电路的时序元件的可控性和可观性不好，使电路的测试生成非常困 难。然而，测试生成的难易程度与电路结构有关。由于时序测试生成必须激励 电路内部节点，并把故障传出，电路中较高的时序深度( 从输入到输出之间的 最多的时序元件的个数) 会非常严重的影响测试生成的效率 在结构分析中，通常将一个同步时序电路的时序拓扑结构用一个有向图 g = ( e 目表示g 中的每个顶点代表电路中的一个触发器，任意两个顶点( ) e 当旦堡当时序单元v 。的输出和屹的输入直接相联或者存在一条从输出 到v 2 输入的完全由组合电路构成的一条通路这种有向图称为时序电路的s 一 图 对于电路中的时序元件构成的非自环路，即在g 中的顶点个数大于1 的有 向回路。由于其状态不能通过外部输入直接确定，对这些环中的触发器置位非 7 篓二翌塑l 一 常困难。因而更难以对电路进行有效的测试。结构化部分扫描设计方法就是根 据这种思想来选择扫描触发器。一个扫描触发器被选择以后，该触发器可以被 完全控制和观察。因此可以认为这个触发器是一个伪标准输入和伪标准输出。 从而可以把这个触发器所对应的s 一图中的顶点与相应的边删除。如果选择一 部分触发器，使s 一图做相应的简化，就可以在很大程度上提高测试生成的速 度和效率。这类方法需要解决有向图的最小反馈顶点集( m i n i m u m f e e d b a c k v e r t e xs e t ) 问题，即对一个简单( 无自环) 的有向图，找到一个它的最小的反馈 顶点集，使删除属于该集合的顶点后该图没有任何回路。根据文献【2 1 的结论， 这个问题是个n p 完全问题，不可能在合理的时间内用算法解决。对m f v s 问 题，许多文章都提出了不同的算法【2 + 7 l f ，l ”l 。 k - t c h e n g 于1 9 9 0 年在文献中提出了这种想法并提出了一种实用的选 择扫描触发器的方法。该方法根据触发器所在的环的数量用贪心法选择扫描触 发器，在选择部分扫描触发器时得到了较高的测试覆盖率，他的方法需要比较 多的扫描触发器t a i 等l ”恻运用了文献【”1 所提出的方法，实现了一个完整的部 分扫描的方法。p a r k 等2 1 在文献的基础上提出用图的删节的方法解决部分扫 描的m f v s 问题，减少了所需要的扫描触发器数。而l i n 等在文献【7 1 里进一步 改进了其中的近似解决部分扫描i v l f v s 问题的算法，提出了更多的图的简化的 准则，从而在选择更少的触发器时消除s 一图中的所有时序回路。叶波在文献| 8 l 中则提出不仅要删除包括自环的所有回路，而且要去除所有的时序重汇合中各 支路具有不同时序长度的情况，使电路的时序结构成为流水线结构。这种方法 可以保证很好的测试覆盖率，并可以很大程度上减少测试生成时间但是这种 方法所需要的触发器数量更多，对电路的性能和面积的影响较大。 1 4 2 基于模拟和测试生成的部分扫描方法 在测试生成中往往可以发现，即使把一个电路的s 一图变为没有非自环的 回路，也不一定能达到满意的测试覆盖率，还有一些本来无环的电路，虽然测 试生成很快，但是电路的测试覆盖率相当低。这时1 4l 节中的基于拓扑结构 部分扫描设计方法就无法使用了。而且在事实上，并不是每个逻辑回路都需要 通过部分扫描的方法加以去除。因此有基于模拟和测试生成的部分扫描的方法 堕二兰塑堕 一 5 - 2 0 l ， 2 2 - 2 3 1 。文献5 1 在s 一图中根据测试生成中的难测故障对s 一图各边设置权重 进行扫描触发器的选择。p a r k 在文献m 坤提出一种基于故障状态传播要求的部 分扫描选择方法。在文献n 9 】中c o r n o 等提出一种基于模拟的遗传触发器选择方 法，与基于遗传算法的测试生成器g a t t o t 6 7 l 一起，可以获得较高的测试覆盖率。 但是g a t t o 假定所有触发器均可以直接复位。而实际的，无初始状态的电路 的故障覆盖率就没有文献值那么高。h s i a o 等在i c v l s l d 9 8 上的文章1 2 0 l 则提出 一种基于触发器状态变化的动态可测性测度，并根据此测度进行扫描触发器的 选择。该方法在使用s t r a t e g a t e t 6 9 l 进行测试生成，虽然可以达到相当高的测 试覆盖率，但是其向量数是常用的h i t e c l 叫大5 0 一1 0 0 倍左右，会大大影响测 试速度。 向东等在文献8 1 1 2 3 | 申提出了基于时序回路的状态密度的扫描触发器选择的 方法。该方法使用逻辑模拟产生大量伪有效状态，并把这些状态映射到时序回 路中，并计算回路的状态密度( 即有效状态与所有状态数之比) 。然后根据状态 密度选择扫描触发器，破除电路的时序回路。具有较好的部分扫描的效果。 1 4 3 其他部分扫描方法 其他的部分扫描的方法包括基于电路的高层次信息，如r t l 级或行为级描 述的扫描选择扫描链排列方法由于- q - 以使用电路的高层信息，可以有效的实 现寄存器宽度的多扫描链设计，并在很多情况下可以减少实现所需要的额外电 路。在有的方法中，把扫描部分写入电路的行为级或r t l 级描述中进行综合， 可以保证较好的特性。也包括基于时序的扫描触发器选择，如文献【6 0 i 等 1 5 本文的工作 本文对部分扫描的触发器选择作了深入的讨论。在原有的基于状态密度的 扫描触发器选择的方法m 】【”l 上作了改进，在电路模拟中摆脱了原方法对电路的 伪初始状态的依赖，提出了一种改进的基于电路触发器对可控性贡献的扫描触 发器选择方法同时，本文提出了两种新的基于故障观察和组合测试生成的触 发器的故障可观性测度，并根据这两种故障可观性测度提出一种新的扫描触发 器选择的方法。我们也分析了扫描触发器对电路时序特性的影响，并根据对时 苎二童塑堕 一一 序特性的影响提出了一种接近全扫描的部分扫描触发器的选择方法。在以上三 种扫描触发器选择方法的基础上，本文提出了一种综合的，根据故障可控性和 可观性的扫描触发器选择的方法。在对i s c a s 8 9 标准电路的模拟中，该方法对 大部分电路可以减少扫描触发器的个数，提高测试效率和测试覆盖率。 1 6 论文的安排 本文是如下安排的：笠二主则对可测性设计作一个综述，并介绍前人的工 作。第二章则在前人的基础上改进了一种基于回路状态密度的触发器可控性增 益的测度，并在该测度下实现一种基于电路可控性的扫描触发器选择的方法和 具体算法实现，并给出对i s c a s 8 9 标准电路进行可测性设计的测试生成的结果。 这一章的主要目的是提出一种改进的触发器可控性增益的测度箜三室则提出 了基于故障传播和观察的触发器可观性测度和一种基于组合电路测试生成的故 障可观性测度及根据这两种方法进行扫描触发器选择的方法。第四童则是对扫 描触发器对电路的时延特性的影响，并提出一种不影响电路的时序特性的接近 全扫描的部分扫描方法，也给出了对i s c a s8 9 标准测试电路的扫描触发器选择 和结果。笠垂主提出了一种基于电路触发器的可控性增益与可观性增益的一种 扫描触发器选择方法，该方法还同时考虑了选择扫描触发器对电路性能带来的 影响并在扫描触发器的选择中减小或完全消除这种影响。笠六主是结论与展望。 在附录中介绍了实现的一个逻辑和故障模拟器，该模拟器是实现扫描触发器的 算法中非常重要的部分。 1 0 篁三童墼主皇堕塑旦鳖丝塑堇墨堡塑里丝丝塑蕉堕旦型丝塑兰一 第二章数字电路的可控性增益及根据可控性增益的 可测性设计 本章提出一种电路触发器的可控性增益的计算方法，该方法在文献m 1 的状 态密度定义的基础上，加以改进。并提出了改进的状态密度计算方法。 2 1 电路的可控性和可控性增益的定义 定义2 1 电路的丛查，是指一组对数字电路的触发器的赋值。在无故障 的情况下的状态所可能赋的值为 o ，1 ， ；在考虑故障模拟的情况下所可能赋 的值为如，l ，d ，万，x 。d ，万分别为二元组( o ，1 ) 和( 1 ，o ) 。二元组的两个元素依 次表示触发器在无故障和故障下的取值。 定义2 2 一个电路的盔塾些查，定义为由电路的任一状态经有限个时钟 和一组相应的输入向量可以达到的状态。 注意任一状态包含全x 的状态。特别的，全x 的状态也属于有效状态。 定义2 3 如果一个有效状态对所有触发器所赋的值均为非x 的值，则称 该状态为塞全查丛些查 定义2 4 一个电路的韭堕塞直垫鉴查是一个有效状态，且存在至少一个 触发器，该状态给它的赋值为x 。 定义2 5 一个电路的垂夔鉴查是指一个状态t ，至少存在另一个状态t ， 不存在一组输入向量，可以经过有限的时间使电路由状态，枯到状态l 推论2 1 所有的无效状态的集合是所有有效状态的集合的补集。 证明：从有效状态和无效状态的定义可得。 推论2 2 一个状态是有效状态，当且仅当它可以由全x 的状态通过有限 的时间转到 证明：如果一个状态可以由全x 状态通过有限时间达到，而任何其他状态 都可以认为是全x 状态，所以该状态可以由任何状态达到，充分性成立。由于 全x 状态也是一个电路的状态，由定义可知必要性成立。得证。 如果在测试生成的状态确定中所要求确定的状态为无效状态，则会进行很 笙三皇墼兰皇堕塑旦丝丝丝垫墨堡塑里丝丝苎重堕里型丝丝盐一 长时间的状态确定而最终达到测试生成的限制而放弃，导致回溯。频繁的回溯 会导致很难确定激活故障所需要的序列，最终可导致放弃该故障的测试生成。 定义2 6 呈二- 旦，为一个有向图g = ( 矿，司，其中顶点集v 代表电路中的 触发器的集合，其中每个顶点代表一个触发器对于图g 中的两个顶点v 、屹， 如果v i 代表的触发器的q 端到v 2 代表的触发器的d 端之间有一条组合通路， 即存在一务通路，且该通路中没有时序元件，边“，v ：) e 定义2 7 叠盆直垫鉴查：如果s = o 。，v ：，v 。) 为一个电路的有效状态， 对于一个部分状态卜”v j 2 ，v k ) ，l f i f 2 ”， 若v 州，1 卅k ，m n ，满足v 。 0 ，1 ，则称该状态为部分有效状态。 定义2 8 丛查睦盘是指对一个有效状态，把其状态映射到一组触发器集， 获得一组部分有效状态的过程 定义2 9 查蕉丛查蜜廑：e d = , i y t o 。t a l ，其中n , o 。为电路的完全有效状态 数，而，为触发器数。该定义的涵义是完全有效状态数与所有可能的完全状态 数之比比例越高则说明电路中存在越多的无效状态，在测试生成时会大大影 响测试生成的速度。 对大部分时序复杂的电路而言，电路的有效状态密度e d 远小于1 ，而对 一些无时序环，或可控性很好的电路，其有效状态密度e d 就比较接近于1 。 定义2 1 0 叠盆盔塾鉴查蜜麈定义为e d ，= 等。其中p 是电路触发器集矿 的一个子集，k = l p i ，表示p 所包含的触发器的数量。p 是所有对应于p 的部 分有效状态的个数因此e 1 ) p 是由触发器集合p 对应的部分有效状态与所有可 能的部分状态之比 定义2 1 1 塑佥型达生盛丛查塞m 是指把一个电路作为组合电路，就是把 一个电路的所有时序元件的时序输入端( 一般为d 端) 作为原始输出端，而q 端作为原始输入端，并删除原来的时序元件对这样的组合电路进行测试生成。 由于这是组合电路，测试生成一般非常迅速。所得到的对应于所有时序元件的 向量组构成组合测试状态生成集 1 2 丝三童墼主堂塑里丝坐塑堡塑堂堂塑型型一 定义2 1 2 组金型达生盛壹金查丛! 噬定义为( d r3 瓮，其中蜱为组合 测试状态集m 映射在触发器集p 中不同的部分状态的集合( 集合元素的个数) 。 而n p 为所有属于膨的不同的部分有效状态的集合( 元素的个数) 根据定义 可知c d ，代表了组合测试生成集所对应的部分状态中有效状态的比例。对于p ：v ( 所有触发器组成的集合) ，如果c d ，= i 则所有电路的故障均可以传播到次 态。 定义2 1 3 堕庄旦整：在一个电路的s 一图g = ( k d 中，存在一组顶点p 2 ( v 。h ，站，满足边( v i + 1 ) e ( ，= l ，k 并记u 。= u ) 。由于同步时序电路 不存在组合回路，因此也可以简称时序回路为堕整由回路顶点构成的集合称 为回路触发器集。 定义2 1 4 堕整鉴查蜜廛r 比 ，是部分有效状态e d e ，且其顶点集( 触发器 集) p = ，v 2 ，v a ，存在一个排列h ，v p ，v 。) ，0 r v i 2 ， ) 是电路的一 个时序回路。 定义2 1 5 堕整塑佥型这些查蜜廛尺c d 尸类似于定义1 4 ，是组合测试生成 状态密度c d e ，且触发器集p 在s 一图中存在排列可以构成回路 对于一个同步时序电路而言，文献【2 3 1 等都表明状态密度与测试生成的效率 有密切的关系，提高电路的状态密度可以有效提高很多嗲电路测试生成的效率。 同时根据结构性部分扫描的理论和文献川【2 1 1 等的讨论，无回路的同步时序 电路的测试生成接近于组合电路而回路之所以影响电路的测试生成的主要原 因是回路的状态难以控制 而一般的结构性部分扫描方法中的触发器选择的原则业就是要消除电路中 的回路。综合考虑以上两个结论，我们在这里考虑回路的可控性。如果一个回 路里的状态可以达到，可以认为该状态是一个容易控制的状态。反之，如果一 个回路的状态难以达到，可以认为该状态是个不能控制的状态对于一个回路 而言，如果其回路状态密度很大，即其大部分状态都可以达到，该回路就具有 较高的可控性，回路的存在对测试生成就没有太大的影响反之，如果该回路 的部分状态密度很小，就会经常导致在测试生成的过程中要求确定一些无效部 分状态。由于无效部分状态无法达到，会导致长时间的反复，会严重影响测试 生戍的过程 兰三童塾兰皇堕塑旦垄丝丝耋垦堡塑旦丝丝堂垫盟旦型丝望堕一 因此我们可以引出一种时序回路对电路的可控性损失的度量，即可以根据 回路的状态密度确定回路破坏对电路可控性的贡献。如果不存在这个回路，该 部分电路的应该很高。虽然由于存在其他回路，破坏后的电路的状态密度也不 一定能够达到1 ，但是这种情况我们应该考虑其他回路的对电路的可控性损失。 根据以上讨论，我们定义了回路可控性损失如下： 定义2 1 6 宴整互揎：睦塑叁为一个时序回路c 的存在对电路可控性的损 失，具体定义为： h c l c 一1 。g ：e d c 。1 0 9 2 忌 由于在状态确定时并不一定需要对回路的所有触发器均决定状态，回路有 效状态数取以2 为底的对数，相当于等效回路中依然可控的平均触发器数。我 们同时假设如果不存在此环可以达到所有状态( 如果不存在其他回路时，可以 满足此假设，但如果有其他回路，达不到所有状态是其他回路对电路可控性的 损失) 。 一个扫描触发器可以被认为是一个d 端的输出端和q 端的输入端，因此 如果一个回路包含扫描触发器，则可以认为该回路已经被破坏因而可以消除 该时序回路对电路可控性的影响。因此对一个触发器来说，如果选择这个触发 器作为电路的扫描触发器，可以破坏所有包含该触发器的时序回路，从而可以 提高电路的可控性 为了度量扫描一个触发器，对电路的可控性的影响，我们定义了触发器的 可控性增益 c l p o r ) = 皿。k 。 c ：i e c 其中c 是一个包含触发器的时序回路，c l 。是回路c 的回路可控性损失， 而颤则是回路触发器的个数。 对回路的组合测试生成状态密度，由于它可以影响电路的可观性，我们在 下一章对此作进一步的讨论 对于实际电路的c z p f f ) 的计算方法在下一节中介绍。 1 4 笙三童塾兰皇堕塑里丝垡塑垫墨塑塑里丝丝丝堇堕亘型丝垦盐一 2 2 电路的触发器可控性增益的计算方法 在上一申已经介绍了本文所使用的可控性增益的定义，并进行了一些讨 论，而本节将重点介绍数字电路的触发器可控性增益的计算方法。 2 2 1数字电路的时序回路的确定 在21 节中的触发器的可控性增益的计算公式。在公式中要求对所有包 含所计算的触发器的时序回路计算它们的可测性损失，因而需要计算这些时序 回路的有效状态密度。但是，对一个较大的，时序比较复杂的电路来说( 如s 1 4 2 3 、 s 5 3 7 8 、s 1 3 2 0 7 、s 1 5 8 5 0 等) ，电路所存在的不同的回路的个数非常大，几乎随 电路的触发器数和电路s 一图顶点的平均入度和出度成指数关系事实上，对 于一个s 一图的一个有向完全子图，即该子图的所有顶点之间均相互有边，根 据组合数学的计算，该子图的不同的回路数有个，不同的回路触发器构 成的集合为2 “一玑其中露为排列数，为石兰万，式中 为完全子图的阶数( 顶 点数) 。 因此不可能把电路所有的回路都找出来，因为对复杂的电路可以达到0 ( 2 ”1 的时间和空间复杂度。这是不可接受的。 同时，把电路所有的回路都找出来本身也是不必要的，对一部分的时序回 路的状态密度的分析，在所有回路都已覆盖的条件下，回路的状态密度可以用 来估计所有回路的情况 由于电路的时序回路强定属于其s 一图的强连通子图的一部分，我们引进 了图论的强连通子图和最大强连通子图的概念 定义2 1 7 堡堡适主虽：在一个有向图g = 缈，e ) 中，如果存在一个顶点集 合矿，满足v u ，v ：，存在一条由v 。到屹的通路 v 1 2 ，v 。) ， v 、= u ，q 。= v ：， 且通路中所有顶点都属于矿。记边集 e = ( v 。，v ：) l ( v ，v ：) e v ，矿，v ：v ) ，则图g = o ，e ) 称为图g 的一个堡壁 1 5 笙三兰塾兰皇堕塑里丝丝丝堇墨竖塑旦堇丝丝堇堕旦型丝丝盐一 塑i 垦s c c 。 推论2 2在一个强连通子图里的任何两个顶点都可以在一个有向回路 中。 证明：由于顶点1 到顶点2 之间有通路，顶点2 到顶点1 之问也有通路， 因此可以构成一个有向回路。 定义2 1 8 塞盘堡壅亟i 堕在一个有向图g = ，e ) 中，图g = o ，e ) 是一 个图g 的强连通子图，满足： 对于任意的不属于矿的顶点( v 矿且v 仨矿) ，我们记k = 矿u p ) ， 巨= 鼢。，v ：) i ( v ，、，：) e ，v 、，v ：v 1 ) ，图g 的子图g i = 以，e f ) 不是图g 的强连通子图。 推论2 3 如果g = 以，e ) 和g ：= 以，e ：) 是图g 的两个不同的最大强连 通子图，满足k 哆，则kn = a 讧明：反证法，如果kn o ，则存在v ，v k ，v 对于任一个v 。k ，嵋v ，存在h 到v 和v 到v 。的通路。 对于任一个v 2 ，v 2 v ，存在v 2 到v 和v 到v 2 的通路。 因此存在到v 到屹的通路，也存在屹到v 到v 的通路。 所以ku 和：) 也是强连通子图，与k 是最大强连通子图矛盾 根据以上的定义和推论，我们可以知道每一个的回路都在某一个包含它的 强连通予图中，而且在不同的s c c 中的回路不可能有交集。 因此我们可以首先把电路划分成各个s c c ，然后在各个s c c 中选择回路 作为计算状态密度的回路 为了找电路的时序回路，首先应当建立电路的s 一图。根据电路获得电路 的s 一图，我确定了一种深度优先的堆栈式的算法其基本思想是从一个触发 器的d 端出发进行回朔，具体算法如下： 1 在所有d f f 和组合器件加一个器件集