（计算机系统结构专业论文）集成电路寄存器传输级故障模型与测试生成研究.pdf

摘璺 摘要 随着集成电路设计技术的发展，其相应的测试也变得十分重要。测试 生成为测试过程中的一个重要环节本文首先综述了当前基于集成电路寄 存器传输级( r e g i s t e rt r a n s f e rl e v e l ，简称r t l ) 的测试生成方法和验证 方法。在此基础上给出作者所提出的r t l 测试生成方法，同时考虑到当前 r t l 测试生成的困难在于缺少有效的故障模型，本文还给出了r t l 故障模 型分析方法。本文工作主要体现在以下三个方面： 1 兼顾r t l 代码内部分技的状念测试生成。本文在状态覆盖的基础 上，给出一种虚扩展状态转换的方法，该方法将状态转换同其内部分技有 效的结合在一起。在此基础上再进行状态覆盖测试生成，生成的测试向量 可以实现对r t l 代码内部分枝的覆盖。结合提出的这种方法，选用了部分 i t c 9 9 一b e n c h m a r k 电路进行了相关实验，给出了实验数据和相关分析，与 v t g 比较，比v t g 生成的测试向量要少一半，而覆盖率平均以后大致相 等。 2 基于遗传算法的时序电路测试向量生成文中引入遗传算法，并以 状态与状态转换为评估。引入静态状态转换( 图) 及动态状态转换( 图) 的概念。给出了静态、动态状态转换的三个基本属性。在此方法的基础上， 给出了实验数据，并将结果x p u l l i n g 系统作比较比较的结果说明：在 覆盖率相近的情况下，比x p u l l i n g 运行速度快一个数量级 3 r t l 故障模型分析。本文针对r t l 故障模型进行分析，分析它与门 级固定型故障模型之间的关系；r t l 故障模型之间的关系。给出了一些基 本概念和定义，依掘这些概念和定义又推导出一些推论在上述分析的基 础上，给出了这些分析的一个应用：r t l 故障模型序列的寻找及建立。通 过分析不同r t l 故障模型间的关系，寻找互相不能完全覆盖的r t l 故障模 型，并将它们作为一个序列用于指导进一步的r t l 钡, 9 试生成同时，使用 三个故障模型作例子，说明该方法、过程。模型序列对于寻找有效r t l 故 障模型是十分有帮助的 关键词：集成电路，有限状态机，测试生成，寄存器传输级，故障模型 中田科学院博卜论文：集成f 乜路r t l 故障模型与测试生成研究 r e s e a r c ho nr t lf a u l tm o d e l sa n dt e s tg e n e r a t i o n r a n gx i u t a o ( c o m p u t e ra r c h i t e c t u r e ) d i r e c t e db yl ix i a o w e i a b s t r a c t i n t e g r a t e dc i r c u i t ( i c ) t e s t i n gp l a y sa ni m p o r t a n t r o l eo ng u a r a n t e e i n g r e l i a b i l i t yo fc i r c u i t t h eg r o w i n gc o m p l e x i t yo fl c si sb r i n g i n gab i gp r o b l e m t oc i r c u i tt e s t i n g t e s tg e n e r a t i o ni sa ni m p o r t a n tp a r to ft e s t i n g t h e o r ya n d m e t h o do ft e s t i n ga r ef i r s t l ys u m m a r i z e d s o m em e t h o d so fr t lt e s t i n ga n d m o d e la n a l y s i sa r ea l s op r e s e n t e dj nt h i sd i s s e r t a t i o n m a i nc o n t r i b u t i o n sa r el i s t e da sf o l l o w s 1 a na p p r o a c hi sp r e s e n t e dt oc o v e ri n s i d eb r a n c h e so fs t a t e s t oc o v e r i n s i d eb r a n c h e so fas t a t e s t a t et r a n s f e rt o k e n sw e r ei n s e r t e di n t ot h ec o d e o r i g i n a lt r a n s f e rb e t w e e nt w os t a t e s i se x t e n d e dt os e v e r a lo n e s s o t e s t p a t t e r n sg e n e r a t e db a s e do nt h em o d i f i e dc o d ec a n c o v e ri n s i d eb r a n c h e so fa s t a t e af o r m a i d e c e p t i o n i s p r e s e n t e dt oe x p l a i n t h i s a p p r o a c h t h i s d i s s e r t a t i o na l s op r o p o s e sa na l g o r i t h mt og e n e r a t et e s tp a t t e r n t r a v e r s a lo f d i r e c t e ds t a t eg r a p hc o u l dh e l pt oc o l l e c tp a t t e r n st h a tc a nt e s ts e q u e n t i a l c i r c u i t e x p e r i m e n tc o n d u c t e do ni t c 9 9b e n c h m a r kr e v e a l st h a tt h i sm e t h o d i sm o r ee f f e c t i v e i ta c h i e v e st h es a m ec o v e r a g ea sv t gi n a v e r a g e f u r t h e r m o r e ，t h el e n g t ho fg e n e r a t e dt e s ts e q u e n c ei sr e d u c e db y5 0 2 m e r i ta n ds h o r t c o m i n go ft r a d i t i o n a ls t a t e sc o v e r i n gm e t h o da n dg e n e t i c m e t h o da r ea n a l y z e d an e wg e n e t i cs e l e c t i n ga p p r o a c hi sp r e s e n t e dt o o v e r c o m et h es h o r t c o m i n go ft h e s et w om e t h o d s f i r s t ，i tc a nb ei m p l e m e n t e d a tr t o l e v e l s e c o n d 。i tu s e ss t a t ec o v e r a g ea sf i t n e s sf u n c t i o n ，w h i c hi su s e f u l t ot e s tt h ec o n t r 0 1 p a r to fc i r c u i t t h i r d ，i tc a nt e s tc o n t r o lp a r ta n dd a t ap a r to f ac i r c u i ta tt h es a m et i m e c o n c e p t sa b o u td s t ( d y n a m i cs t a t et r a n s f e r ) a n d s s t ( s t a t i cs t a t et r a n s f e na r ea l s ob r o u g h tu pi nt h i sd i s s e r t a t i o nt od i r e c t t p g ( t e s tp a t t e r ng e n e r a t i o n ) b a s e do nt h i sa p p r o a c h a na t p gt o o in a m e d g r t ti sd e v e l o p e d e x p e r i m e n t a lr e s u l t sf o ri t c 9 9b e n c h m a r k sd e m o n s t r a t e t h a tt h ep r o p o s e dm e t h o dc a ns p e e du px p a l l i n gb ym o r et h a nlo r d e ro f m a g n i t u d e 3 t h e r ea r en oe f f e c t i v ef a u l tm o d e l sd e f i n e da th i g hl e v e l t os o l v et h i s p r o b l e m 。t w ok i n d so fr e l a t i o n s h i p s b e t w e e nd i f i e r e n tf a u l tm o d e l sa r e a n a l y z e d r e l a t i o n s h i pb e t w e e nah i g h - l e v e lf a u l tm o d e la n ds t u c k a tf a u l t m o d e l ( d e f i n e da tg a t el e v e l ) i sa n a l y z e d ，f o l l o w e db ya n a l y s i so fr e l a t i o n s h i p b e t w e e nt w oh i g hl e v e lf a u l tm o d e l s t h e s er e l a t i o n s h i p sa r e e x p e c t e dt o f o u n do n eo ras e to fe f f c c t i v e h i g h - l e v e lf a u l tm o d e l s h i g h 1 e v e lf a u i t m o d e l sf o u n d e da r ee x p e c t e dt od i r e c ta t f g ( a u t o m a t i ct e s tp a t t e r ng e n e r a t i o n ) a n dd f t ( d e s i g nf o rt e s t ) m o r ee f f e c t i v e l yt h a nt r a d i t i o n a lo n e s e x p e r i m e n t c o n d u c t e do nb e n c h m a r ko fi t c 9 9d e m o n s t r a t e st h i sa p p r o a c h t h r e ek i n do f h i g h 。l e v e lf a u l tm o d e l sa r ea n a l y z e d ，t r a n s f e rf a u l tm o d e l ，s t a t e sf a u l tm o d e i a n db r a n c hf a u l tm o d e l k e y w o r d s ：i n t e g r a t e dc i r c u i t s ，f i n i t es t a t e sm a c h i n e ，t e s t g e n e r a t i o n ， r e g i s t e rt r a n s f e rl e v e l ，f a u l tm o d e l 血 声明 声明 我声明本论文是我本人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，本 论文中不包含其他人已经发表或撰写过的研究成果。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示了谢意。 作者签名：忆易告 日期：彩一4 川a 论文版权使用授权书 本人授权中国科学院计算技术研究所可以保留并向国家有关部 门或机构送交本论文的复印件和电子文档，允许本论文被查阅和借 阅，可以将本论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编本论文。 ( 保密论文在解密后适用本授权书。) 作者签名：怡j 哆如导师签名：矧日期砰4 目即日 第一帝哼i 刍 第一章引言 集成电路自从出现就大大改观了社会生活，并进一步地促进了社会的 发展从早期的第一个集成芯片4 0 0 4 的出现，到今天的c p u 以及诸多应 用于其它方面的集成电路如：m p 3 、机顶盒等，集成电路的集成度已非昔 开可比。但足一个问题也日益突出起来，那就是：如何保证更大集成度的 电路能够正确、可靠地工作。这个问题，不仅涉及到电路的设计，更涉及 到电路的验证与测试等 1 1 概况 对上述问题的回答基本上有两种途径：验证( v e r i f i c a t i o n ) 与测试。无 论是验证还是测试都是基于一个目的：尽可能的发现电路设计或成品中的 错误( 如果存在的话) ，以此来提高最终产品的可靠性。随着研究的进展， 已有许多方法被提出，但是研究者也渐渐认识到这个问题的难度。那就是 集成技术的发展，使得电路的规模过于庞大，相应的测试、验证难度增加 的更快而且，目前测试费用也很高，部分集成电路的测试费用已占到其 整个费用的3 0 还多因此，如何能提出更有效的验证、测试方法一直是 学术界执着追逐的问题。 从集成电路的设计、测试的整个过程来看。由于相关e d a ( e l e c t r o n i c d e s i g na u t o m a t i c ) t 具的出现，电路的设计过程被大大加快，而且工具的 可靠性逐步提高但是另一方面，对电路进行验证、测试的自动工具却相 当有限。目前，已有的_ 些验证工具对电路的规模有着限制，对超大规模 的集成电路进行验证时，或者耗时太长，或者无法实现而测试工具则更 为有限，已有的工具一则测试生成的时间较长；二则，对相应故障的覆盖 率低。因此，与电路的设计相比，电路的验证与测试难度要大很多，而且 要做的工作也很多。 从测试的角度来看，我们要设计一种集成电路产品、组装并测试它。 假如该产品没有通过测试，那么就可能是由如下原因引起： 测试过程有错误 生产过程中出了问题 设计有误 中闺 i 学院博i 论文：集成i 乜路r t l 敞障模型j 劂试生成研究 需求有问题 由此，可见正确有效的进行测试是十分重要的。如果测试过程足对的， 那么我们就可以怀疑是生产、设计和需求的问题 图1 i 芯片设计沉程图 从电路的整个设计流程来看( 图1 1 ) 。它主要分为以下几个步骤：系统 需求、结构需求与设计、行为级或r t l 设计、综合、仿真、投片生产等。 从电路设计的层次上来分则划分为6 级【王0 2 】。最高层次为系统级，最低 层次为版图级( 又称物理级) 。硬件设计方案可以在任何层次描述。对于设 计层次最低的版图级，其用几何图形描述硬件，即用硅表面上的扩展区、 多晶硅和金属来表示硬件。在这一次层，硬件的描述只是结构，而硬件的 功能则隐含在器件的物理方程中版图级之上为电路级电路级用有源器 件和无源器件的互连关系描述硬件电路级之上为逻辑门级( 本论文中如无 特别说明，简称门级1 ，这是数字系统设计的主要层次在门级设计时，电 路的基本单元通常是与门、或门、异或门、反向器等逻辑门，有时还带有 少量的晶体管构成的开关以及d 触发器、j k 触发器、锁存器等逻辑单元。 在这一层次。基本的时序单元足时延。门级之上的层次是r t l 。r t l 最基 本的设计单元是寄存器、计数器、多路选择器、算术逻辑肇元( a l u ) 等。 r t l 设计的基本单元也可以继续展开成基本逻辑门，但在r t l 设计时通常 不作这种展开，而是把它们作为整体处理。r t l 之上足行为级，也称为算 法级在该层次，设计由运算步来描述这一层次的典型描述方法是行为 有限状态机( b f s m b e h a v i o r a lf i n i t e s t a t em a c h i n e ) 、控制流图( c f g c o n t r o lf l o wg r a p h ) 、数据流图( d f gd a t af l o wg r a p h ) 以及控制数据流图 ( c d f g c o n t r o ld a t af l o wg r a p h ) 设计的最高层次是系统。在系统级，行 2 第一帝0 i 等 为描述的内容通常为二- 些性能指标。 对应于集成电路的设计层次，验证测试大致分为如下几层：从系统级 到行为级级转换的验证，这一阶段为需求验证；从r t l 到门级转换( 综合) 的验证。这一阶段为功能一形式验证：从门级到物理版图的验证，这一阶段 为结构一功能故障测试可以看出，在设计的整个过程中验证测试贯彻始终 集成电路的验证分为形式验证与模拟验证形式验证提出于2 0 世纪9 0 年代。其涵义是：用形式的方法来确立设计的实现满足规范的要求。所谓 的实现是指硬件在任何不同抽象层次的设计，不仅仅指最终的物理版图， 例如系统级，r t l ，门级，晶体管级等等所谓的规范是指设计所期望的 并被认为是“正确”的属性，通常用形式化的方法来描述形式验证的任 务是提供证明，以便确立实现满足规范的要求，证明采取形式化的、数学 的严格证明主要包括【邵0 4 】：定理证明，模型检验、等价性检验、语言包含。 用形式验证方法来对电路进行验证的最大优点是可信度比较高，一般经过 严格形式验证为无误的电路，正确的可能性大大提高。但是一个很大的缺 点是其时间复杂度高其所面临的一个困难是“状态爆炸”的问题。虽然 有些方法可以尽可能的避免，但所能处理的电路规模比较小。模拟验证的 方法是一种比较直接的方法，也是常用的方法。其基本思想是生成激励( 如： 随机生成测试向量) 对电路的运行进行模拟仿真。模拟验证的优点是比较直 接，容易理解，而且现在随着电路规模的增大，越来越依赖于这种方法。 但是其可靠性不高，虽然容易发现电路中的明显故障或错误，但是对于一 些比较隐蔽的故障或错误的测试能力有限对于整个验证来说，最直接的 方法莫过于穷举，但这有困难，因为当电路的规模很大时，穷举的复杂度 太高，因此不便直接采用 对于电路的验证，无论是形式验证还是模拟验证都面临着一些待解决 的问题，而且这种验证工作量比较大为了减少测试的压力，人们提出了 可测性设计 杨9 8 】 一般来说，可测性设计一定会增加硬件的开销。在这方面有两种基本 策略，一种是为了获得最大的可测性而不惜成本地进行设计；另一种是希 望采取一些切实有效的方法，增加少量或有限的硬件开销来提高系统和电 路的可测性这两种策略是根据不同的测试要求来确定的同时考虑到硬 件复杂度往往会降低可靠性。因此在实际进行可测性设计时还要考虑到可 靠性的要求。可测性设计方法分为两大类：一类是专项设计，即按功能基 3 中固科学院博 论文：集成i 乜路r t l 故障模型与删试生成研究 本要求设计系统和电路，采取一些比较简单易行的措施，使它们的可测性 得到提高；另一类足结构设计，它足根据可测性设计的一般规则和基本模 式来进行电路的功能设计 目酊这种可测性设计大多是基于硬件描述语占来进行的。或者说是在 r t l 或行为级进行的其主要方法有：测试点插入、内建电路自测试( b i s t ， b u i l ti ns e l f t e s t ) 、扫描设计等。不同的方法针对点也不同。测试点插入 足为了提高电路的可测性；增加内建电路自测部分是为了实现部分电路的 自测，如：存储器内建自测( m b i s t ，m e m o r yb u i l ti ns e l f t e s t ) 就是实现了 对集成电路块中的m e m o r y 块的自测试 杨0 3 】；而扫描设计则是针对时序电 路进行的时序电路的测试是电路测试中的一个难点，尽管时序电路又可 分为同步时序电路和异步时序电路，但是异步时序电路的测试十分的困难， 所以在一般的设计中尽量避免使用该类型电路。对于测试来讲，也主要是 针对同步时序电路【m i z c 8 3 】，总体来讲，目前对时序电路并没有什么好的 方法，主要是使用扫描电路设计( s c a nd e s i g n ) 方法。这种方法不仅使时序 电路的测试得到简化，同时使电路能够自检，从而大大提高电路的可靠性。 扫描设计的主要思路是将电路中的组合元件与时序元件分开，其中组 合电路用其它方法来测试，而其中的时序元件被串接成移位寄存器形式， 以便把测试信号移入时序元件内，也便于将时序元件的状态移出来，方便 观察 测试生成也是实现对集成电路测试的一种好方法使用这种方法，需 要生成测试，这些生成的测试或者基于某种故障模型，或者是无故障模型 基于故障模型的测试生成，是当前最常用的方法，针对电路的故障行为定 义一系列故障模型，针对这些故障模型预先生成测试，这些测试被施加于 电路之上，以检测是否覆盖到了所定义的故障如果对故障模型所定义故 障的覆盖率较高，被认为是一种成功的方法例如，对于门级电路，最常 用的故障模型就是固定型( s t u c k a t ，简称s a ) 故障模型( 本文后面一律 以s a 指代门级的固定型故障模型) ，s a 故障模型中又以单s a 故障( s i n g l e s t u c ka tf a u l t ) 模型最为有效。测试生成可以在几个层次进行，如在门级、 r t l 、行为级等无论是在哪个层次进行测试生成，其目的都很明确就是： 生成测试向量，对电路进行测试，尽可能使得电路正确 对于门级测试生成，其研究比较早目前相关的测试方法和故障模型 也比较多目前，最为常用的故障模型是单s a 故障模型这种故障模型是 4 第一帝0 i 苦 假设电路元件的连线，或者是认为某个电路元件的输入、输出上发生了固 定型故障，即线上的值保持为某种值，如0 或l ，不能随着要求而发生变化。 实践证明，这种假设的故障模型对于门级电路的测试十分有效，能够检测 到大部分类型的故障不仅如此，单固定型故障模型对多故障也有很好的 测试能力耳前，很多测试生成工具，如：m e n t o r g r a p h i c s 公司的e d a 工具 就支持该故障模型。当然，除了单s a 和多s a ( m u l t i p l es t u c ka tf a u l t ) 故障 之外，还有一些其它类型的故障模型，如：桥接故障【m e i y 7 4 】【m i l l 8 8 】，它 是假设电路内部的连线发生了短路 对于r t l 和行为级的测试生成，目前还不够成熟，不过也集中了一些 研究成果，给出了一些方法r t l 与门级之间的区别在于，它们之问有一 个综合过程。r t l 或行为级是代码描述，它与实际的电路还有很大的差距， 与实际物理电路差得更多。所以在该类层次的测试生成存在一些欠缺。同 门级的测试生成也是一样，r t l 测试生成也分为有故障模型和无故障模型 两种。无故障模型是从电路的行为着手，更接近于功能测试。有故障模型 方法则是在r t l 假设一种或一类故障模型，依据该故障模型生成测试。遗 憾的是，目前对该层故障模型的研究还不足，业界还不能给出一种恰当的 故障模型，用以准确描谜该层的故障加之，该层距离物理电路在设计上 远，其生成的测试对芯片的测试能力有待提高所以，当前有很多工作是 基于对r t l 或行为级的故障模型的研究而展开的。 另一方面，在r t l 或行为级做测试有很多的优点：及早的发现电路设 计的错误，便于及时的进行修改；r t l 或行为级相比较门级而言，电路还 没有被完全展开成逻辑门的互连，所以其规模相比较而言还小；r t l 或行 为级尚属于代码级，一经发现错误修改起来比较容易，对于一些使用测试 方法无法检测到的故障或局部电路单元，还可以选择可测性设计来解决。 总之，集成电路的验证与测试具有非常重要的意义，它关系到最终产 品的可靠性，也关系到设计结果的成败而在电路的r t l 或行为级做测试 生成，又可以使得对电路的测试更提前一个阶段，便于及早的发现错误以 进行及时的修改与补救。 1 2 研究背景 从电路设计的层次上来看，对于门级电路的测试生成研究比较成熟， 5 中困科学院博t - 论文：集成l u 路r t l 敞障模型。j 删试生成研究 已有大量的方法被提出，理论也比较完善，已经被工业化由于电路本身 分为组合逻辑电路与时序逻辑电路，而在设计层次上又有许多划分，因此， 测试的研究涉及面比较广，从总体上来看，主要集中于以下几个方面 组合电路的门级网表测试生成，组合电路的测试生成是该领域最早被 研究的内容最容易想到方法，当然足穷举法：一个具有n 个原始输入端 的组合电路实现逻辑功能f 伍) ，而原设计的逻辑功能为f ) ，如果对于 任何胛维向量置，有 f 伍) - f ) ( 1 i ) 那么认为所设计的电路足正确的，或者说足无故障的但是，对于一个，l 维 向量来说，x = k ，屯，) ，其中，f 一1 , - - - 以均有两种取值：0 r l ，这样就 会有个向量。当n 比较大时，这是一个非常庞大的数目。以一个6 4 位进 位加法器为例，从功能测试的角度，有其1 2 9 个输入和6 5 个输出。因此，要 完全地执行功能测试就需要2 ”个输入向量并同时生成个输出响应。设 一个自动测试仪( a t e ，a u t o m a t i ct e s te q u i p m e n t ) - i - 作频率为l g h z ，那么施 加完整个向量集需要2 1 5 8 0 5 6 6 1 4 2 1 0 ”年 尹0 3 】，因此在实际应用中有困 难。为了使得穷举法有实用价值，一些学者又提出了伪穷举【a r c h 8 4 】此 外，还有布尔差分法等这类方法的优点是，不需要已定义好的故障模型， 即可实现对电路的测试，从根本上来说属于“功能测试”，而功能测试便是 要为待测电路生成完全测试集，其实用还有限。 第一个具有启发意义的算法是r o t h 的d 一算法，其首先开了使用d 一立 方建立a t p g 算法的先河d 算法中两个主要的操作是：激活、传播所 谓激活就是指激活故障，传播是将故障所生成的错误沿一定路径传播至原 始输出。因此，这是一种典型的路径敏化( p a t hs e n s i t i z a t i o n ) 类方法。d 算 法解决了组合电路的单s a 故障的检测【h a y e 8 5 ，而相关的研究还说明， 对该类故障的检测，同时还可以检测到大多数的多s a 故障 i h u g h 8 6 儿h u g u 8 4 】 理论上，对于任何非冗余组合电路，d 算法均能为任意单s a 故障找到 6 第一节嵋l 高 测试，但由于其在进行敏化通路的选择时随意性太大，因此会使得相当一 部分选择失败，只好进行回溯。这些大量的回溯，对d 算法的效率有很大 的影响在d 算法的基础上，【g o e l 8 1 l 提出的p o d e m 算法和【r n j i 8 3 1 提出的 f a n 算法均是要尽量避免测试生成过程中的选择回溯。除了面向故障模型 的测试生成方法以外，还有一些是无故障( 也称故障独立) 的测试生成方 法，如临界通路方法总的说来组合电路在门级网表这一层的测试生成研 究已经很成熟。 时序电路门级网表的测试生成虽然时序电路包括同步时序电路与异 步时序电路，但异步时序电路的测试比较困难，所以在设计时都会尽量使 用同步时序电路如果设计中存在异步时序电路，对它测试也一般是采用 可测性设计方案。因此，本文主要讨论同步时序电路的测试生成。 图1 2 时序电路示意图 一个同步时序电路是由组合电路和触发器共同组成。如图1 2 所示： 组合逻辑电路的一些输出为触发器的输入，而触发器的输出又为该组合逻 辑电路的输入。图中的黑线表示一组信号。由图中也可看出，组合逻辑电 路的输入分为两部分：外部输入，称为原始输入( p i ，p r i m a r yi n p u t s ) ；伪 原始输入( v p i 。p s e u d op r i m a r yi n p u t s ) ，或称为当前状态，由触发器提供。 同样地，组合逻辑电路也有两种输出：外部可以观察到的部分，称为原始 输出( p 0 ，p r i m a r yo u t p u t ) ；送往触发器的部分，称为伪原始输出( p p o ， p s e u d o p r i m a r y o u t p u t ) 或称为下一状态因此，对于一个时序电路，输入 向量被施加于其原始输入，在其原始输出可以观察到结果但是，由于缺 少对p p i 和p p o 的直接连接，使得对组合逻辑的检测也变得困难起来。目 前，对于时序电路的测试方法主要有以下几种： 时问帧展开方法：为了将组合电路的a t p g 算法应用于图1 2 所示的时 序电路中，我们必须知道组合电路与时序电路之间的基本区别：第一个区 别就是为了检测到时序电路中的一个故障需要多个测试向量，或称为测试 向量序列，而对于组合电路来说，要检测到一个故障，只需一个测试向量 7 中国科学院博t 论文；集成i 乜路r t l 故障模! i ! j 测试生成研究 即可；第二个区别在于对时序电路中触发器的初始化。组合电路中常用的 a t p g 算法，如5 值逻辑，对组合电路非常有效，但对于时序电路却常常无 效。因此，对时序电路进行测试时，通常使用9 值逻辑。在此基础上，将 时序电路按时问帧展丌，如图1 3 所示展刀：以后，每一帧( 除第一帧外) 的输入均为上一帧的输出，每帧( 最后一帧除外) 的输出又为下一帧的输 入。每一帧均为一个组合电路。可以使用组合电路的测试尘成方法生成测 试序列。对于一个位于第t 帧的故障，要想检测到它，测试向量显然必须 要经过k j 帧才能到达它，所以其测试向量序列应该至少包含k 个向量 ( 可能还需要初始化向量，所以说至少为k ) 这样一来，电路的规模被扩 大了很多，如果测试生成算法本身就需要很多回溯，那么对整个电路进行 测试的复杂度会很高。对于这样的展开，一个重要的问题就是如何初始 时b 】 图1 3 时序电路按时问帧展开 化? 如果电路本身不具有自初始化功能，那么就必须由测试者提供相应的 测试向量来对电路进行初始化，不过在一般的设计中，大都会提供复位 ( r e s e t ) 功能该类方法的代表系统为g e n t e s t f b e n c 9 1 】【c h e n 8 9 】，它是 由b e l ll a b s 开发的时序电路测试生成系统，为了避免系统进行过量的计 算，其限定了为每个故障生成测试向量的时间，这样就提高了系统运行效 率，不过也使得许多难测故障可能无法被检测到。另一个系统是由l l l i o n i s 大学开发的h 1 t e c n i e r 9 1 】，它把帧的前、后向扩展结合起来，分别进行 故障的激活和故障效应的传播，同时，为了提高运行效率还使用了并行故 障模拟器f n i e r 9 2 1 。 基于模拟的方法：使用故障模拟器束进行测试生成最先是由s e s h u 和 f r e e m a n 在上个世纪6 0 年代提出的将随机向量生成与故障模拟相结合进 行测试生成是在上个世纪7 0 年代被提出的首先随机生成向量，然后故障 模拟器只选择那些能提高故障覆盖率的向量以使为测试生成的结果虽然 该方法对一些组合电路的测试生成效果不错，但对一些算法上需要回溯的 8 第一帝i 者 电路，效果不佳【b r e u 7 1 专门为时序电路给出了一种基于模拟的方法， 它将向量的选择集中在某个“当前状态”【s c h u 8 8 又给出一种并行故障 模拟器( c f s c o n c u r r e n tf a u l ts i m u l a t o r ) 使用模拟方法的优点在于：在一个向量被选为测试向量之日i ，首先对 它进行模拟。一个事件驱动的模拟器不仅分析了电路的逻辑，也分折了电 路的时序，被选中的向量能够保证不受冒险与竞争的影响。 后来，遗传算法( g e n e t i c a l g o r i t h m ) 也被引入该方法之中【g o l d 8 9 】 【m a z u 9 9 儿p r i n 9 4 a l p r in 9 4 b 】【r u d n 9 4 l 【s a a b 8 2 】遗传算法的优点在于它的 向量是随机生成的，只要评估函数定义好，就可以进行向量的筛选。缺点 是遗传算法本身就存在着效率与质量的权衡问题，要提高效率，很多时候 不得不对所生成向量的质量有所让步反之，若要提高质量，就会牺牲效 率。基本模拟方法的代表系统是c o n t e s t 【a g r a 8 9 】。 由于当前电路规模的增大，有很多研究倾向于在r t l 或行为级做测试 生成。相比于电路的门级，r t l 或行为级为高层描述，其规模小，一般在 该层作验证会取得比较好的效果，而且这也是目前设计验证的主流工作 但也因为该层规模小，将测试生成引入到该层也能取得不错的效果，另外 在该层做测试生成复杂度会相应的低些目前的研究主要有： 与门级电路有些不同，r t l 或行为级又是代码级，所以有一些测试生 成方法是借用了软件测试的思想。此类方法基本上是白盒测试方法和黑盒 方法。黑盒测试对应于r t l 或行为级的功能测试，最直接的方法是穷举法， 但是这对于规模大的电路根本不现实，时问和空间上都不允许故有一些 变形的方法被提出来，避开对向量空问的全部枚举，只进行部分的测试， 只求达到一个可以接受的覆盖率即可。 自盒测试对应于r t l 或行为级的结构测试。大多数的测试生成是基于 这种方法的，虽然它的覆盖率难以达到1 0 0 ，但是其效率相对于枚举来讲 却要高很多，精心设计一些测试方法，也可以达到一个很高的覆盖率，而 时问上又可以接受。 由于在r t l 验证方法的发展，也带动了该层测试生成的研究。这些方 法的基本思想就是基于约束生成测试。为一些语句或是判断条件产生约束 表达式，在处理的过程中对循环语句作了简化以方便约束表达式的产生。 然后使用b d d 或s a t 生成向量1 9 9 8 年由f a r z a nf a l l a h ，r i n i v a sd e v a d a s ， k u r t k e u t z e r 提出的【f a l l 9 8 】，该方法也是针对h d l 模型的。由z h i h o n gz e n g ， 9 中国科学院博i 论文：集成l u 路r t l 故障模型j 测试生成研究 p r i y a n kk a l l a ，m a c i e jc i e s i e l s k i 发表的【z e n 9 0 1 l 等。l p s a t ：使用约束方法 进行测试尘成的一个系统，出c o m p u t e rs c i e n c e e n g i n e e r i n g u n i v e r s i t y o f w a s h i n g t o n 丌发，是l i n e a rp r o g r a m m i n g 与s a t 的一个融合 当然，也有面向故障模型的方法。这类方法是借用门级测试生成方法 中的思想，寻找寄存器传输级或行为级中的可能故障，构造一种或几种故 障模型，针对这些故障类型来产尘测试向量。这种方法采用的也有一些， 比较典型有方法是1 9 9 9 年由y i o r g o sm a k r i s ，a l e x o r a i l o g l u 提出 的【m a k r 9 9 】同时也有对这类模型进行比较分析的研究工作。如；o g o l o u b e v a ，m s o n z ar e o r d a ，m v i o l a n t e 的研究工作【g o l 0 0 2 a l f g o l 0 0 2 b 1 ， 文中通过实验分析的方法对各种故障模型进行比较，以确定确实可行的或 是比较有效的故障模型。【尹0 3 】定义了一种传输故障模型，并在此故障模 型基础上作测试生成，取得了不错的效果，但该方法面临的问题是：时序 电路需要按时间帧展丌，这种展开需要耗费大量的存储空问。受门级s a 故障的启发，在【c h e n 9 8 】中给出一种变量固定型故障模型，并在此基础上 作测试生成，效果不错。这类方法的优点在于有很强的针对性，同时，又 由于是结构测试，所以其效率都比较高。缺点在于：首先，受所定义故障 模型的影响，故障模型定义的好，效果也好，但是如果故障模型定义的不 好，则所生成的测试向量的质量就很低。而如何给出一种有效的故障模型 却是一个困难的事情f g o l 0 0 0 2 a l g o l 0 0 0 2 b 由于在寄存器传输级，难于找到一种很有效的故障模型，所以一些研 究则先用了基于模拟的方法论文f 高0 4 1 在分析时序电路特征的基础上， 给出一种基于时问深度的测试生成方法该方法充分考虑了时序电路与时 序有关的特性，但是由于在测试生成过程中只集中于对时序的考虑，所以 其测试生成的效果不甚很好遗传算法也被引入寄存器传输级的测试生成 中【c o r n 9 6 a 】【c o r n 9 6 b 】【c o r n 9 6 c 】【c o r n 9 7 】，这种方法的优点在于使用遗传 筛选可以避免故障模型的困扰，但是缺点是仍然要用到单s a 故障列表。【李 0 2 】则尽可能地融合了上述几中方法，它的基本思想足对状态问转换进行 聚类，将相同转换条件的状念划为一类，集中根据约束生成测试向量。 1 3 论文的组织 总的来看，寄存器传输级或行为级的测试生成有待于作进一步的研究 1 0 第一节0 i 言 本文内容共分三部分：考察代码内部分枝的状态覆盖测试；基于遗传算法 的测试生成及r t l 故障模型分析。 状态覆盖测试对时序电路的r t l 测试生成是比较有效的，但是传统的 状态测试生成存在一个缺点，只考虑状态和状态问转换的测试。为解决该 问题，可以将针对状态的测试尘成与针对分枝的测试生成分开进行，但是 这样会使的测试生成的复杂度升高，如果状态数比较多，所需的计算开销 就会比较大，本文在状态测试生成的基础上，给出一种虚扩展状态转换的 方法，该方法将状态转换同其内部分技有效的结合在一起。原来的状态转 换中，从一个状态到另一个状态，可能只有一个或几个状态转换而这些 转换并不包含上一状态内部分枝信息。通过在每一状态内部的分枝节点处 增加一个虚状态阶段变量赋值语句，可以虚增加一个状态转换。对应于状 态转换图而言，则就增加了一个有向边。这样，扩展以后的状态转换图中， 每一个状态转换边都包含了一个内部分技信息及内部分枝上的约束条件。 在此基础上再进行状态测试生成，实现对r t l 代码内部分枝的测试。 确定的状态覆盖向量生成方法，基本可以实现对控制流图中状态及状 态转换的覆盖，而随机方法可以实现对数据流图的测试不足的是，随机 方法太过于盲目，所生成的数据量又太多，为了解决该闯题，我们引入遗 传筛选，并以状态与状态转换为评估依此方法所选择出的向量具有以下 优点：对状态及状态转换的覆盖率比较高，其中状态及状态转换反映了电 路的控制部分的内容，也就是说对控制部分的测试比较好；具有随机测试 向量的优点，可以同时实现对数据部分的测试 针对r t l 故障模型进行分析，分柝它与门级s a 故障模型之问的关系； r t l 故障模型之间的关系文中给出了一些基本概念和定义，依据这些概念 和定义又推导出一些推论。在上述分析的基础上，给出了这些分析的一个 应用：r t l 故障模型序列的寻找及建立。通过分析不同r t l 故障模型间的关 系，寻找互相不能完全覆盖的r t l 故障模型，并将它们作为一个序列用于 指导进一步的r t l 测试生成 第二学生成i 乜路验证j j 铡试综述 第二章集成电路验证与测试综述 集成电路的验证与测试是两大研究重点验证有助于对不同层次的设 计结果进行比较，以找到设计及层次转化之间的问题，一旦发现电路中的 错误可以及时的修改；同时，将所得电路与j 下确电路比较也可以发现设计 中的错误。从方法的角度上，验证分为形式验证与模拟验证。相比较而占， 形式验证在理论上比较成功，但是在实际应用中受电路规模等因素制约， 其应用有限。测试的研究重点是测试生成，测试生成过程为待测电路生成 测试向量，用所得向量作为激励来检测电路中可能存在错误。事实上，无 论是验证还是测试，都是基于两种方式：基于结构的验证或测试；基于功 能的验证或测试。在本章中主要概述形式验证、模拟验证及测试生成方法 2 1