（计算机系统结构专业论文）基于相容类加权的扩展相容性扫描树构造算法研究.pdf

颂士学位论文 摘要 如今，数字系统已经广泛应用于生活中的各个角落。而对于各种数字系统，集成电 路是其中最关键的部分。近几十年来，随着超大规模集成技术的迅猛发展，芯片中晶体 管的密度成指数倍增长。集成电路的测试日益成为一个挑战。全扫描设计是最重要的可 测性设计方法之一，但是全扫描设计存在测试应用时间过长的缺陷。为了解决这一个问 题，国内努学者已经做了很多研究，但是都鲅多或少存在着某些局限性。 本文首先介绍一些与测试相关的基本概念，阐述扫描设计的主要思想和基本原理， 总结现有基于扫描设计的各种技术，并指出各自的优缺点和适用性。 其次，本文对扩展相容性扫描树结构进行详细介绍和分析。该技术通过添加逻辑非 和异或函数扩展了扫描单元的相容性，并对相容的扫描单元扫描移入相同的测试数据， 降低了扫描链的长度。与以往的扫描树技术相比，扩展相容性扫描树结构在降低测试应 用时间、测试数据量和测试功耗方面具有较大优势。但是该结构的扫描树构造算法使得 电路中大部分韵扫描单元都集中在几个楣容类中，导致扩震相容性扫描树的扫描输出楣 对较多。 针对现有扩展相容性扫描树构造方法所存在的问题，本文首先提出了两条减少扫描 输出的规则和一种基予相容类加权的扩展相容性扫描树构造算法。在不降低故障覆盖率 的前提下，两条规则有效地减少了扫描树的扫描输出，且不会增加扫描树的层数。通过 对扫描单元设置权值，加权算法使得扫描单元较平均地分布在各个相容类中，减少了扫 描树的层数和扫描输出。算法计算量相对较小，能较好地满足实际应用的要求。实验数 据表明，利用该算法构造的扫描树比原始扩展相容性扫描树的层数平均减少8 5 ，扫 描输出的个数平均减少3 0 4 ，极大地降低了测试应用时间和硬件开销。然艨本文对加 权算法做出了进一步的改进，在如何选取扫描单元生成相容类以及如何生成异或类这两 个方面对算法进行了补充。实验数据表明，利用改进算法构造的扫描树比改进前层数平 均减少8 7 ，扫描输潦的个数平均减少7 。9 。 针对扩展相容性扫描树结构，本文加权算法能有效地生成层数较少且扫描输出也较 少的扩展相容性扫描树，较好地满足了扫描设计中对于降低测试应用时间和硬件开销的 要求。 关键词：全扫描设计；扫描树：测试应用时间；测试数据量 基于相容类加权的扩展相容性扫描树构造算法研究 a b s t r a c t u pt o 瓣w 击爵ts y s t e m sa r ea p p l i 甜t oe v e r yc o 越e ro fo wd a i l yl i f e 淞t e 鲥甜e 主f c u i t s e r 垤sa s 也e 越o s i m 刺p a r 耋遮a l l 燃n d so fd i g 主ts y s t e m s hr e c e n ld e c a d e s ，姒m 也e r a p i dd e v e l o p m e n to fv e 搿l a r g es c a l ei n t e 铲a t i o n l s dt e c 埘q u e ，t 1 1 ed e n s 时o f 仃a n s i s t o r s i n c r e a s e sm 眦a t i c a n y ，h e n c em et c 蚰1 9i sb e c o i l l i n gah u g ec h a l l e n g e f u i l s c a nt e s t i n gi s o 糕eo f 谯e 壤建i 壤磷癯a 臻s i 蛰塔勤f 鼍e s 油i l 埘m 文h o 面l o 沓e s h o w e v e 毛i te o s t s 协。趱u 矗 t e s ta p p l i c a t i o nt i m e 。h lo r d e rt os o l v et h i sp b l e m ，l o t so fr e s e 粼h e sh a v eb e e nd o n ei l lt h e w o r l d ，b u tu 1 1 曲r t u 】删e l yw i ms o m e w h a tl 蛔j t a t i o 潞 髓畦st 量l e s i s 觚缱y 翻d u c e ss o m eb a s i cd e 蠡1 1 i t i o n sa b o u t t e s t i n ga n d 西籼r a t e st 董l em a 主n 西建e i p l e so f 辩a n 专e 姬n g h 蠢s os 蝴a 矗z e s 饿ec 戳羚越蚀e k o l o 垂e s 吞的毽s c a 疆绝羹攮g 强d p o i n t so u tm e i ra d v a m a g e sa n dd i s 缸l v a m a g e sa sw e l la st 1 1 e i ra p p l i c a b i l i 够 s e c o n d l y ，t l l es 仃u c 瓴胎o fe x t e n d e dc o m p a t i b i l i t i e ss c a n 仃e ei si l l u s 仃a t c d 1 1 1 i st e c h m q u e e x t e 瘫s 也ec o m p a t i b i l 戤o fs c a l le e l l s 妇o u 醢e 翻【p l q 河gl o g i cn o ta n dx o r 氛苴l c 矗o n s 。l l s l 娃f b 也es a m ed a 协i n 幻m e m 刚b l es c a nc e l l s 也a tt ：kl e l l g mo f s c a nc h 蔹ni sl 嚣g e l y m d u c e d c o m p a r e d 谢t ho m e rs c a n 协e et e c l l i l o l o g i e s ，t h i sm e t h o di ss u p e r i o ri nr e d u c i n gt h e t c s t 印p l i c a t i o nt i m e ，d a t av o l t l m ea n dt e s tp o w e r h o w e v e r ，i n 协i s 舭t i l r e ，m o s to ft l l es c a n l l se o l l e c 毫纽j 毽建s e v e f 蘸暇p 蠢i b l ee l i q 毽e s ，w 毯e h 愆s 珏l 鼍s 遮壤。您s c 强。脚越s i i lo m e rt 0s 0 l v e 也ep r o b l e m so fe x t e i l d e dc o m p a t i b l es c a i l 垤e ，l h e 也e s i sp r o p o s e s 抑o r u l e st 0r e d u c et l l es c a no u t p u t s 锄da ne x t e n d e dc o m p a t i b i l i 够s c a nt r e ec o i l s t r i j c t i o nb a s e do n w e i 出e dc o m p a t 主b l ee l i q u e s o nt h ep f e m i s e so fn o td e c 辩a s i n g 也e 纽懂t v e r a g e ，t h e 铆o r 蠢e s 聪d 醢c es c a no 瞧p u t se 懋e i 髭l l y 跹d 啾趣c r e 黟e 氆el a y e 懋。t k 粥i g h l e d 越g o 蠢囊m a v e r a g e l yd i s t r i b u t e sa l ls c a i lc e l l st ot 1 1 ec o r n p a t i b l ec l i q u e ss o 勰t or e d u c em el a y e r sa i l d s c a no u 印u t s e x p e r i m e n t a ir e s u l t ss h o w 也a tt h em l m b e ro fl a y e r sa v e r a g e l yr e d l l c e sb y8 5 c o m p a 托d 诵壤壤a 专o f 辨v i se x 专e n d 舔e o m p a 螽醚es c 鼹讯ea p p 馘毽a 稚凌。秘m b e fo f s c 姐。呦u _ 拯a v e r i 韵萨l yd e c r e a s e sb y3 0 4 1 ll a 毽e l y 捌u c e s 饿l e s ta p p l i c a t i o nt 蛔ea 芏l d h a r d w a o v e r h e a d i na d d i t i o m 也i st 王l e s i sf h r t h e ri l n p r o v e st h ew e i g h t e da l g o r i m ma b o u t h o wt os e l e c ts c a nc e l l sa l l dh o wt og e tx o r c l i q u e s e x p e r i i n e n t a lr e s 谢t ss h o wm a lt h e 矗憾b 嚣o fl a y e 落蠢e c l i 纛e s 酚8 7 髓i 鑫g 辔e 弧p v 甜。藏e 诚也也e 擞髓融o fs c 勰。域印t s d e c r e a s e sb y7 9 ，t h em e s i se m p l o y st 1 1 ew e i 曲t e da l g o r i t l l mw i l i c hc o n s t m c t sl e s s - 1 a y e ra n dl e s s o u t p u t e x t e n d e dc o m p a t i b i l i t i e ss c a l l 仃e e se 蔬c 畦v e l ys oa st or e d u c e 伽et e s ta p p l i c a t i o nt 矗n e 蠲d 魏鑫h 雠o v e 嫩e a 磊 k e y w b r d s ：m l l s c a nt e s t i n g ；s c 孤心；t e s ta p p l i c a 士i o nt m e ；t e s td a 妞v 0 1 啪e i l 硕士学位论文 插图索引 图2 1扫描设计工作框图9 委2 2d 触发器10 图2 。3 扫描单元。lo 图2 4 扫描设计方案1 l 图3 1正常相容和不相容的扫描单元1 4 图3 2 扫描树和扩展楣容性扫描树1 5 图4 1减少扫描输出规则l 。2 2 图4 2 减少扫描输出规则l 第二种情况2 3 嚣4 3 减少扫摇输出规则2 2 3 图4 。4 减少扫撼输出规则2 第二种情况2 4 图4 5 减少扫描输出规则2 第三种情况2 4 图4 6 贪婪算法生成的相容类2 6 图4 7 整体相容性较好的被测电路使用加权方法生成的相容类2 7 图4 。8 整体相容性较好的被测电路使用贪婪算法生成的相容类2 7 图4 9 整体相容性不好的被测电路使用加权方法生成的相容类2 8 图4 1 0 限制异或类中扫摇单元的数目2 9 图4 1l 优化扩展相容性扫描树。3 0 图5 1未对扫描单元包含x 进行排序所生成的相容类3 6 图5 2 对扫描单元包含x 排序后所生成的相容类3 7 图5 3 改进蓠掰生成豹扫描树3 8 图5 4 选取度较小的扫描单元所生成的扫描树3 9 图5 5 异或类不能再异或时所生成的扫描树。4 0 图5 6 允许异或类再进行异或所生成的扫描树4 0 图5 7 基准电路s1 4 2 3 的扩展相容性扫描树4 7 l 珏 基于相容类加权的扩展相容性扫描树构造算法研究 附表索引 表3 1 扩展相容性扫描树结构1 7 表3 2 扫描树前五层基本类所包含的扫描单元18 表3 3 扩展相容性扫描树结构的相容类1 9 表3 。4 扩展相容性扫描树结构的扫描输磁1 9 表4 1 两条减少扫描输出的规则31 表4 2 限制异或类中扫描单元个数3 2 表4 - 3 优化蜃的扫描树与未优化的扫描树结果比较3 2 表4 。4 加权扩展相容性扫描树构造算法与原始算法结果比较3 3 表5 1 按包含x 个数的顺序选取扫描单元4 2 表5 2 选取度较小的扫描单元组成异或类4 2 表5 3 相容佳较好的电路异或类再进行异或4 3 表5 4 相容性不好的电路异或类再进行异或4 3 表5 5 改进后扩展相容结构基本类包含扫描单元4 4 表5 6 改进算法第一层基本类的扫描输出4 5 表5 。7 改进震扩展相容结构只包含个扫描单元的相容类4 5 表5 8 加权扩展相容性扫描树构造算法与改进后算法结果比较4 6 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本入承担。 作者签名： 。拟酶日期：矽谚年，月，彩日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 套阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密囹。 ( 请在以上相应方框内打“ ) 作者签名：，瓿锐兹 导师签名：唧啉 墨鬻：弘峥萝年岁胃，参吕 墨期： 暗年r 胃步尽 硕士学位论文 1 1 引言 第1 章绪论 随着各种数字系统的飞速发展，集成电路( i n t e g r a t e dc i r c u i t ，i c ) 得到了广 泛的应用，其制造水平也随之迅速提高。制作高精度的集成电路芯片一般需要经 过多道工艺流程，难免存在着缺陷或故障。检测集成电路芯片工作正常与否，对 于生产厂商和用户都是非常重要的。因而，集成电路测试成为了数字系统设计制 造过程中极其关键的一环。但是随着集成电路的集成度、规模以及复杂度呈现出 几何级数的增长，进行测试所需要的费用也越来越昂贵，这些都给电路测试带来 了极大难度，同时也出现了很多新的问题，一些传统的测试方法已经不能满足人 们对系统可靠性的要求。要解决这些问题，迫切需要采用一些新的测试理论和技 术。 过去，一般都是设计人员根据所需要完成的功能来设计电路，而测试人员根 据已经设计或研制完毕的电路来制定测试的方案。这一传统的做法已经不适应实 际生产的要求。因而，人们提出了所谓的可测试性设计( d e s 逗nf o rt e s t a b i l i t y ， d f t ) ，即功能设计人员在设计电路的同时，应该考虑到测试的要求，看所设计 的电路是否可测以及测试是否方便。近十多年来，关于d f t 的研究已经取得了不 少成果，d f t 也给测试领域开拓了一条切实可行的途径，引起了各方面的关注。 但是目前各种d f t 方法在不同程度上均存在着局限性和实际应用上的困难，因此 继续深入研究硬件开销少、故障检测覆盖率高的设计方法仍然是数字系统设计领 域中一个十分重要的课题。 d f t 技术本质上是一种提高电路可控制性和可观测性的设计技术。全扫描设 计作为目前最重要的d f t 方法之一，其主要思想是通过在触发器之间添加一些逻 辑( 如多路选择器等) ，并在电路中添加测试模式，使得全部的触发器都具有全 可控制性和全可观测性。当电路处于测试模式时，所有的触发器在功能上形成一 条或者多条扫描链。各个扫描链通过扫描移位，可以将所有的触发器都设置成任 意期望的逻辑值。全扫描电路的测试应用时间与电路中最长扫描链的长度成正比。 全扫描设计彻底地降低测试生成的复杂性，但是一般来说，它会增加电路的硬件 开销；而且对于规模较大的电路，全扫描设计的测试应用时间一般会很长，长时 间占用自动测试设备( a u t o m a t e dt e s te q u i p m e n t ，a t e ) 将导致测试费用非常高， 降低其测试费用是当务之急。另一方面，由于数字系统在测试模式下的功耗通常 要比在工作模式下的功耗高很多，以至于i c 在测试时可能会被损坏，如何降低i c 基子提容类掬权的扩襞福容橼扫搐树构造算法研究 的测试功耗也已经成为当前研究的一个热点。然而，通常情况下测试应用时间与 测试功耗在i c 测试中是两个互相矛盾的因素。在硬件开销合理的前提下，很难同 时降低测试费用和测试功耗。量前关予低费用测试和低功耗测试方法，多是以耀 牲其中一个为代价取得的。因此，如何在低功耗的条件下进行低费用测试是相当 重要的。我们迫切需要取得理论上的突破，形成低功耗且低费用测试的方法体系， 使得在硬件开销合理的情况下，同时降低i c 的测试费用和测试功耗。 本课题正是在此背景下产生的。 1 2 基于扫描设计的研究概况 扫描设计是时序电路可测试性设计的一种重要方法。利用扫描设计，电路内 部触发器中的值可以通过扫描移位被观察到，同时也可以通过扫描移位将电路内 部的触发器设置成所期望的逻辑值，这放本质上提高了系统的可观测性耱可控制 性。目前，大多数的系统都采用这种设计方法。扫描设计可以大大简化系统的测 试过程，因此越来越引起各方面的重视【l ，2 】。 基于扫描设计，p h i l i p s 公司予1 9 8 5 年提出了边界扫描设计的概念。这种技术 将恣建自测试( b u i l l 1 l ls e l fh s t ，b l s t ) 的思想推广到了系统级。美国斯坦福大 学的w i l l i 锄s 和a n g e l l 在文献 3 】中详细说明了边界扫描设计在硬件测试中的应 用。美国电气及电子工程师学会( i n s t i t u t eo fe l e c t r i c a la n de l e c t r o n i c se n g i n e e r s ， 主e e e ) 予1 9 9 0 年将豫i l i p s 公司关予边界扫描设计的标准定名为薹e e 嚣l1 4 9 1 。目前， 国际上一些有实力的公司都已经开始应用该标准，l b m 、n e c 和其他一些公司对 这个标准采用了不同实现形式1 4 j 。 现有的各种扫描测试方法在不同程度上均存在着测试费用高、测试应用时间 过长、测试功耗过高和实际应用上的缺点。一般来说，如果要降低测试应用时闻， 势必要提高测试的并行性，即用更多的跳变去激活故障，从而导致测试功耗升离； 如果要降低测试功耗，则需要降低电路中信号的翻转活跃性，这将会减少同时测 试出的故障数，使测试应用时间变长。在目前的研究中，要么只考虑低费用测试， 要么只考虑低功耗测试，这些技术，通常以牺牲另外一个因素药代价。 在扫描设计中，有种方法被称为随机访问扫描( r a n d o ma c c e s ss c a n ，r a s ) 1 5 】。与其它扫描设计不同的是，采用这种设计的扫描单元在测试模式下可以按地址 进暂访问，这与随机访阀存储器( r a i l d o ma c c e s sm e m o r y ，r a m ) 的工作方式类 似。随机访问扫描减少了测试模式下设置和观察扫描单元状态所需的时闻，但是 由于需要对触发器进行寻址，r a s 将会在电路中添加大量的门和测试管脚，因而 硬件开销较大。 为了降低测试数据量，可对测试向量重新进行编解码【瓢翔。这些策略也主要利 用了测试向量中存在的不确定位，采用数学方法实现对数据的压缩。文献【8 】提出 2 硕士学位论文 了一种基于多扫描链相容压缩的距离标记压缩方法，利用相容压缩和基于差分的 编码方法两次压缩测试数据，有效降低了电路的测试数据量。 近几年来，关于低费用测试，涌现出大量新的技术p 以训。一般来说，目前的低 费用测试研究主要是利用编码方法对测试向量进行压缩，再由芯片中的硬件解压 缩，达到用较少的数据量来测试电路的目的。带轮转扫描链( c y c l i c a ls c a nc h a i n s ) 的游程编码【9 1 ，哈夫曼编码【l 们，格林编码【1 1 1 被用来压缩测试向量。文献 1 2 1 4 】提 出了新的扫描结构，通过降低测试应用时间以及测试数据量来降低测试费用。文 献【1 2 】中的方法通过加入多路选择器，用有限的外部输入管脚控制大量内部扫描链 来测试整个电路，较大地减少了测试应用时间和测试数据量。v i n u a l s c a n 技术【l 列 引入编码方案，通过对测试向量和测试响应的集合进行数据压缩，减少全扫描电 路中的最长扫描链长度来降低测试费用。c i r c u l a r s c a n 结构1 1 4 】利用存在的不确定 位，对测试数据进行压缩，采用专有硬件解码，在扫描输入测试向量时，仅替换 与捕获的测试响应不同的那些位，从而极大地减少了测试数据量和测试应用时间。 文献【1 5 】采用交迭测试将电路分为几个部分，对每个部分进行测试时，通过改变扫 描链中扫描单元的顺序来降低电路总的测试时间。文献 1 6 】基于贪婪策略和单扫描 链最优排序技术，提出了一种多边界扫描链优化配置技术。 扫描树技术【l7 也2 】可以减少测试应用时间和测试数据量。在这些技术中，扫描 单元被构造成一个树型结构。相比单扫描链结构，被测电路中最长扫描链的长度 降低了，从而降低了测试数据量和测试应用时间。在扫描树中，经过根扫描单元 的测试数据通过扫描移位进入扫描树的每一个节点( 对应于一个扫描单元) 。扫描 树同一级上的扫描单元有相同的测试数据。因此，为了保持故障覆盖不变，同一 级上所有的扫描单元对所有测试向量相容。作为扫描树技术最原始的想法，文献 【1 7 】将扫描单元划分成几个扫描链，使电路具有两种测试模式：并行和串行装入。 在并行装入模式下，所有的扫描链同时装入相同测试数据，减少了测试数据量和 测试应用时间。文献【1 8 】在文献 17 】的基础上，提供了两种不同的扫描单元划分方 法，从而降低了提出串行装入的测试向量。文献【1 9 】构造了一棵扫描树，并且通过 修改测试向量来最小化它的高度。文献【2 0 】将文献【l9 】中的技术推广到多扫描链的 情况。文献 2 l 】采用了交叠模式，增强了并行性，优化了生成的扫描树结构。在文 献 2 2 】中，通过单扫描链模式和扫描树模式的动态重构来极大地减少测试应用时间 和测试数据量。 为了降低测试应用时间，文献 2 3 】采用并行扫描测试，提出了一种扫描森林测 试结构。该方法主要利用了测试向量中存在大量的不确定位，使用一个扫描输入 来驱动多条扫描链或者将外部扫描输入转换为多个内部扫描输入，减小了扫描链 的长度，从而降低测试向量置入扫描链所需的时间。文献【2 4 】提出基于电路结构信 息的c o n n i c t 测度，提高了电路整体的可测试性。文献 2 5 】提出扫描森林结构的重 基于穗容类热投酶扩袋福容健扫描树构造算法研究 组策略和基于电路结构信息的异或树构造策略，避免了故障屏蔽，降低了可测试 性设计的面积开销和布线难度。文献【2 6 】提出了一种两级扫描测试结构。该结构通 过添加多路选择器将扫描单元划分到不同的时钟域，使得在输入测试向量时只有 一部分扫描单元进行扫描移位，并引入异或网络来减少扫描输出。 如何降低测试功耗已经成为当今设计中必须考虑的问题之一。因为过高的功 耗会导致高溢，而高温将引发很多问题1 2 7 】，如增加产晶的成本，降低l c 的可靠性， 给性能验证带来困难，降低移动设备的便携性等等。 在c m o s 电路中，测试功耗正比予电路的时钟频率和电路节点跳变率【2 引。因 此，降低时钟频率或节点翻转的活跃性都能达到降低测试功耗的目的。 有诲多方法是通过降低电路内部信号翻转髂活跃性来降低测试功耗的。为了 最小化测试功耗，文献【2 9 3 2 】采用了测试向量和扫描单元重新排序的方法。这些 方法的基本思想是重排测试向量和扫描单元的顺序，使得连续的测试向量之间产 生跳变的数量减少。文献【3 3 3 4 】将测试立方中的不确定位x 赋值为适当的o 或者 l ，放丽提高连续测试向量之间酌相关性，降低了测试功耗。 文献 3 5 3 9 】使用阻塞部分扫描链时钟的技术来降低测试功耗。w h e t s e l 【3 5 】， s a x e n a 【3 6 】和b o n h o m m e 印】提出了三种低功耗测试方案。在这些方案中，扫描链被 分成个子扫描链，其中为整数且渺l 。在扫描移位时，仅有一个子扫描链的 时钟没有被阻塞，因此降低了平均功耗。b 魏撒a o h 哪鑫f 3 8 】提出了双重扫描树结构。 在这个结构里，扫描单元被排成两颗叶子重合的k 级二叉树。在扫描移位时，仅 有在同一个扫描路径上的扫描单元被驱动，使得平均功耗有所降低。但是这些技 术在捕获测试响应时，所有的扫描链都活跃，峰值功耗没有明显降低。文献【3 9 】 将扫描链被分成个子扫描链，在扫描移位和捕获测试响应时，仅有一个子扫摧 链活跃，这使得平均功耗和峰值功耗都有了较大地降低。 文献【4 0 】提出了一种扩展相容性扫描树结构，具有测试费用和测试功耗均比较 低懿特点。该结构通过添加逻辑非和异或醢数将扫描单元的相容性推广了。与以 前的扫描树技术相比，文献【4 0 】中的方法使得扫攒树的测试应用时间更短。扩展相 容性扫描树结构极大地降低了扫描链的长度，但是同时也使得生成的扫描树的扫 描输出过多。在文献【4 0 】的基础上，本研究对其扫描树生成算法进行改进和优化， 在进一步降低测试应用时闻和测试数据量的同时，减少了该扫描结构所需的硬件 开销。 1 3 本文研究目的与意义 随着超大规模集成技术的飞速发展，集成电路的测试变得越来越困难，可测 试性设计已经成为豢前测试领域的一个研究热点。全扫描设计是v l s l 电路中最重 要的可测试性设计方法之一，它彻底地降低了测试生成的复杂性，但是也存在着 4 硕士学位论文 测试应用时间过长的缺陷。 为了降低测试应用时间以及测试数据量，现有的扫描树生成算法使得构造的 扫描结构硬件开销较大。文献【4 0 】没有很好地考虑到扫描树的平衡性，存在着扫描 树层数相对较少但是扫描输出较多的问题。扫描输出较多将使得测试的硬件开销 增加，并导致对扫描树输出的压缩变得极其困难。为了减少扫描输出，文献 2 0 】 对扫描树每一层触发器的个数加以限制。这样虽然控制了扫描树扫描输出的个数， 但使得扫描树层数又有所增加，测试应用时间和测试数据量亦会增加。因而设计 一个使得扫描树的层数和扫描输出更少的优化算法来降低测试应用时间、测试数 据量以及减少测试硬件开销是很必要的。 本研究对如何判定被测电路整体相容性的好坏提出了一种新的方法，给出了 构造一棵扩展相容性扫描树的算法，并补充了两条减少扫描树扫描输出的规则。 本研究完善了扩展相容性扫描树结构，对该结构的发展有着积极的作用，并对扩 展相容性扫描树结构今后在实际中的应用起了一定促进作用。 1 4 本文主要工作 本文对扩展相容性扫描树结构进行了详细分析，并针对该结构提出了新的扩 展相容性扫描树构造算法。本文主要工作归纳如下： 1 针对现有扩展相容性扫描树构造算法的不足，提出了一种基于相容类加权 的扩展相容性扫描树构造算法。文献【4 0 】中的方法使用贪婪算法构造扩展相容性扫 描树，其扫描输出个数较多，且扫描树的层数存在进一步降低的空间。通过实验， 本研究对扩展相容性扫描树结构扫描单元的相容性以及电路整体相容性进行了分 析，在该结构的基础上提出了新的扩展相容性扫描树构造算法。该算法通过设置 权值来生成相容类，用较小的硬件和时间开销构造了新的扩展相容性扫描树，减 少了扫描树的层数和扫描输出，使得扩展相容性扫描树结构的测试应用时间和硬 件开销有了较大地降低。 2 对1 中的加权算法做出了进一步改进。在使用加权算法生成相容类时，若 多个扫描单元同时满足选取条件，该算法根据扫描单元的编号顺序进行选择。在 多个扫描单元同时满足选取条件的情况下，改进算法将根据扫描单元的测试数据 以及度来选择。同时，改进算法提出异或类可以再进行异或以生成新的异或类。 实验结果表明，改进算法构造的扩展相容性扫描树在层数和扫描输出个数方面有 明显下降。改进算法用相对较小的代价进一步降低了测试应用时间和测试硬件开 销，这种基于扩展相容性扫描树结构的算法是可行的。 5 基于相容类加权的扩展相容性扫描树构造算法研究 1 5 本文组织结构 全文共分5 章，各部分内容安排如下： 第一章概述基于扫描设计的研究概况以及本文所做的工作。 第二章对电路测试中的一些基本概念和方法进行简单介绍，并阐述扫描设计 的一些基本原理。 第三章介绍扩展相容性扫描树结构的基本思想和该结构扫描树的构造算算 法。之后通过实验对其各项数据进行量化分析，指出扩展相容性扫描树结构目前 所存在的问题。 第四章针对扩展相容性扫描树结构存在的问题，补充了两条减少扫描输出的 规则，提出一种基于相容类加权的扩展相容性扫描树构造算法。实验结果表明了 此算法的有效性。 第五章对第四章算法中未考虑的几种边界情况进行了补充和改进，并给出理论 以及实验数据的证明。之后使用改进算法生成了基准电路s 1 4 2 3 的扩展相容性扫 描树，通过实例对比展示该算法的有效性。 最后总结全文，并给出了未来的工作。 6 硕士学位论文 第2 章电路测试中的基本概念和扫描设计 2 1 引言 数字集成电路测试技术对保证数字系统质量、可靠性及商业影响力至关重要。 随着数字系统规模和复杂度的增加，d f t 技术得到越来越广泛的应用。d f t 技术 在被测电路中加入额外的器件和信号，使得测试可以按照某个预先设定的过程进 行。这样的设计除正常功能模式之外，还有一个测试模式。最常用的d f t 方法就 是本章所讨论的扫描设计。 2 2 电路测试中的基本概念 数字集成电路在设计和制造以及运行过程中，需要进行测试，以检验是否符 合设计的要求以及是否能够正常工作。对数字系统来说，一般主要是测试其功能、 时序和逻辑关系。 如果仅仅是测试一个电路是否存在故障，则称之为故障检测；如果不仅要检 查电路中是否存在故障，而且要定位故障点，则称之为故障诊断。一般来说，故 障检测和故障诊断统称为测试。 2 2 1 故障 一个逻辑元件或者电路，由于某种原因而导致其不能完成应有的逻辑功能， 则称这个逻辑元件或者电路已经失效( f a i l u r e ) 。而故障( f a u l t ) 是指一个逻辑元 件或者电路物理上的缺陷，它有可能使得这个元件或者电路失效。但是并不是有 故障就一定引起失效。 故障可以用故障的性质、故障值、故障的范围以及故障的持续时间等特征来 描述。故障可以是瞬时故障、永久故障或周期性故障。一旦发生故障，将导致系 统的状态出错，这些错误将可能引发系统失效。 故障处理主要有四种方法：故障预测、故障避免、故障消除、容错。故障预 测是利用数学模型和实验分析发生故障后所产生的后果。故障避免和故障消除通 过严格的规范和验证技术来实现，尽可能地避免发生故障。容错采用了各种冗余 系统来减少或者消除发生故障所带来的影响。 2 2 2 故障模型 元件、电路或系统的故障是千变万化的。为了研究这些故障对于电路或系统 的影响，诊断出故障所在的位置，有必要对故障进行分类，并构造最典型的故障， 7 基予相容类加权的扩展相容性扫描树构遗算法研究 这个过程叫故障的模型化。用来代表一类故障的典型故障称为模型化故障。目前 常见的故障有固定型故障，桥接故障，开路故障，时延故障等。 固定型故障( s t l l c l ( a lf a u l t s ) 模型主要反映电路或系统中菜横信号线( 如门的输 入线、连接导线筹) 上的不可控性，即该信号线在系统运行过程中永远固定在某 一个值上。在数字系统中，如果某一根线( 或该点) 固定在逻辑高电平上，则称 之为固定l 故障( s t u c k - a t 1 ) ；如果该线( 或该点) 固定在逻辑低电平上，则称之 为固定o 故障( s t u e l 【鑫1 0 ) 。根据电路中豳定型故障的数霉，可分为单固定型教障 ( 即电路中只存在一个固定型故障) 和多固定型故障( 电路中存在二个或二个以 上的固定型故障) 。 固定故障模型中最常用的是单固定型故障。固定故障模型在实际应用中非常 普遍，对于固定敌障的测试生成和赦障模拟技术也豳趋完善。 本文中的故障均指的是单固定型故障。 2 2 3 故障等价与故障精简 考虑一个带有刀个输入变量的单输出组合电路。将电路输出函数记为苁玢， 这里的y 是个糟位的布尔向量。对予该电路口和6 两个故障，记口的输如为尼( 玢， 测试集为疋；矗的输蹴为五( 乃，6 的测试集为磊。 若疋熊够检测赦障6 ，那么称6 是口的支配故障。当两个故障互相支配时， 则称口与6 两个故障等价。 被测电路中所有敞障的集合可以划分成若干个子集，每个子集中的故障都相 互等价。等价集可将所有的故障分成不相交的子集。因为如采一个故障出现在两 个等价集中，那么这两个等价集必定相互等价。从每一个等价集中选择一个故障 的过程称为故障压缩。选择的故障形成的集合称为等价压缩集。所有故障与等价 压缩集的比值就是压缩比。在等价压缩集中消除支配故障可进一步增大压缩比。 2 2 4 故障覆盖率 故障覆盖率就是指测试向量集能够检测出的故障数占所有故障总数的比率。 例如，透过测试生成褥到一组测试向量，使用其对被测电路进行测试。若电 路中可能的故障共为押个，而这组向量能够测试出其中的删个，则这组向量对 该被测电路的故障覆盖率为朋砌。 2 。3 扫描设计 典型的扫描设计工作框图如图2 1 所示。首先，由测试生成得到被测电路的测 试向量，这些测试向量以及对应的期望的测试响应被存储在测试仪里；然后，测 试仪通过扫描移位向电路施加测试向量，并捕获电路在相应激励下的测试响应： 最后测试仪根据得到的测试响应与期望的测试响应比较来判断电路是否存在敌 硕士学位论文 障。 图2 1 扫描设计工作框图 扫描设计的主要思想是获得对被测电路中扫描单元的可控制性和可观测性。 通过在被测电路中增加一个测试模式，使得当被测电路处于测试模式时，所有扫 描单元在功能上构成一条或者多条扫描链。这些扫描链的输入与输出可以是电路 的原始输入和原始输出。因此在测试模式下，通过将测试数据扫描移位到扫描链 中的方法，可以把电路中所有的扫描单元都设置成测试所需要的状态。类似的， 也可以通过扫描移位来观察扫描单元中的逻辑值。由此可知，对于扫描电路而言， 其测试应用时间与电路中最长扫描链的长度成正比。 为了使被测电路具有扫描测试功能，设计者首先将对电路中的触发器进行功 能测试。这些触发器一般是d 触发器( d f f ) ，其时钟信号通过原始输入端控制。 一个典型的d 触发器如图2 2 所示。 辱= 主锁存器匕= 令辱= 从锁存器匕= 冷 图2 2d 触发器 q 哦 一旦电路完成了功能验证，这些d 触发器就全部被替换成扫描单元( s f f ) 。 9 基于福容类麴权懿扩裟稳容髋扫接瓣构造算法研究 一个典型的扫描单元如图2 3 所示。 与基本的d 触发器相眈，扫描单元加入了一个多路选择器和两个新的信号输 入，测试数据鼢和测试控制信号彤。当陀力l 时，被测电路正常运行，将原 来的输入数据d 保存到扫描单元中；而当愆为o 时，被测电路将处于测试模式， 扫描单元保存的是舳的值。 l b ) 利用规则l 薅的扩展楣窭性扫描树 图4 1 减少扫描输出规则1 图4 2 是规则1 的另种情况。 幻原扩展相容性扫攒树 b ) 利用规雯| l l 优化薏翡扩震摆容性扫描树 图4 2 减少扫描输出规则l 第二神情况 硕士学位论文 如图4 2 ( a ) 所示，原扩展相容性扫描树有3 个扫描输出，即扫描单元j 泓，j 锯和历 的输出。异或类鼢】由基本类慨】与基本类【历】相异或而成。根据规则l ，由于基本 类呖】的上一层基本类嘶班】中扫描单元历存在扫描输出，因而可将扫描单元挠的 扫描输出连接到历之前的异或门。通过规则1 的优化，扫描树减少了扫描单元历的 扫描输出，如图4 2 ( b ) 所示。 同理可以证明，此时规则1 仍然保持了故障覆盖率不变。 规则2 假设异或类q 是由基本类彳和基本类曰异或而成，若q 中的扫描单元存在 扫描输出，那么可以将异或类q 下一层的相容类通过添加一个异或门接在q 之后。 如图4 3 ( a ) 所示，原扩展相容性扫描树存在3 个扫描输出，分别为扫描单元历， 历和历的扫描输出。异或类场】是由基本类 历】和基本类晚】异或而成，且异或类鼢】 中扫描单元历存在扫描输出，因而其满足可利用规则2 的条件。根据规则2 ，异或 类场】下一层的基本类慨扔】可通过添加一个异或门而接在历之后。在图4 3 ( b ) 中， 扫描单元历连接在历之后，从而使得扫描树减少了历的扫描输出。 利用规则2 将扫描单元历连在历之后，若异或类场】的扫描单元历中出现了故 障值，可由历传播到扫描输出；若扫描单元历与伤同时出现故障值，则虽然异或类 呖】的扫描单元历中故障值与基本类【历】异或后被屏蔽而不能被检测到，但是扫描 单元历中的故障值可经历传播到扫描输出，因而最终仍可捕获到被测电路的故障。 所以规则2 保持了故障覆盖率不变。 a ) 原扩展相容性扫描树 b ) 利用规则1 优化后的扩展相容性扫描树 图4 3 减少扫描输出规则2 图4 4 和图4 5 是规则2 的另外两种情况。在这两种情况中，先找到满足利用规 则2 条件的异或类，然后将它下一层的异或类通过添加一个异或门接在其后，从而 纂手耦容类热投懿扩袋裾容榷耘箍树构造算法研究 减少了扩展相容性扫描树的扫描输出。以图4 4 ( a ) 为例，原扩展相容性扫描树存在 3 个扫描输出，即扫描单元历，j 鳃袒历的扫描输出。基本类沥】与基本类暾】相异或 褥到异或类鼢】；异或类沥】中的扫描单元历存在扫描输出，因而异或类鼢】满足可 以利用规则2 的条件。根据规则2 ，异或类嘲】下一层的异或类鼢】中的扫描单元可 通过添加一个异或门而接在历之后。在图4 4 ( b ) 中，异或类 历】中的扫描单元历连 接在蕊之后，从而减少了历的扫描输出。 同理可以证明，在这两种情况下的规则2 仍然保持了故障覆盖率的不变。 a ) 原扩展相容性扫描树 b ) 利用规则2 后的扩展相容性扫描树 图4 4 减少扫搂输出觏刘2 第二种情况 a ) 缀扩震相容性扫描树 b ) 利用规则2 后的扩展相容性扫描树 图4 5 减少扫描输出规则2 第三种情况 硕士学位论文 4 2 2 被测电路整体相容性评定 在构造扩展相容性扫描树之前，本章加权算法先对被测电路整体相容性进行 评估。若被测电路的整体相容性较好，那么算法在生成相容类时，容易使得大多 数的扫描单元集中在少数几个相容类中，这将导致最终扫描树的层数和扫描输出 增加。因而对于整体相容性较好的被测电路，更应该关注的是各个相容类包含扫 描单元的平衡，避免生成几个包含大部分扫描单元的相容类。若被测电路整体相 容性较差，则在生成相容类时容易生成很多孤立的扫描单元，这将使得最终扫描 树的层数增加。所以对于相容性较差的被测电路，除了要保证扫描单元尽可能平 衡地分布在各个相容类中，同时关键还要减少孤立扫描单元的产生。 基于这两种不同的被测电路，新的扩展相容性扫描树构造算法应该有所区别 的对待。 定义评定相容关系矩阵彳如下： f o 觏镢不相容，瓤相容且f _ 一l 7 1 1 若厉与毵相容且f 。 由表5 2 可知，按度的升序选取界或类扫接单元对于整体相容性较好和不好的 被测电路都适用。此改进不需要增加额外的硬件开销，且有效地降低了扩展相容 性扫描树的层数，平均降低达到2 ，回时扫摧输患平均减少1 5 。虽然对于个别 被测电路，所生成的扫攒树扫播输爨个数有所增加，但是增加幅度缀小。这样鹩 代价是可以接受的。 综上所述，选取度较小扫描单元组成异或类减少了扫描树的层数和扫描输出， 降低了测试应用时闻班及测试数据量。 4 l 表5 1 按包含x 个数的顺序选取扫描单元 电路名改进前扩展性扫描树改进后的扫描树 l o o p s o u t l o o p s o u t s 1 4 2 33 0 1 73 01 0 s 5 3 7 89 42