（通信与信息系统专业论文）基于粒子群算法的数字集成电路测试生成研究.pdf

哈尔滨工程大学硕士学位论文 摘要 随着微电子技术的进步，集成电路的规模越来越大，结构也越来越复杂， 这使得数字集成电路的测试生成变得越来越难。那些传统的测试生成算法已 不再适用。国内外的许多学者已经提出了“基于遗传算法的数字电路的测试 生成算法”。该算法对于某些电路是非常有效的，在很大程度上缩短了测试时 间，提高了测试效率。但它还不是一种普遍适用的有效的算法。本文在基于 模拟的测试生成算法的基础i - n 用粒子群算法生成电路的测试集。 本文以数字集成电路的测试生成为研究对象，采用单固定型故障模型， 以提高算法的故障覆盖率和减少测试生成时间为主要目标，将一种新型的、 结构简单的算法一粒子群算法及其改进算法，应用于组合电路的测试生成、 时序电路的初始化、时序电路的测试序列的生成和测试集优化。本文的主要 研究内容和所取得的成果如下： 1 将粒子群算法威用于组合电路的测试生成，与基于遗传髀法的测试生 成算法相比，缩短了测试时闯，提高了故障覆盖搴。表明了算法的有效性。 2 蘩l 溺粒子群算法避葶亍嚣痔电路豹耪始纯，潮予该算法墓裔蠢在静著雩予 性和选择性，因此在较短的时间里就能使尽可能多的触发器有确定的状态。 实验结果袋明了该算法的可行性。 3 ，秘麓粒子饕算法避孬霹亭壤赣溪l 试彦剜戆奄残。实验绥暴袭臻该冀法 能有效的提高故障覆盏率和减少测试生成时间。 4 利用粒子群算法优化电路的测试集。时序电路中触发器的数目越大， 测试序歹l l 就越长，占用缀多内存空阙。该算法g l 搿效的压缩测试集，从两褥 羁电路静最小瓣试集。实验结采表明了算法静有效经稻可行毪。 5 在箍于粒子群算法的测试生成、时序电路初始化、电路测试集的优化 各算法的熬础上，用改嫩粒子群算法代替各算法中的粒子群算法，结果表嬲 改透算法露雯爵戆收敛靛，致透冀法雯秀有效。 关键词：数字集成电路；测试生成；粒子群算法；初始化；测试集优化 蹬尔滨工程大学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h em i c r o e l e c t r o n i ct e c h n i q u e ，t h es c a l eo ft h e i n t e g r a t e dc i r c u i t sb e c o m e sm o r ea n dm o r el a r g e , a n dt h es t r u c t u r eb e c o m e s m o r e a n dm o r ec o m p l e x ，w h i c hl e a d st ot h et e s tg e n e r a t i o nf o rd i g i t a li n t e g r a t e dc i r c u i t s b e c o m i n gm o r ea n dm o r ed i f f i c u l t t h o s et r a d i t i o n a lt e s tg e n e r a t i o na l g o r i t h m s a r en o ta p p l i c a b l ea n ym o r e 。a b r o a da n dd o m e s t i cs c h o l a r sh a v ec o m eu pw i t ht h e g a st e s tg e n e r a t i o na l g o r i t h m t h ea l g o r i t h mi sg r e a t l ye f f i c i e n tf o rs o m ec i r c u i t s b e c a u s ei td e c r e a s e st h et e s tt i m ea n di m p r o v e st h el e s te f f i c i e n c y b u ti ti sn o t u n i v e r s a l l ye f f i c i e n ta l g o r i t h m t h ew o r kp r o p o s e st e s tg e n e r a t i o nm e t h o db a s e d o np a r t i c l es v c a l q p 娃o p t i m i z a t i o no nt h eb a s eo f s t p g t h i sd i s s e r t a t i o ns e l e c 招t h ed i g i 粒di n t e g r a t e dc i r c u i t sa sr e s e a r c ho b j e c t sa n d u s e st h es i n n es t u c k - a tf a u l tm o d e l r e g a r di n e a s i n gt h ef a u l tc o v e r a g ea n d d e c r e a s i n gt h et e s tt i m ea sg o a l s i tp r o p o s e san e wa n ds t r u c t u r e ds t m # a l g o r i t l m a - - p a r t i c l es w a r mo p t i m i z a t i o nt h a ti su s e dt og e n e r a t et h et e s tp a t t e r n s o fc o m b i n a t i o n mc i r c u i t s ，i n i t i a l i z et h es e q u e n t i a lc i r c u i t s ，g e n e r a t et h et e s t p a t t e r n so fs e q u e n t i a lc i r c u i t s o p t i m i z et h et e s ts e to fc i r c u i t s 皿em a i nc o n t e n t s a n dc o n t r i b u t i o n so f t h i sd i s s e r t a t i o na r ea sf o l l o w s ： l 。g e n e r a t e st h et e s tv e c t o r sf o rc o m b i n a t i o n a lc i r c u i t su s i n gp s o 。w h i c hi s c o m p a r e dt ot h ea t p gb a s e do ng a t h ee x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h e e f f i c i e n c y - - - - d e c r e a s i n gt h et e s tt i m ea n di m p r o v i n gt h ef a u l tc o v e r a g e 2 + i n i t i a l i z e st h es e q u e n t i a lc i r c n i t su s i n gp s o p s oh a si n n e rp a r a l l e l i s m a n ds e l e c t i o n s oi tc a ni n i t i a l i z em u c hm o r ef l i p - f l o p si nm u c hl i t t l et i m e 。1 1 瓣 e x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h ef e a s i b i l i t y 3 g e n e r a t e st h et e s t s e q u e n c e sf o rs e q u e n t i a lc i r c u i t su s i n gp s o t h e e x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h em e t h o de 黼i m p r o v et h ef a u l tc o v e r a g ea n d d e c r e a s et h et e s tt i m ee f f i c i e n t l y 毒，c o m p a 或t h et e s ts e to ft h ed e t e c t e dc i r c u i t su s i n gp s o 骢l en u m b e ro f 嚷零滨工程大学硕士学位论文 t h ef l i p f l o p si nas e q u e n t i a lc i r c u i ti sm u c hl a r g e r , t h et e s ts e q u e n c ei sm u c h l o n g e r , a n dt h e yn e e dm u c hl a r g e rs t o r a g e 弧em e t h o dc a l lc o m p a c tt h et e s ts e t e f f i c i e n l l ya n dg a i nt h em i n i m a lt e s ts e to ft h ed e t e c t e dc i r c u i t 。豫e x p e r i m e n t a l r e s u l t sd e m o n s t r a t et h ee f f i c i e n c ya n df e a s i b i l i t yo f t h em e t h o d 5 o nt h eb a s e so ft h et e s tg e n e r a t i o nu s i n gp s o ，i n i t i a l i z a t i o no ft h e s e q u e n t i a lc i r c u i t su s i n gp s oa n dc o m p a c t i o no ft h et e s ts e tu s i n gp s o ，w e s u b s t i t u t et h ei m p r o v e dp a r t i c l es w a r mo p t i m i z a t i o nf o rt h eb a s i cp a r t i c l es w a r l n o p t i m i z a t i o nt h a ti su s e dt og e n e r a t et h et e s tp a a e r u s ，t oi n i t i a l i z et h es e q u e n t i a l c i r c u i t sa n dt oc o m p a c tt h et e s ts e t 豫ee x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h e i m p r o v e da l g o r i t h mh a sb e t t e rc o n v e r g e n c ea n di sm u c hm o r ee 伍c i e n t k e yw o r d s ：d i g i t a li n t e g r a t e dc i r c u i t s ；t e s tg e n e r a t i o n ；p a r t i c l es w a r m o p t i m i z a t i o n ；i n i t i a l i z a t i o n ；t e s ts e tc o m p a c d o n 哈尔滨工程大学 学位论文原创性声明 本人郑熏声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明弓| 用的波容外，本论文不包含任何其勉个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) 堡丝函 日期：孙年? 月夕 e t 哈尔滨工程大学硕士学位论文 第1 章绪论 随着微电子技术的进步、超大规模集成电路的飞速发展，数字集成电路 的测试生成变得越来越困难。现代设备的研制生产、维护和运行，对大规模 集成电路测试技术提出了越来越高的要求：对计算机运算速度的要求越来越 高，所需计算机的内存容量也越来越大，使得某些现有的测试生成算法失去 了实用价值。因此，研究有效的测试生成算法具有重要的理论价值和现实意 义。 1 1 研究目的及意义 集成电路的规模越来越大，结构也越来越复杂，数字集成电路的测试生 成变得越来越困难。大型数字集成电路的测试日趋迫切，寻找新型、有效的 测试生成算法成为测试领域中一个重要的研究课题。 一个系统或电路在设计和制造过程中以及运行过程中都需要进行测试， 以检验它是否符合设计要求或是否能正常工作。对数字系统来说，主要是测 试其功能、时序关系和逻辑关系等。如果仅仅是测试一个电路或系统是否存 在故障，则称之为故障检测：如果不仅要检测电路或系统中是否存在故障， 而且要定位故障点，则称之为故障诊断。一般来说，故障检测和故障诊断统 称为测试。但二者是有细微差别的：测试是面对产品的检验来说，因此测试 的结果可能有故障，也可能没故障；而故障诊断一般是指在已确定系统或电 路有故障的前提下来确定故障的位置，所以故障诊断也可称为故障定位。 数字集成电路的测试生成与数字系统的故障诊断是紧密联系的。数字系 统故障诊断技术的发展，是同数字系统中的元件、结构和应用，特别是数字 计算机的发展密切相关的，由于数字系统已经广泛应用于各行各业，为保证 其可靠运行，故障诊断是一个必不可少的重要环节。在系统故障诊断中，核 心问题是确定施加什么样的激励能使故障激活，同时能在输出端测量出来。 1 哈尔滨工程大学l 甄士学位论义 阊样，数字集成电路的测试缴成识就是，求解一个( 或缝) 测试矢羹，使 拔测数簿激活，劳且能糁故障豹效应传撵到原始输趣端测量出来。测试生成 的基零目禄使确定测试矢量，当将其加委被测崤路时，能将正常电鼹与故障 电路嚣分开采。 魏在毒一些戏熟熬骥论秘实悉方法来进褥测试，毽计冀王传量翻溺试憨 歼销都比较大。尤其是现在的系统的规模越来越大，测试的矛爝也日盏尖锐。 豳_ l i ：，对予集成瞧路测试垒成算法的磷究一赢避行着。 数字集袋电路豹测试生成算洪不投翅予测试生成和救漳诊凝，蕊且霹强 用于印蒯娥路板的光援测试和加载板测试。另外，它也是集成魄路翻动测试 设备的核心技术之一。数字集成电路的测试生成技术，述可以为集成电路静 设诗、猃谖、综合窝钱纯笔提供蠢力豹技本支持。 数字集成电路测试生成算法的研究涉及到计算机、优化算法、微电子、 敬障诊断等学科领域杰静理论帮技术，爨育穰嵩的瑾论意义和实舔意义。箍 麓数字诗舅穰穗集成电鼹魏舞速发展，数字纂娥戆潞已经应瘸子诲多霉子数， 因此，数字集成电路测试生成算法的研究不仅舆露学术意义，还具商巨大的 效益。 1 2 豳内外相关研究情况 i 缀会毫貉籁试生成簿法静磷究现状 数字电路的测试最早是从研究组合电路的测试开始的，1 9 5 9 年e l d r e d 首 次提出了关于组舍电路的测试报告，该方法只能用于完成两级以内缀合电路 豹鼓除检测。在e l d r e d 恩懋夔夔麓l l 上，1 9 6 6 冬b 。a r m s t r o n g 提出了线逶 路敏他的方法，就是绘多级门邀鼹寻找一条从故艨点到原始输蹬端瀚敏化通 路，便故障信号在原始输出端能被观察副。当时人们认为，电路中盼非冗余 放障郡楚潴着一条逶路传播翻藤始输逛臻豹。蠢粼1 9 7 6 年，s c h n e i d e r 摊出 了一个反例，证明了某些故障信号只通过一祭通路是不可能传播到原始输出 端的，丽必须沿着两条或两条以上的路径同时向原始输蹬端传输，程原始输 蹬壤方骞甏裁鼹溅到故障接噼。 哈尔滨工程大学硕士学位论文 罗斯( r o t l l ) 在1 9 6 6 年提出的d 算法【1 1 是第一个完全的算法，d 算法克 服了一维通路敏化的缺点，考虑到故障信号传播到输出端的所有可能通路。 从多值逻辑理论来看，d 算法属于五值算法，它的五种状态为1 ( 1 1 ) 、0 ( 0 0 ) 、 x ( x x ) 、d ( i 0 ) 、d ( o 1 ) 。其中括号内的值中，前一部分代表正常值，后一 部分代表故障值，x a ( o ，1 ) 代表不定状态，d 表示信号线的正常值为逻辑1 ， 故障值为逻辑0 ，而j d 表示信号线的正常值是逻辑0 ，故障值是逻辑1 。每条 信号线可能有五个值1 、0 、鼠d 和d 。d 算法的两个基本操作是d 操作和 j 操作，d 操作就是选择一条或多条路径执行前向的故障敏化，使故障点的d 或d 向前驱赶直到原始输出端；j 操作又叫做反向线确认操作，是用来寻找 一个原始输入矢量，使敏化通路上所有门的值均满足要求。 d 算法对于任意非冗余的组合电路中的故障均能找到某个( 某些) 故障 的测试矢量，而且它的计算方法很容易用计算机来实现。但是在具体应用时， 由于计算工作量很大，尤其是对大型组合电路计算时间很长，以致很难付诸 实际应用。分析其原因是，在进行敏化通路的选择时其随意性太大，尤其是 考虑多通路敏化时各种组合的情况太多，然而真正有效的选择期望较少，因 此在做d 算法时，做了大量的返回操作。为了尽可能减少返回操作的次数， 大大缩短计算时间，出现了两种改进的算法：p o d e m 算法和f a n 算法。 g o e l 对d 算法做了有益的改进，提出了p o d e m ( p a t ho r i e n t e dd e c i s i o n m a k i n g ) 算法口】。p o d e m 算法事实上是个程序。它吸收了穷举法的优点，对 d 算法进行了有益的改进，大大提高了算法的运行速度，具有一定的实用意 义。该算法通过回退( b a c k t r a c e ) 确定满足目标的原始输入赋值，一个原始 输入被赋值后，通过前向蕴涵( f o r w a r di m p l i c a t i o n ) 来确定它对电路的影响。 如果目标不满足，则重复执行这一过程，如果出现冲突，算法就作回退，选 择一个没有试过的赋值。在p o d e m 算法中，对故障电路和无故障电路做逻 辑分析计算的过程对应于d 算法中的d 驱赶，但是d 算法中的反向蕴涵包 含在出始目标的确定和p i 的确定过程中，二者不同之处是：在d 算法中d 驱赶的方向选择是随意的，而在p o d e m 算法中一定要寻找d ( d ) 到p o 端最近的通路做驱赶；在做反向蕴涵时，p o d e m 算法要选择“最容易”和 “最困难”的路径，这样目标比较明确，成功的概率比较大，从而大大减少 啥尔滨工程大学硕士学位论文 d 箨法孛麓返鼙次数，提寒了遮舞速溲。 在p o d e m 算法的基础上，f u j i w a r a 和s h i m o n o 于1 9 8 3 年提出了f a n ( f a no u to r i e n t e d ) 算法牡l 。虽然p o d e m 葵法减少了返回次数，提离了溅试 生成的速凌，但是它不能及早发现不存强解的情况，因此无效的选择秘返圜 的次数还怒很多，为进一步减少返回的次数，提商测试速度，f a n 算法中主 要采取了以下尼点措施：( 1 ) 程磐法瓣簿一步尽霹黪多逸礁患巴唯一隐涵篷 盼信号值。( 2 ) 故障值分配给出故障礁确定或隐含的地方。( 3 ) 在d 前沿 中只有一个元件时，可以选择一条唯一确定的敏化通路。( 4 ) 反向蕴涵只要 翻圭导线麓霹鞋停止，蠢不登菇鹈爱话麓涵，圭磐线懿篷哥滋雄遥妥簸簌髯 去确认。( 5 ) 多通路的同时反斑蕴涵。( 6 ) 在多遘路蕴涵中，如果扇出点的 嚣标是矛嚣魏霹n o t ) 窝n ( p ，焱骂上箨壹骰恭涵，荠绘邀个寨窭煮p 赋 德，如聚崩出点p 翟n o t ) 或n 1 ( p ) 中肖一个为0 ，刚鲍扇出点继续徽反囱 蕴涵。如粜现行目标组及扇出点目标组均己空时，即都已到达主导目标线或 瓣瀵，澍扶c 楚转爨，然爱麸烹导嚣豁缀中菝次激疆主导鏊褥，菸绘它们 赋值，檄后再做蕴涵。 在f a n 冀法的基础上，s c h u l z 等人提出了s o c r a r e s 算法嘲，s o c 删s 冀洼主要携出了一静众嚣蕴涵避德，一耱改进豹嚷一鼓耗过獠，两辩辩f a n 黧法的多路回退过程也作了相_ 陂的改进。这些技术的应用，进一步减少了回 遗斡次数，瑟旦可以据蘸发现冲突以及冗余故障，提离了整个测试生成熬逮 发。 上述均为确定性算法，基于模拟懿缀合电路测试生成冀法籀述大豁上鼹 时事电路，下面将鬟瓣，这里簸不佟 l 逡。 在超大规模集成电路出现之前，缎台电路的测试生成算法已相当成熟， 虢着超大援模集成魄路兹出瑰，这些传统的算法纛不实用，逡切鬟要磷炎鼗 的测试生戚算法。由予利用掴擒设计技术可以将孵序电路的测试生成转化为 缀合电路的测试生成，因此，组合电路测试生成的研究尤其黛要，是数譬电 路溅试生成豹基磁。 2 时序电路的测试生成算法的研究现状 时序魄路由于内部有存储元件，玄瓣输出不仪决定于当髓的输入信譬， 4 蹬尔滨工程丈攀颈学位论文 而且决寇予襻储元件的状态，因此，时序电路的钡4 试生成比组食电鼹复杂褥 多。时序电路测试生成肖两种思路：第一，可以将时序电路转换成组合电路， 然掰幂j 麓组禽电路豹溯试生藏方法和理论进行溺试整成；第二，利掰算法童 接对时净逛貉进露溪l 试生成。 m u t h 提出的九值算法用丸值模型代替d 算法的五值模型，对时序电鼹 的测试生成用救治算法比五俊d 冀法驻有效。农使用重复阵列模型对，由予 时墩的熏复馥障效应，一个单故潞表现为多故障。九值算法充分考虑了这种 重复敌簿簸瘦，受龆霄效，大大躐少了d 算法牵路径选择豹次数。 e s s 黔盯狐l 测试耋基成器f 4 ，它燕一秘有效的爨适成测试生成算法。 e s s e n t i a l 算法采用的关键技术主要是：在开娥实际魏测试生成嚣， e s s e n t i a l 算法开始一个学习过程，在预处理阶段对电路结构进行分析以 了解毫薅瓣全蜀结枣奄及定位菠馕瑟路；在蓣闼采沼r t p ( 爱商时闻簸理) 技 术，在搂疮慕建f t p 戆自瓣阀处瑾) 按拳，；除鼹瓤隐含乡尽霹纛对装上 和黧汇聚瓣扁出点上避抒全局隐含。其测试生成分为三个黔段：赦障鞠关信惑 研究、故障效应传播、对未判决线进行判决。最遵要的一点是对电路信息进 行蹬究，涛搿蔼的工作疆供稿发拣倍感。 h i t e c 溅试生成琴统 5 1 ，袭致善溅试垒袋翡经糍，瑟生成器在前天懿萋 础上提出了几个关键技术，。h i t e e 将测试生成分为鼹个黔段：一是f t p 除 段，将故障激活并传播到原始输出端。二是r t p 阶段，进行初始状态的确认。 该涮试系统还采焉了p o d e m 算法的翔决技术和f a n 算法的赋值技沭。 f a t e s t 箨法，它怒一释只镶耀f t p 技术并蘩予p o d e m 算法的时序窀 路测试生成舅法。对于一个绘定鲍数障，它使用s c o a p c 测度馋计测试霭要 的时帧数爨，它首先确定激活故障所需要的最小数量的时帧，磁后检查被激 活的故障是番能在输出端观测蓟。该算法的优点憝可以快速的确认不能这铷 的状态，如滤测试生成，缺患是需要辩时蔽数量作出精确估计，否弼会浪费 大量时间。 上蘑箨法属于确定链算浚( d t p g ) ，虽然都可以取褥较离懿赦障覆盖攀， 但对大规模时序电路来说，其测试生成的时间也比较长。为了撮商时序电路 的震l 试效率，缩短溅试生成时润，采掰了基于模拟的测试警成算法( d t p g ) 。 哈尔滨工程大学硕士学位论文 d t p g 的基本思想是：基予前一个测试生成下一个待测矢量和序列，将这个 待测矢量或序列加到故障模拟器或逻辑模拟器，从模拟结果可以知道当前电 路状态和未检测故障所需状态之间的差距，若差距缩小，则将该矢量加到测 试矢量集中，否则丢弃，如此反复直到故障被检测到或待测矢量的数量已经 达到预置值。 基于模拟的测试生成是s e s h u 和f r e e m a n 于1 9 6 2 年提出的，他们指出故 障模拟器用于对待测矢量进行评估，检测到最多故障的测试矢量作为下。个 测试矢量，其它检测到故障的矢量送入栈以生产新的待测矢量。若待测矢量 没有检测到故障，将从栈中取出一个矢量作为当前的待测矢量，一直重复到 栈空为止。b r e u e r 于1 9 7 1 年提出另一种基于模拟的方法：待测矢量随机产生， 每次循环生成一定数量的待测矢量，通过故障模拟器对它们进行评估，从中 选出最好的一个作为下一个测试矢量，如此重复，直到检测完所有的故障为 止。 文献【1 1 】提出了一个c o n t e s t 算法，这是一个基于仿真的算法。它通 过改变测试矢量中的某一位来产生试验矢量，用一个代价函数来指导测试生 成，在不同的阶段使用不同的代价函数，算法中采用了并发性故障模拟 ( c o n c u r e n tf a u l ts i m u l a t i o n ) 。该算法的优点是结构简单，缺点是不能识别冗 余故障，故障覆盖率较低。 文献【9 】提出一种快速高效的故障模拟器p r o o f s 故障模拟器。该故障 模拟器综合了区分故障模拟( d i f f e r e n t i a lf a u l ts i m u l a t i o n ) ，单故障传播( s i n g l e f a u l tp r o p a g a t i o n ) ，和并行故障模拟的优点，使它们各自的不足达到最小。并 且该故障模拟器需要较小的内存，缩减计算门的数量，使整个算法的复杂度 达到了最小，是一个快速的时序故障模拟器。 文献【1 0 】- 【1 1 】提出了h o p e 并行故障模拟算法。h o p e 故障模拟器是在 p r o o f s 故障模拟器基础上发展起来的一种时序电路故障模拟器，提出了三 个关键技术来加速故障模拟过程。第一：压缩故障表；第二：采用新的故障 注入方法；第三：将静态故障排序与动态故障排序相结合。该算法的优点是 适用范围广，容易实现；缺点是不能识别冗余故障，产生的测试序列较长， 对于难测故障不能产生测试序列。 哈尔滨工程大学硕士学位论文 近几年来的基于模拟的测试生成算法中主要是：将遗传算法应用到测试 生成算法中。遗传算法是一个迭代过程，它模仿生物在自然环境中的遗传和 进化机理，反复将选择算子、交叉算子、变异算子作用于群体，最终得到问 题的最优解或近似最优解。在测试生成中，先随机产生n 个个体作为初始群 体p ( t ) ，该群体代表问题优化的一些可能解的集合，从这个群体出发，计算每 个个体的适应度( 适应度与所能检测到的故障数成正比) ，模拟进化过程( 选 择、交叉、变异) ，择优汰劣，然后生成新群体( 下一代) ，重复直到检测到 所有故障或达到最大代数为止。 文献 1 7 提出了基于遗传算法的时序电路的测试生成的框架。开始时随 机初始化测试矢量群体，用时序电路故障模拟器来计算每一个矢量的适应值， 生成的最优矢量被加到测试集，将该测试矢量加到故障模拟器模拟电路，删 除它能检测到的所有故障。整个过程一直重复直到故障覆盖率不能再有所提 高时为止。当初始群体选择的不合适时，产生的测试矢量将不会检测到任何 故障，这时，遗传算法将重新随机初始化群体来尝试着产生有用的测试矢量。 另一方面，不能保证电路会进入所希望的状态，长的矢量限制会增加测试时 间和故障的测试集，因此此文中采用时序深度的倍数作为测试矢量进步的限 制。结果表明：当采用无复制的选择和统一交叉会产生较好的结果，而变异 的概率对故障覆盖率不会有太大的影响。当群体尺寸为1 6 或3 2 时，= 进制 编码会产生较高的故障覆盖率。非重叠群体会得到较高的故障覆盖率，但是 重叠群体会将非重叠群体的运行速度提高1 3 倍。基于遗传算法的时序电路 的测试生成不局限于单固定故障模型，它同样适用与其它故障模型。 到目前为止，遗传算法在测试生成中已经取得了很大进展：如c r i s t “1 、 g a t t o f ”】、h p g a s t “1 等。c r i s 是基于g a 的较早提出的测试生成器，可用 于组合电路和时序电路，但不易激活难测故障，所以故障覆盖率较低。 g a t e s t 是一种基于时序电路的测试生成器，它通过一个故障模拟器 p r o o f s 计算每个待测矢量的适应度，g a 根据所有矢量的适应度选择一个 最优的作为测试矢量，但要激活一个难测故障，并把故障效应从触发器传播 到原始输出端仍然是个难题。h p g a s t t ”1 是基于并行g a 和故障模拟器 h o p e 的测试生成算法。因g a 测试产生器【1 6 】- 【”1 是并行执行的，即用多台处 哈尔滨工程大学硕士学位论文 理器同时执行测试生成，从而有效的缩短了测试时间。h o p e 故障模拟器是 建立在p r o o f s 基础上的一种高效并行故障模拟器，成功的避免了无效故障 的模拟，从三方面入手来加速故障模拟过程：通过将非扇出点故障映射为扇 出点故障而缩减故障数；采用功能故障注入；动态故障排序与静态故障排序 相结合。这些技术的应用，很大程度上加速了故障模拟过程，取得了更好的 试验结果，但仍需改进，以得到更高的故障覆盖率和更短的测试时间。 一定的算法对与某一些电路特别有效，基于模拟的算法由于不需要电路 信息，生成测试矢量的速度很快，所以适用与大规模集成电路，但对于难测 故障，由于缺乏电路相关信息，很难检测到。确定性算法对于大规模集成电 路测试非常慢，但有助于识别不可测故障及难测故障。所以研究新型、有效 的时序电路测试生成算法，仍然是一个至关重要的课题。 总的来说，时序电路的测试生成比组合电路的测试生成要困难得多。虽 然基于扫描设计的技术可以将时序电路测试生成的复杂性转化为组合电路测 试生成的复杂性，但是这一技术的代价需要增加l o 一2 0 的硬件开销。对于 集成电路的测试工作者来说，研究新型、有效的时序电路测试生成算法，仍 然是一个巨大的挑战。 1 3 测试生成的基本原理 在数字系统的设计、制造和应用阶段，不可避免地会出现故障，为了保 证其工作地可靠性，必须对它们进行测试。测试的基本思想是：在数字集成 电路的原始输入端施加输入矢量作为激励信号，观察原始输出端地响应信号， 并且与预期地正常响应相比较，二者相同，表示系统正常，系统中不存在故 图1 1 故障测试的基本模型 哈尔滨工程大学硕士学位论文 障，反之，表示系统中存在故障。 为了全面地测试电路，把所有可能地输入作为输入矢量，然后观察其响 应是否与原设计相符，以鉴别其是否存在故障，这种做法称为穷举法。穷举 法可以检测电路中地所有故障，但其测试地工作量太大。例如：一个具有1 8 0 个输入端地组合电路，如果用穷举法来测试，需要施加2 1 9 0 矾5 3 1 0 5 4 个测试 矢量。如果每旌加一个测试矢量及观察其响应所需时间为0 1 u s ，则测试完该 电路需要1 5 3 1 0 4 7 s ，约为4 8 x 1 0 ”年。这种测试显然是不现实的。那么就应 该找到能在短时间内选择最少的测试矢量也能达到相同效果地测试生成算 法。 数字集成电路的测试生成算法主要完成两个目标：( 1 ) 故障激活，即在故 障点产生一个与故障值相反的信号值；( 2 ) 故障传播，即将故障效应沿着某一 条路径传播到原始输出端，用以测试故障值是否与正常值不同。数字集成电 路的测试生成，就是寻找能激活故障、并将故障能够传播到原始输出端的输 入矢量。 1 4 研究内容及结构安排 本文以数字集成电路的测试生成为研究对象采用单固定型故障模型，以 提高数字集成电路测试生成算法的效率和故障覆盖率为主要研究目标，研究 一些新型的数字集成电路测试生成算法。 本文的其它主要内容和结构安排如下： 第2 章：基于模拟的自动测试生成。首先介绍测试的相关概念、故障及 故障模型，然后介绍目前的测试生成算法、算法主要评价指标，接着介绍基 于模拟的自动测试生成过程。最后对本文所采用的故障模拟器- p r o o f s 的主要特点作简要介绍。 第3 章：基于粒子群算法的组合电路的测试生成。介绍了蚂蚁算法的发 展过程、基本原理，给出了粒子群算法用于组合电路的测试生成的具体实现 过程，并根据得出的仿真结果与相关算法进行比较。 第4 章：基于粒子群算法的时序电路的初始化。提出了粒子群算法用于 哈尔滨工程大学硕士学位论文 时序电路初始化的具体实现过程，给出了仿真结果，并与相关算法进行了比 较、分析。 第5 章：基于粒子群算法的时序电路的测试生成。介绍了粒子群算法在 时序电路测试生成中的具体应用和表现，给出了仿真结果，并与相关算法进 行了比较、分析。 第6 章：测试集的优化。提出了粒子群算法在测试矢量动态压缩中的实 现方法，给出了实验结果，并与相关算法进行了比较。 1 0 哈尔滨工程大学硕士学位论文 第2 章基于模拟的自动测试生成 基于模拟的自动测试生成，由于避免了回溯的复杂性，只需作前向处理， 大大减少的测试时间，因此在自动测试生成中应用得相当广泛。本文研究的 就是基于模拟的自动测试生成。 2 1 测试生成的相关概念 1 输入激励 输入激励是在电路的原始输入端所加入的输入值。对于组合电路，输入 激励又称为输入矢量( i n p u tv e c t o r ) 或输入模式( i n p u t p a t t e r n ) 。对于时序电 路，输入激励又称为输入序列( i n p u ts e q u e n c e ) 。 2 输出响应 在输入激励的作用下，电路的输出称为电路对应于输入激励的输出响应。 无故障电路( f a u l tf r e ec i r c u i t ) 的输出响应称为正常输出响应，故障电路( f a u l t c i r c u i t ) 的输出响应称为故障输出响应。 3 钡9 试生成 测试生成( t e s tg e n e r a t i o n ) 是产生电路的测试矢量或测试序列的方法或 算法。 4 测试码 测试码( t e s tc o d e ) 又称为测试矢量( t e s t v e c t o r ) 或测试模式( t e s t p a t t e r n ) ， 是指能够检测数字集成电路中某个故障的输入激励代码。对于组合电路，一 个测试码是一个原始输入激励。对于时序电路，一个测试码是若干个原始输 入激励的组合，又可称为测试序列( t e s ts e q u e n c e ) 。 5 期4 试集 测试集( t e s ts e t ) 为若干测试码的集合。某个故障的全部测试码的集合 称为该故障的完全测试集，被测电路所有n - 7 浏j 故障的完全测试集的集合，称 为电路的完全测试集，简称电路的测试集。 埝尔滨王穗大学硬士攀霞论文 6 可测故障 搿测藏薄( d e t e c t a b l ef a u l t ) 逶豢鍪少莓羧一个溺试必薰嚣羧溺潮熬教簿。 7 研：可测敞障 不可测故障( u n d e t e c t a b l ef a u l t ) 又称为冗余故障( r e d u n d a n tf a u l t ) ，是 指没肖任何一个湔试矢爨能够检测溺的故障。 8 等效故障 等效馥潦( e q u i v a l e n t f a u l t ) ：若救瓣群窝救漳p 静测试集分别爨疋和易， 如聚肖砭c ，疋 ，郎瓦= ，则称故障货和p 是等效故障。 9 支配和隶属故障 支嚣藏障( d o m i n a n t f a u l t ) ：菪敬簿搿葶瑟毅瘴p 豹溯试集分弱怒瓦羁毛， 如果肖疋c ，贝称故障搿隶属故障p ，两敞障p 支配故障搿。 1 0 。敬瓣覆箍率 故障覆盖率( f a u l tc o v e r a g e ) ：蹙措被测电路测试繁所麓检测剿雏故障数 与被测电路故障总数的比愎。即： 五= 詈1 0 0 ( 2 - 1 ) v 式中，袭示赦障覆盏率，虬袭示测试生成算法产生的测试集能够捻 溅翻黪敌障总数，表承羧溅毫鼹审麓敏辕惑数。 1 l 灞4 试生成时间 测试生成辩闫( t e s tt i m e ) ：溅试生娥冀法生成被溺电路测试熊所芯费躲 霹重阔，一般用c p u 时闻束表示，攀僚建移( s ) 。 以下三个檄念是时序激路所特窝豹。 1 2 。嚣步謦确 同步序列( s y n c h r o n i z i n gs e q u e n c e ) ：悬将系统从强意状态转移到同一个 已觚寒态豹序列。毽并嚣糍个系统粼褥在燕步痔刭。 1 3 引导序列 q l 导序列( h o m i n gs e q u e n c e ) iw 以使系统从一个未知状态“弓i 导”到綮 些跫籁貔寒态( 霹棂据不黼爨襄应黪魏采爨是宋态) 熬羧入窍列。 1 4 区分序列 蹬尔演工纛大学疆士学往论文 障。 区分序列( d i s t i n q u i s h i n gs e q u e n c e ) ：能够根据不同的响威序列来区分敞 2 2 故障和故障横型 1 赦障 藏溱是指一令嚣 孛、电路鬻系统豹物理缺陷，它可麓傻遽个元 孛、惫鼹 和系统失效，也可能不失效，也就怒说，存在有一定故障的元件、电路和系 统仍有可能完成其固商的逻辑功能。 教瓣霹蔽裂霉敢骧戆缝凄、数薅篷、兹障懿羧度窃范嚣黻及数障夔懿阗 间隔等参数来描述。敞障性质是指故障属于逻辑敝障还是非逻辑故障。凡怒 使电路或系统中某一节点的逻辑值为正常值的相反值的故障叫做逻辑故障， 如元件输入端开路、输寤端短路、元件损坏以及巍态故障等均耀于逻辑故障。 豫逶辑簸簿瑷井斡蔽漳都称为j 逻瓣敌漳。藏障簸是捂电路袋系统中藏障产 生的错误逻辑值是固定的，还是变化的；如果悬围定的，那么它的固定值撼 多少。故障的限度及藏圉是指故障的影响是局部裂的还是分布烈的。局部敞 漳影翡擎变量，恧分农鐾竣蹲影穗多交量。餐翔邂辑载骧一簸都是嚣部墼羧 障，而时序电路中的赦障一般属于分布型的故障。故障的时闯间隔是用来说 明故障怒永久性的，还是间歇性的。 2 撤障模型 为了讶究酸簿对壤路或系统静影确诊断敬簿鹃位霆，登须对敬障连雩亍分 类，并凰构造最典型的故障，这个道程叫做故障的模型化。即建立被测系统 的故障横溅。 建立簸障摸墅秘蒸零覆簧毒秘个：一是藏障骥羹痘戆难旗逵爱骧菜一藏 障对电路成系统的影响，二是故障横型应尽可能简单，以便于进行运算。下 面介绍几种常用的故障模型： ( 1 ) 圈定型故障 固定黧故障( s t u c kf a u l t s ) 主簧是指电路或系统中菜一嘏信号线上信罨 的不可控性，即在系统运行过程中该信号永远固定在某一个德上。如果该线 蹬象滨工耧夫学矮学坟论文 ( 或该点) 固定在逻瓣高电平上，则称为固定l 故障( s t u c k a t 1 ) ，简记为 s a - l ；如果该线( 或该点) 固定在逻辑低电平上，则称为固定0 故障 ( s t u c k a t - o ) ，簿记瓷轴a - o 。故簿模銎s 1 8 - l 巍s _ a 1 0 枝裹始终霞节焘上鹣逻 辑电平停留在逻辑离嗽平或逻辑低电平上的各种物理故障的集合，而不是单 指节点岛电源或与地之间的短路。 电鼹元俘的损坏、连线的开爨和大部分的趣鼹故障都能瘸固定型故障模 鍪准确热籀述凄来，势盈描述篱攀，方便楚瑾敏障，嚣筵强宠鳌敲簿模登在 实际应用中用得最普遍。固定型故障模型可分为单固定型故障模型和多固定 型故障模型。 ( 2 ) 褥接教簿 固定型故障主要怒指系统内节点上的信号不能永远是输入信号控制的敞 障，它一般不会改变电路的拓扑结构，即不会使电路或系统的基本功能有根 本性的变征。电路中髅号线连接程一起鲍故障稔为掭接故障，+ 该故障斡壤援 是多释多样的，完全霄可麓改交电路的拓矜结榆，导致系统静功戆发生檄本 性的变化。常见的桥按故障有两种。一是元件输入端之间的桥接故障；二怒 元件输入端和输出端之间的反馈式桥接故障。 一个元箨赣入壤之阂豹耩接敬簿一羧形成线与关系。一令元 孛输入臻酾 输出端之间的反馈式轿接故障比较炭杂，发生这类故障时有w 能把组合电路 改变成时序电路，甚麓使电路发生髓荡而趋于不稳定。 ( 3 ) 甏态故障 暂淼故障( t e m p o r a r yf a u l t s ) 麓相对于固寇凝故障磊言的。它有两种炎 型，即瞬态故障( t r a n s i e n tf a u l t s ) 和间歇性故障( i n t e r m i t t e n tf a u l t s ) 。 瞬态放障不是由系统或电路中硬件弓f 起的故障，两是由曦源的于扰和掰 粒子戆辗嚣等嚣嚣遘艘豹，嚣魏这类教漳无法人为予敬重复滋瑷。 间歇性故障是可熏复出现的非阐定型故障。产生这类故障的原因有：元 件参数的变化、接插件的不可靠、烬点的虚焊和松动以及温度、湿度和机械 扳动等其它舔境原因铸。 ( 4 ) 辩浠故障 时滞故障( d e l a yf a u l t s ) 主要考虑电路中信号的动态故障，即电路中务 1 4 哈尔滨工程大学硕士学位论文 元件的时砥变化和脉冲倍号的边 蓊参数的交能簿。这类敌障圭黉导致辩寄配 套上麴错谈，因此在对廖电跤中影响较大。 本文将单固定型故障作为研究的对象。其原因主要裔以下凡方面： 它嚣要处理的故障憨数少，易于溯试奎戏，弱子精确分丰蓐故障覆燕情 嚣，易于赦障定经。 实践表明，只要单故障的覆盖率达到9 0 以上，则单故障钡9 试集也能 裣凋箕它类蓬的