（计算机科学与技术专业论文）ndetection测试产生方法研究.pdf

t h er e s e a r c ho nn d e t e c t i o nt e s t sg e n e r a t i o n h u a n g g a i y o u b e ( h u n a nu n i v e r s i t yo fa r t sa n ds c i e n c e ) 2 0 0 7 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro f e n g i n e e r i n g c o m p u t e rs c i e n c ea n dt e c h n o l o g y i n t h e g r a d u a t es c h o o l o f h u n a n u n i v e r s i t y s u p e r v i s o r p r o f e s s o rk i7 a n gj i s h u n m a y ，2 0 1 1 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者躲谨坏 、- 日期：加7 j 年1 月习日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“”) ，作者签名：青蛳 剔谧氢门叫 日期：加i1 年瑚岁7 日 日期：a 刮年r 月了1 日 n d e t e c t i o n 测试产生方法研究 摘要 随着超大规模集成电路技术进入纳米时代，电路日趋复杂，集成度日益增高， 由此导致数字集成电路故障的复杂性急剧增加，为每一类故障建立故障模型并产 生测试集是不现实的。解决此问题的一个有效方法是使用n d e t e c t i o n 测试。 n d e t e c t i o n 测试以广泛使用的固定故障模型为基础，对于电路中的所有可测固定 故障都至少产生n 个不同的测试。此测试方法的理论基础是：某个固定故障被检 测的次数越多，激活此故障点非模型故障的概率越大。已有的实验结果表明， n d e t e c t i o n 测试集对固定开路故障、桥接故障等故障模型有很高的故障覆盖率。 但是n d e t e c t i o n 存在产生测试困难，测试数据量过大等缺陷。 最小单检测测试集中测试向量数目的下界是独立故障集的大小，在最小单检 测测试产生研究已经非常成熟的情况下，人们开始寻找获得最小n d e t e c t i o n 测试 集的方法，在理论上，最小n d e t e c t i o n 测试集中测试向量数目的下界是独立故障 集大小的n 倍。但用现有的n d e t e c t i o n 测试a t p g 工具获得的n d e t e c t i o n 测试 集远大于理论值，难测故障是造成测试集较大的重要原因。 本文提出了一种高效的n d e t e c t i o n 测试产生方法。首先用传统的单检测 a t p g 工具产生一个非最优的m d e t e c t i o n 测试集，然后将其压缩为n d e t e c t i o n 测试集。由于这个问题可以转化为整数线性规划模型求解，因此通过求解整数线 性规划可获得最小的n d e t e c t i o n 测试集。 虽然用单检测a t p g 工具产生的m d e t e c t i o n 测试集对难测故障的检测次数大 于n ，但较易测故障偏少，影响测试压缩效果。于是本文针对所有难测故障产生 一个额外的含无关位测试向量，压缩后再进行随机填充，这种方法只需增加较少 的测试向量就能显著的增加难测故障的检测次数。通过这种改进，提高了测试压 缩率 用整数线性规划求最优解的时间开销很大，本文定义了一种约束矩阵中的行 支配关系，通过删除支配行，减少约束矩阵的维数，提高了n d e t e c t i o n 测试产生 方法的时间效率和对大电路的适应性。 关键字：集成电路测试；n d e t e c t i o n 测试；a t p g ；故障模拟；i l p n 硕：卜学位论文 l i i喜- 毫皇暑詈詈詈詈暑喜篁皇= 詈暑暑毫詈暑詈詈暑皇皇詈詈暑墨毫詈詈詈= 鲁詈皇= 暑富= 暑詈詈暑詈詈! 詈= 葛皇皇= 詈詈詈詈詈鼍葛詈鲁兰暑詈暑兽詈皇詈墨鲁皇葛摹喜詈詈詈詈暑詈拿暑暑鼍皇 a b s t r a c t w i t ht h et e c h n o l o g yo fv e r yl a r g es c a l ei n t e g r a t e dc i r c u i t st e c h n o l o g yh a s e n t e r e di n t ot h ea g eo fn a n o m e t e r ，i t sf u n c t i o nb e c o m e sm o r ec o m p l i c a t e da n dt h e i n t e g r a t e dd e n s i t yi n c r e a s eq u i c k l y a sar e s u l t ，t h ec o m p l e x i t yo fc i r c u i t s f a u l t s s h a r p l yi n c r e a s e d t h e r e f o r e ，i ti sn o tr e a l i s t i ct oe s t a b l i s hf a u l tm o d e la n dg e n e r a t e t e s ts e t sf o ra l lf a u l t s o n ee f f i c i e n ts o l u t i o nt ot h i sp r o b l e mi st h en d e t e c t i o nt e s t t h a tu s e sc o n v e n t i o n a ls t u c k - a tf a u l tm o d e lt og e n e r a t ep a t t e r n st h a ta t t e m p tt od e t e c t e a c hf a u l ta tl e a s tnt i m e s t h i st e s tm e t h o di sb a s e do nt h et h e o r yt h a tt h et i m e so fa s t u c ka tf a u l tt ob ed e t e c t e dm o r e ，t h ep r o b a b i l i t yo fa c t i v a t i o nt h en o n - m o d e lf a u l to f t h i sn o d ei sg r e a t e r p r e v i o u se x p e r i m e n t a lr e s u l t sh a v es h o w nt h a tn - d e t e c t i o nt e s t s e t sh a v eh i g hf a u l tc o v e r a g ef o rs t u c ko p e nf a u l t ，b r i d g i n gf a u l t sa n do t h e rf a u l t m o d e l s h o w e v e r , i ti sh a r dt og e n e r a t et e s ts e t sf o rn - d e t e c t i o na n dw h i c hn e e d sh u g e t e s td a t av o l u m e t h el o w e rb o n do nt h es i z eo ft h es i n g l ed e t e c t i o nt e s ti st h es i z eo ft h e i n d e p e n d e n tf a u l ts e t ( i f s ) p e o p l ew a n tt oo b t a i nm i n i m a ln d e t e c t i o nt e s ts e t sa st h e s m a l l e s ts i n g l e - d e t e c t i o nt e s tg e n e r a t i o ns t u d i e sh a v eb e e nv e r ym a t u r e i nt h e o r y ，t h e m i n i m a lo ft h en d e t e c t i o nt e s ts e ti snt i m e so fi f s b u tt h en d e t e c t i o nt e s ts e t s o b t a i n e db yt h ee x i s t i n ga t p gt o o la r em u c hl a r g e rt h a nt h et h e o r e t i c a lv a l u e a t t r i b u t i n gt oh a r df a u l t a ne f f i c i e n tm e t h o dt og e n e r a t en - d e t e c t i o nt e s t si sp r o p o s e di nt h i sp a p e r f i r s t ， t r a d i t i o n a ls i n g l e - t e s ta t p gt o o li su s e dt og e n e r a t ean o n - o p t i m a lm - d e t e c t i o nt e s t s e t s t h e nt h ec o m p r e s s i o np r o b l e mi st r a n s f o r m e di n t oa ni n t e g e rl i n e a rp r o g r a m m i n g ( i l p ) m o d e l s ot h em i n i m u mn - d e t e c t i o nt e s ts e t sc o u l db eo b t a i n e db ys o l v i n gt h e i l p t h ed e t e c t i o nt i m e so fh a r df a u l tb ym - d e t e c t i o nt e s ts e t sw h i c hg e n e r a t e db y s i n g l ed e t e c ta t p gt o o la r el a r g e rt h a nn ，b u ts m a l l e rt h a ne a s yf a u l t ，w h i c ha f f e c t s t h ec o m p r e s s i o ne f f i c i e n c y s ot h i sp a p e rp r o p o s e sa ne x t r av e c t o rw h i c hc o n t a i n s d o n tc a r eb i tf o ra l lh a r df a u l tb ya t a l a n t aa l g o r i t h m t h e s ev e c t o r sa r ec o m p r e s s e d a n dt h e nt h ed o n tc a r eb i ti sf i l l e dr a n d o m l y t h en u m b e ro ff a u l t sd e t e c t i o nt i m e si s s i g n i f i c a n t l yi n c r e a s e db yt h i sm o t h o d t h ec o m p r e s s i o nr a t i oi sa l s oi n c r e a s e db yt h i s i m p r o v e m e n t i ti st i m ec o n s u m i n gt of i n do p t i m a ls o l u t i o n sb yi l p t h e r e f o r e ，ar o w i i i n d e t e c t i o n 测试产生方法研究 ! ! = = 目= = = = ! ! ! 自e e ! ! = = = = s ii i i m l 目 d o m i n a n c er e l a t i o n s h i pi nam a t r i xi sd e f i n e di nt h i s p a p e r t h ed i m e n s i o no f c o n s t r a i n tm a t r i xi sr e d u c e db yr e m o v i n gt h ed o m i n a n tr o w , w h i c hi m p r o v e st i m e e f f i c i e n c yo ft h en - d e t e c t i o nt e s tg e n e r a t i o nm e t h o da n da d a p t a b i l i t yf o rl a r g e c i r c u i t s k e yw o r d s ：i ct e s t i n g ；n d e t e c t i o nt e s t ；a t p g ；f a u l ts i m u l a t i o n ；i l p i v 硕士学位论文 口罩 h 刊k 学位论文原创性声明和学位论文版权使用授权书i 摘要- i i a b s t r a c t i i i 插图索引v i i 附表索引v i i i 第1 章绪论1 1 1v l s i 简介及其测试1 1 2n d e t e c t i o n 测试介绍2 1 2 1 固定故障模型3 1 2 2 固定故障的测试产生和故障模拟4 1 2 3n d e t e c t i o n 测试产生7 1 2 4n d e t e c t i o n 测试集的应用7 1 3 本文研究目的和意义1 0 1 4 本文的主要工作1 1 1 5 本文的组织结构1 1 第2 章组合电路的测试集压缩技术1 2 2 1 单固定故障压缩1 2 2 2 静态压缩1 4 2 3 动态压缩o ：17 2 4 基于独立故障的测试压缩1 7 2 4 1 故障关系分类1 7 2 4 2 判断独立关系的方法1 8 2 4 3 独立故障图和独立矩阵2 0 2 4 4 独立度和相似性2 2 2 4 5 独立故障压缩算法2 3 2 5 组合逻辑电路的最小测试集2 5 2 6 ，j 、结2 6 第3 章一种高效的n d e t e c t i o n 测试集产生方法2 7 3 1n d e t e c t i o n 测试集大小的下界2 7 3 2m d e t e c t i o n 测试集的产生2 8 3 2 1a t a l a n t a 和h o p e 软件介绍2 8 v n d e t e c t i o n 测试产生方法研究 3 2 2m d e t e c t i o n 测试集的产生方法3 0 3 3 用i l p 获得最小的n d e t e c t i o n 测试集3 2 3 3 1i l p 及其求解工具介绍3 2 3 3 2 产生最小n d e t e c t i o n 测试集问题的形式化描述3 4 3 3 3 约束矩阵a 的产生3 6 3 4 实验结果3 7 3 5 小结3 8 第4 章n d e t e c t i o n 测试产生方法的优化_ 。3 9 4 1m d e t e c t i o n 测试集的优化3 9 4 1 1 难测故障3 9 4 1 2 难测故障的测试产生j 4 0 4 2 约束矩阵的化简4 2 4 3 实验结果与分析4 3 4 4 j 、结4 6 结 论4 7 参考文献4 9 附录a 攻读硕士期间发表的论文5 3 致谢5 4 v l 硕七学位论文 插图索引 图1 1 v l s i 芯片的制造过程2 图1 2 一个单固定故障的例子4 图1 3 故障模拟在测试生成的作用6 图1 4 故障模拟过程6 图1 5 一个n d e t e c ta t p g 算法例子7 图1 6 桥接故障模型8 图1 7 晶体管故障转化为固定型故障9 图2 1 布尔门的等价故障。1 3 图2 2 一个故障压缩例子1 4 图2 3 故障间基于测试的关系1 8 图2 4 布尔门的功能独立故障1 9 图2 5 两个子块间故障的蕴含独立1 9 图2 6 基于a t p g 的寻找独立故障方法。 2 0 图2 7c 1 7 电路中的s a l 故障( 压缩后) 2 l 图2 8c 1 7 电路的独立故障图2 1 图2 9 独立故障压缩算法2 4 图2 1 0c 1 7 电路独立故障图的压缩过程2 5 图3 1a t a l a n t a 程序产生的测试集2 8 图3 2b 0 1 电路结构( c d l 描述) 2 9 图3 3 测试集结构2 9 图3 4 故障模拟( h o p e ) 结果3 0 图3 5 故障模拟在m d e t e c t i o n 测试集产生过程中作用3 0 图3 6 故障模拟结果31 图3 7 电路中每个故障被检测的次数3 1 图3 8 一个用i l p 求最小测试集模型3 5 图4 1 含无关位测试向量压缩算法4 0 图4 2m d e t e c t i o n 测试集优化后电路中故障的检测次数4 2 图4 3 用支配关系化简矩阵算法4 3 图4 4 基于测试向量的无关位给电路分类4 5 v i i n 。d e t e c t i o n 测试产生方法研究 附表索引 表1 1 集成电路工艺的发展特点和规律1 表1 2n d e t e c t i o n 测试集的固定故障覆盖率和桥接故障覆盖率8 表1 3 检测固定开路故障的两个向量一9 表1 4n d e t e c t i o n 测试集的固定开路故障效率1 0 表2 1i t c 9 9 基准电路单固定故障的压缩1 4 表2 2 集合覆盖矩阵1 6 表2 3c 1 7 电路的独立矩阵2 1 表2 4 按独立度的降序排序2 3 表2 5 相似矩阵2 3 表2 6 独立故障分组结果一2 4 表2 7 最小的单检测测试集2 6 表3 1 运行a t a l a n t a 算法1 0 次获得的测试集3 2 表3 2 由文本文件产生的矩阵m 转置成a 3 6 表3 3b o l ，b 0 2 和b 0 7 三个电路的n d e t e c t i o n 测试集3 7 表3 4 用i l p 获得的n d e t e c t i o n 测试集( i t c 9 9 ) 3 7 表4 1 电路中检测次数为n ( 7 k 1 6 ) 次的故障数3 9 表4 2b 0 3 电路利用无关位进行填充优化m d e t e c t i o n 4 1 表4 3 矩阵化简的例子4 3 表4 4m d e t e c t i o n 测试集优化后的性能一4 4 表4 5 用i l p 获得的n d e t e c t i o n 测试集( i s c a s 8 5 ) 4 4 表4 65 - d e t e c t i o n 的比较4 5 v i i i 硕士学位论文 1 1v l s i 简介及其测试 第1 章绪论 超大规模集成电路( v e r yl a r g es c a l ei n t e g r a t e d ，v l s l ) 是现代电子设备最重 要的部分【l 刁j 。此类电路采用非常复杂的工艺，把成千上万个晶体管集成在一 个面积很小的半导体晶片上，然后封装在一个管壳内，成为具有特定电路功 能的微型结构，使得整个电路的体积大大缩小，为现代电子产品的发展奠定 了基础。v l s i 开始出现于复杂半导体和通信技术迅速发展的2 0 世纪7 0 年代。 由于其集成度一直遵循“摩尔定律”以每18 个月翻一番的速度急剧增加，目前一个 芯片上集成的电路元件数早已超过十亿，这种发展趋势正在使v l s i 在电子设备 中扮演的角色从器件芯片转变为系统芯片( s o c ) 。表1 1 反映了集成电路工艺的发 展特点和规律。 表1 1 集成电路工艺的发展特点和规律 v l s i 工艺最小线宽己达到超深亚微米( 小于1 0 0 n m ) ，在最小线宽不断缩小、 集成度和芯片面积以及实际功耗不断增加的情况下，物理极限的逼近使影响v l s i 可靠性的各种失效机理效应敏感度增强，设计和工艺中需要考虑和权衡的因素大 大增加，剩余可靠性容限趋于消失，从而使v l s i 可靠性的保证和提高面临巨大 的挑战。高效的v l s i 测试方法显得越来越重要。 图1 1 是一个v l s i 芯片制造过程，由图可知整个过程需要不同类型的测试。 对用户需求和功能规范的测试通常称为“审查”，对设计过程的测试称为“设计验 证”，对制造过程的测试就是集成电路领域常说的“测试”，也是本文所采用的测 试的含义。传统的测试方法是使用自动测试设备( a u t o m a t i ct e s te q u i p m e n t ，简 称a t e ) 对被测电路施加测试向量，捕获电路的输出结果与预期的正确结果进行 n d e t e c t i o n 测试产生方法研究 比较，以判断电路中是否存在某一类型的故障。随着单片v l s i 电路功能的日益 复杂和集成密度的倍增，除了采用传统的测试方向外，近年来，自动测试生成【1 3 】 ( 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 t p g ) 、可测性设计【4 1 ( d f t ) 和内建自测 试【5 - 7 1 ( b u i l t i ns e l f - t e s t ，b i s t ) 等更为先进的测试技术和策略成为了研究热点。 用户 功能正常的芯片 图1 1 v l s i 芯片的制造过程 a t p g 是一种确定性的自动测试生成方法，它根据被测电路的模型来生成测 试集。与随机测试生成( r a n d o mt e s tg e n e r a t i o n ，r t g ) 相比，a t p g 代价更高， 但它能产生简短、高质量的测试。 可测性设计( d f t ) 是一种控制测试成本的方法，它要求电路设计工程师设 计易于测试的电路，需要i c 设计部门制定周密细致的d f t 规范和规则。d f t 技 术可以提高电路的可控制性、可观察性和可预测性，降低测试成本。 内建自测试( b i s t ) 是在设计电路时集成功能电路用于自我测试功能的技术， 以此降低测试成本和对自动测试设备( a t e ) 的依赖程度。价格高昂的先进a t e 也无法跟上最新i c 高速时钟频率的要求，而且很多电路用传统测试方法不方便测 试，比如没有直接的外部引角。于是，就提出了将原本置于传统a t e 中的测试产 生电路、测试响应电路和特征分析电路嵌入到i c 芯片中去的新策略，即内建自测 试技术。 1 2n d e t e c t i o n 测试介绍 固定故障模型的应用非常广泛，但是它仅为固定故障产生测试向量，并没有 考虑在实际生产中可能要会到的其它故障类型。很明显，随着集成电路制造工艺 的发展，仅靠较高固定故障覆盖率难以保证产品的质量。同时，实际生产中很多 故障都是不可知的，为每一种故障建立故障模型是不现实的。对于一个有上亿晶 体管的芯片，不可能为每一种可能的故障产生测试向量。 2 硕士学位论文 大量的实验表明：一个固定故障被检测的次数越多，激活此点非模型故障的 概率越大。所以可以通过多次检测某个固定故障点来激活此点的非模型故障。文 献【8 】提出了一种n - d e t e c t i o n 测试，n d e t e c t i o n 测试是指对于电路中的任何固定故 障都用不同的向量至少检测n 次。电路中的很多非模型故障都可以用这种测试集 检测。相对于n d e t e c t i o n 测试，传统的固定故障测试称为单检测测试( s i n g l e d e t e c t t e s t ) 。 1 2 1 固定故障模型 一个电路，由于某种原因导致其表现出来的功能与原来设计的不一致时，称 这个电路已经失效( f a i l u r e ) 。而故障( f a u l t ) 是指一个电路物理上的缺陷，它 有可能使得这个电路失效。为了测试电路，需要对被测电路( c i r c u i tu n d e rt e s t ，简 称c u t ) 施加一个输入测试集，然后将这个输出与无故障电路的输出做比较，判 断此电路是否有故障。每个输入向量称为测试向量，为了完整的测试一个电路需 要很多测试向量。如果c u t 是一个含有n 个输入的组合逻辑电路，为了测试固定 型故障( s t u c k a tf a u l t ，简称s a f ) 可以采用2 n 个测试向量。这种方法称为穷举测试 ( e x h a u s t i v et e s t i n g ) 。如果一个电路通过了穷举测试，就可以不管其内部电路结 构，认为这个电路没有功能故障。但是当n 很大时，采用穷举测试是不现实的， 而且这种测试方法对含n 个输入的时序电路效果有限。这种采用穷举测试集对组 合逻辑电路进行测试的方法叫做功能测试( f u n c t i o n a lt e s t i n g ) 。 一个更好的方法是基于电路结构信息和故障模型( f a u l tm o d e l ) 选择具体的 测试向量，这种测试方法称为结构测试( s t r u c t u r a lt e s t i n g ) 。 结构测试都是基于一定的故障模型，同时，为了方便产生和评价测试集，也 要用到故障模型。一般来说，一个好的故障模型即要能够很好的反映缺陷的特征 又要在故障模拟和测试产生方面有效率。文献【9 】提出了多种故障模型，每种故障 模型都有自己反映缺陷的特征。 故障的模型与电路的模型紧密相关，因此对应于不同的设计层次可以有不同 的故障模型。行为级( 1 宦e h a v i o r a ll e v e l ) 又称为高级( h i g hl e v e l ) 的电路描述。 这个级别的故障模型主要涉及电路功能而与制造缺陷没有明显的关系，这种级别 的模型更多地用于基于模拟的设计验证。 寄存器传输级( r e g i s t e rt r a n s f e rl e v e l ，简称r t l ) 的电路描述包含结构化 的电路信息，逻辑电路描述包含更详细的门级网表。在这个级别，固定故障模型 是数字测试领域使用最普遍的故障模型。它假定电路一个固定故障仅仅影响了门 的互连，每一个连线可以有两种类型的故障：固定l 故障和固定0 故障。本文中 的研究是基于固定型故障模型。 晶体管级的故障模型有固定开路故障( s t u c ko p e nf a u l t ) 和固定短路故障 ( s t u c ks h o r tf a u l t ) 等，这是门级的故障模型。此模型将晶体管作为理想开关， n d e t e c t i o n 测试产生方法研究 假设只有一个晶体管处于固定开路或短路状态。固定开路故障可以转化为固定故 障来检测，固定短路故障可以通过静态电流( 易d d ) 测试检测。 固定故障( s t u c k a tf a u l t ) 是建立在假设电路是由布尔门互连基础上的模型。 假定一个固定故障仅仅影响了门的互连，每一个连线可以有两种类型的故障：固 定1 故障和固定o 故障( 通常写为s a 1 和s a 0 ) 。因此，具有固定1 故障的线 将一直处于一种逻辑状态，而与驱动它的门的正确输出无关。 一般来说，几个固定故障可以在电路中同时出现。电路中每一条线都可能有 3 种状态：s a l ，s a 0 和无故障，对于一个有n 条线的电路，所有n 条线的组合减 去唯一的一种全部无故障的情况即可得所有可能的故障数：3 n _ 1 。这样一个中等 规模的数n ，也会需要一个很大的固定故障规模。因此实际测试中仅考虑单固定 故障( s i n g l e s t u c kf a u l t ，简称s s f ) 模型。单固定故障模型假设电路中只有一条 逻辑门之间连线有故障，此故障线永远是0 或者1 ，一个有n 条连线的电路至少 可以有2 n 个单固定故障。本文所涉及的固定故障都是指单固定故障。 故障输出 图1 2 一个单固定故障的例子 如表1 2 所示的单固定故障例子，o r 门的输出标示一个固定为l 的故障。如 果o r 门的正常输出是1 ，即它的输入为0 1 、1 0 或1 1 ，则这个故障不影响电路中 的任何信号。可是如果o r 门的输入为0 0 ，则在正常电路中会产生一个0 输出而 这个故障电路o rf - j 的输出仍然为l 。图中显示o r 门的输出连到a n d 2 上的情 况，正常值为0 ，故障值为1 。如果将a n d l 的输入置1 l ，即将a n d 2 的另一个 输入置l ，图中所示故障即可测。输入向量11 0 0 来测试固定1 故障，得到与正常 输出0 不同的故障输出l 。 单固定故障模型( s s f ) 应用非常广泛，许多其他类型的故障模型都用到了s s f 的原理和技术并对其进行了扩展。 ， 1 2 2 固定故障的测试产生和故障模拟 基于具体的故障模型产生测试向量，虽然不能保证检测所有可能的故障。但 是故障模型为测试集的故障检测能力提供了一种定量衡量的方法即故障覆盖率： 故障覆盖率= 塑鼍襻 ( 1 1 ) 4 -i丫d l l o o 硕士学位论文 因为存在不可测故障( 冗余故障，r e d u n d a n tf a u l t ) ，不可能获得过且过1 0 0 的故障覆盖率。不可测故障是指没有测试向量能够将包含此故障的电路与正常电 路区分开来。于是，人们将故障覆盖率修改为故障检测效率： ，故障检测效率= 恿丽面篱笔墨芒巢 。， 为了计算故障检测效率，需要确定不可测故障的数目。 测试产生( t e s tg e n e r a t i o n ，简称t g ) 是一个涉及许多交互因素的复杂问题。， 主要方面有：t g 的成本，生成向量的质量和施加测试的成本。 t g 的成本依赖于测试生成方法的复杂度。测试生成方法可以分为三类：穷 举法，随机生成法和确定性生成法。如果组合电路的原始输入较少时，穷举测试 集包含所有的测试向量可以获得1 0 0 的故障覆盖率。随机测试生成( r t g ) 是 一种简单且成本较低的的测试生成方法，它的输入由随机的测试向量组成。一个 向量只要它能检测到新的故障，就会保留在测试集中。用这种测试生成方法要想 获得较高的故障覆盖率，需要很多的测试向量。确定测试的质量( 如故障模拟) 也是一个开销很大的过程。同时，一个较大的测试集施加到被测电路上进行测试 时开销会更大，因为增加了测试实验的时间和测试仪的内存开销。对大电路采用 随机测试生成方法很难获得满意的故障覆盖率。 与r t g 不同的是确定性测试生成( d e t e r m i n i s t i ct e s tg e n e r a t i o n ，简称d t g ) ， d t g 基于故障模型来产生测试。任何一种确定性的测试生成算法，对于电路中的 每个固定故障，都必须解决两个问题：激活故障和传播故障。激活故障是在故障 点产生一个与故障值相反的值。传播故障是将故障点的值传播到电路的原始输出。 故障效应传播的过程称为敏化，故障点取值的可观测性将影响故障传播的难度。 如果一个测试激励了被测电路中的一个故障并且将其故障效应传播到了电路的原 始输出，则称该测试覆盖了这个故障。由此可见，确性性测试生成比随机测试生 成要复杂，但是其产生的测试集较小且故障覆盖率高。 一般来说，随机测试生成方法与确定性生成方法通常结合起来使用。首先用 随机生成法获得6 0 8 0 的故障覆盖率，然后用确定性生成方法为那些难测故障生 成测试向量。 固定故障的确定性测试产生算法的研究已经非常成熟。二十世纪六十年代提 出的d 算法是一种经典的测试产生算法【1 0 0 1 1 。二十世纪八十年代，提出了 p o d e m ( p a t h o r i e n t e dd e c i s i o nm a k i n g ) 算法【l 引，采用分支限界法来搜索输入 向量空间，相对于d 算法大大提高了搜索的速度，可对较大电路产生测试。紧 接着提出的f a n ( f a n o u t o r i e n t e dt g ) 算法【1 3 】又成功地扩展了p o d e m 算法j 引入“头线( h e a dl i n e ) ”和“多路回退( m u l t i p l eb a c k t r a c e ) ”的概念来加速搜索 过程，其效率相对于p o d e m 算法又有很大的提高，f a n 算法因此也成为国际 n d e t e c t i o n 测试产生方法研究 上公认的比较有效的测试产生算法。其后，人们在门级测试产生的算法优化方面 又做了孜孜不倦的努力，实现了一系列的门级a t p g 系统【1 4 - l7 1 。到了二十世纪， 文献【1 8 】推出了一个计算效率更高的组合电路a t p g 工具，处理大规模i c 的能 力很高。 故障模拟的功能很多，可用它来计算给定故障模型的故障覆盖率，辅助测试 产生和测试集压缩等。故障模拟的输入包括电路网表，测试向量集和目标故障集。 若没有提供故障列表，故障模拟器将对待定的故障模型生成一个故障列表。并可 根据给定测试集将故障列表中的故障分为可测故障和不可测故障。当一个故障能 被给定测试集检测时，将从故障列表中删除，避免重复模拟。所以故障模拟可统 计可测故障，计算故障覆盖率。如果故障覆盖率达到一个预期目标值就停止模拟， 删除末模拟的向量，则这种故障模拟可以进行测试集的压缩。图1 3 所示为故障 模拟在测试生成中的作用。 停止 图1 3 故障模拟在测试生成的作用 故障模拟的基本原理和过程如图1 4 所示，其中模块c 0 是无故障电路，模块 c ( f i ) 表示包含故障f i 的故障电路。相同的测试向量应用到所有的模块上，通过比 较故障电路的同无故障电路输出，可以判断该测试向量具体可测哪些故障。 图i 4 故障模拟过程 6 硕士学位论文 1 2 3n d e t e c t i o n 测试产生 n d e t e c t i o n 测试产生是指对于电路中的可测固定故障都至少产生n 个不同的 向量。传统的n d e t e c t i o n 测试产生方法是：研究改进已有的单检测a t p g 工具， 使之能够对每个故障产生多个向量【1 9 。2 1 】。这种a t p g 算法每次都为目标故障产生 一个测试集，如果某个故障被检测了n 次，则从目标故障集种删除，然后对检测 次数小于n 次的故障继续产生测试，直到所有的故障都被检测n 次，图1 5 给出 了一个n d e t e c ta t p g 算法【19 1 。难测故障使得这种a t p g 程序的运行时间很长， 同时这种测试产生方法没有对测试集进行压缩，产生的测试集非常大。 1 p e r f o r ms i n g l e - d e t e c tf a u l ts i m u l a t i o nw i t hs i n g l e - d e t e c tp a t t e r n s e tt if o ra l lf a u l t s 2 s a v ea l lf a u l t sd e t e c t e db ys i n g l e d e t e c tf a u l ts i m u l a t i o nw i t h p a t t