（计算机应用技术专业论文）数字集成电路测试生成算法研究.pdf

堕玺鎏銎三盔主巫圭兰垡笙塞数字集成电路测试生成算法研究摘要数字集成电路是当今发展最快的技术领域之一，随着数字电路设计及工艺技术的发展，电路的规模和复杂度日益增大，使得电路的测试生成日益困难，并已成为集成电路芯片生产的瓶颈。对于复杂的大规模集成电路，传统的测试生成算法已不再适用，因此研究新型有效的数字集成电路测试生成算法具有十分重要的理论价值和实际意义。集成电路的测试生成问题是数学上公认的难题一n p 完全问题，在过去的几年中，国内外的学者虽然提出了许多新的测试生成算法，但是到目前为止还没有一种算法能适合所有的大规模集成电路，集成电路的测试生成问题已成为一个重要的研究课题。本文采用单固定故障模型和路径时滞故障模型，对数字集成电路的测试生成进行研究，为提高故障覆盖率，减小测试生成时间，重点研究了以下内容：1 综述了集成电路测试生成技术的研究现状和发展概况，指出了目前存在的问题和不足之处，并且展望了未来的发展趋势。2 研究了基于二值h o p f i e l d 神经网络的组合电路测试生成算法。并在此基础上，将三值神经网络应用于组合电路测试生成算法中，用三值神经网络表示数字电路，可以减小搜索空间，避免很多不必要的赋值，因此可以在保证具有较高故障覆盖率的情况下，减小测试生成时间，提高算法的测试生成效率。通过构造电路的约束网络，求解约束网络对应能量函数的最小值点得到故障的测试矢量。3 研究了基于布尔差分的组合电路测试生成算法。针对布尔差分法存在大量异或运算的问题，提出了组合电路单固定故障测试生成中求解一阶布尔差分的简化方法，它不用异或运算，而是通过求解恒等式来得到完全测试集，避免了大量的布尔运算。同时，通过对二阶布尔差分的剖析，得n t 二阶布尔差分法的简化算法，为双故障的测试生成提供了方便。4 研究了组合电路中非鲁棒性路径时滞故障的测试生成算法。时滞故障是集成电路故障中的一种，电路中如果存在时滞故障，将导致它在给定的高速时钟频率下无法正常工作。因此研究时滞故障的测试生成算法非常重要。迄今为止，国内外学者提出了很多时滞故障模型，其中路径时滞故障模型是最常用的。路径时滞故障模型的缺点是故障的数目随电路中门的数目成指数比例增长，即“指数爆炸”，使得在较短时间内对电路生成测试矢量非常困难。本文将使用路径分支转换技术，使用较成熟的固定故障测试生成算法对组合电路中非鲁棒性路径时滞故障生成测试矢量，该算法能够避免“指数爆炸”，提高故障覆盖率，减小测试生成时间，改善测试生成效率。关键词测试生成算法；神经网络：蕴涵：路径敏化哈尔滨理工大学工学硕士学位论文r e s e a r c ho f t h et e s tg e n e r a t i o na l g o r i t h mf o rd i g i t a li n t e g r a t e dc i r c u i ta b s t r a c td i g i t a li n t e g r a t e dc i r c u i ti so n eo ft h eq u i c k e s tt e c h n i q u e si nd e v e l o p m e n t w i t ht h ed e v e l o p m e n to ft h ed e s i g nf o rt h ed i g i t a li n t e g r a t e dc i r c u i t sa n dt h et e c h n i q u eo fc r a f t ，t h es c a l ea n dt h ec o m p l e x i t yo ft h ed i g i t a li n t e g r a t e dc i r c u i t sb e c o m em o r ea n dm o r el a r g e ，a n dt h et e s tg e n e r a t i o nf o rt h ed i g i t a li n t e g r a t e dc i r c u i t si sb e c o m i n gi n c r e a s i n g l yd i f f i c u l t i th a sb e c o m et h eb o r l e n e c kf o rt h ep r o d u c t i o no fi n t e g r a t e dc h i p t h 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 mi si n e f f i c i e n tf o rt h ev l s ic i r c u i t s s ot h er e s e a r c ho f n e wa n de f f e c t i v et e s tg e n e r a t i o na l g o r i t h m sh a sv e r yi m p o r t a n tv a l u ea n dm e a n i n g t h ep r o b l e mo ft e s tg e n e r a t i o nf o rt h ed i g i t a li n t e g r a t e dc i r c u i t si sah a r ds o l v e dp r o b l e mi nm a t h e m a t i c s ，b e c a u s ei ti san p - c o m p l e t e n e s sp r o b l e m ，w h i c hh a sb e e np r o v e d a l t h o u g hm a n yt e s tg e n e r a t i o na l g o r i t h m sh a v eb e e np r o p o s e di nt h el a s tf e wy e a r s t h e r ei sn oo n et h a ti se f f i c i e n tf o ra l lv l s ic i r c u i t s t h ep r o b l e mo ft e s tg e n e r a t i o nf o rt h ed i g i t a li n t e g r a t e dc i r c u i t sh a sb e c o m ea ni m p o r t a n tr e s e a r c hs u b j e c t t h et e s tg e n e r a t i o nf o rt h ed i g i t a li n t e g r a t e dc i r c u i t si ss e l e c t e da sr e s e a r c ht a r g e ti nt h i sp a p e r t h es i n g l es t u c k - a tf a u l tm o d e la n dt h ep a t hd e l a yf a u l tm o d e la r eu s e d i tm a i n l ya i m st oi m p r o v et h ef a u l tc o v e r a g ea n dr e d u c et h et e s tg e n e r a t i o nt i m e t h em a i nc o n t e n t sa r ea sf o l l o w i n g ：1 t h ed e v e l o p m e n ta n dc u r r e n tr e s e a r c hs t a t u so ft h et e s tg e n e r a t i o nf o rt h ed i g i t a li n t e g r a t e dc i r c u i t si si n t r o d u c e di nt h i sp a p e r t h ee x i s t i n gp r o b l e m sa n df u t u r ed i r e c t i o nf o rd e v e l o p m e n ta r ep o i n t e do u t 2 t h et e s tg e n e r a t i o na l g o r i t h mb a s e do nh o p f i e l dn e u r a ln e t w o r k sf o rc o m b i n a t i o n a lc i r c u i t si ss t u d i e d ，t h r e e - v a l u e dn e u r a ln e t w o r k si sa p p l i e di nt h et e s tg e n e r a t i o na n dt h et e s tg e n e r a t i o na l g o r i t h mb a s e do nt h r e e - v a l u e dn e u r a ln e t w o r k sf o rc o m b i n a t i o n a lc i r c u i t si sp r o p o s e di nt h ep a p e r r e p r e s e n t i n gd i g i t a lc i r c u i t sb yt h r e e v a l u e dn e u r a ln e t w o r k sm a yr e d u c er e s e a r c hs p a c ea n da v o i dm a n yw a s t e f u la s s i g n m e n t s s ot h r e e - v a l u e dn e u r a ln e t w o r k s a p p l i c a t i o ni nc o m b i n a t i o n a lt e s ti i l -哈尔滨理工大学工学硕士学位论文g e n e r a t i o nm a yr e d u c et e s tt i m ea n di m p r o v et e s te f f i c i e n c y n l et e s tv e c t o r sf o rf a u l tc a nb e e no b t a i n e db yc o n s t r u c t i n gt h ec o n s t r a i n tn e t w o r ko ft h ec i r c u i t sa n ds o l v i n gt h em i n i m u mo f e n e r g yf u n c t i o no f t h ec o n s t r a i n tn e t w o r k 3 t h et e s tg e n e r a t i o na l g o f i t h r ab a s e do nb o o l e a nd i f f e r e n c ef o rc o m b i n a t i o n a lc i r c u i t si ss t u d i e d c o n s i d e r i n gt h a tt h e r ei sal o to fe x c l u s i v eo rc a l c u l a t i o ni nt h eb o o l e a nd i f f e r e n c e ，as i m p l i f i e dm e t h o dt h a ts o l v e sf i r s to r d e rb o o l e a nd i f f e r e n c ei nt h ec o u r s eo fg e n e r a t i n gt e s tv e c t o r sf o rs i n g l es t u c k - a tf a u l ti nc o m b i n a t i o n a lc i r c u i ti sp r o p o s e d i nt h i sm e t h o d ，t 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 tc a nb eo b t a i n e do n l yb ys o l v i n ga l li d e n t i t ya n de x c l u s i v eo rc a l c u l a t i o ni sn o tn e e d e d t h es i m p l i f i e dm e t h o do fs e c o n do r d e rb o o l e a nd i f f e r e n c ei so b t a i n e db ya n a l y z i n gt h es e c o n do r d e rb o o l e a nd i f f e r e n c e ，a n di tp r o v i d e sc o n v e n i e n c ef o rt h et e s tg e n e r a t i o no f t w of a u l t si nt h ec o m b i n a t i o n a lc i r c u i t 4 t 1 1 et e s tg e n e r a t i o na l g o r i t h mf o rn o n - r o b u s tp a t hd e l a yf a u l ti nc o m b i n a t i o n a lc i r c u i t si ss t u d i e d t h e r ea r em a n yf a u l t si nd i g i t a li n t e g r a t e dc i r c u i t ，o n eo fw h i c hi sd e l a yf a u l t n 他c i r c u i tc a n tw o r kp r o p e r l ya th i g h - s p e e dc l o c k靠e q u e n c yi f t h e r ei sd e l a yf a u l ti nt h ec i r c u i t s oi ti sv e r yi m p o r t a n tt os t u d yt h et e s tg e n e r a t i o nf o rd e l a yf a u l t u n t i lm o w , m a n yd e l a yf a u l tm o d e l sh a v eb e e np r o p o s e db ys c i e n t i s t s ，t h ep a t hd e l a yf a u l tm o d e li so n eo ft h em o s tg e n e r a lm o d e l sm n o n gt h e m h o w e v e lt h ed i s a d v a n t a g ew i t ht h ep a t hd e l a yf a u l tm o d e li st h a tt h en u m b e ro ff a u l t sw i t hr e s p e c tt ot h en u m b e ro fg a t e si nt h ec i r c u i ti se x p o n e n t i a l ，a n dg e n e r a t i n gt e s tv e c t o r sf o rf a u l t si ns h o r tt i m ei sg e n e r a l l yh a r d w jw i l lg e n e r a t et e s tv e c t o r sf o rn o n r o b u s tp a t hd e l a yf a u l tn s m gs t u c k - a tf a u l tt e s tg e n e r a t i o na l g o r i t h mb yu s i n gp a t h l e a ft r a n s f o r m a t i o n t l l i sa l g o r i t h mc a na v o i d “e x p o n e n t i a lp r o b l e m r e d u c et e s tg e n e r a t i o nt i m ea n di m p r o v et e s tg e n e r m i o ne f f i c i e n c y k o y w o r dt e s tg e n e r a t i o na l g o d t h m ：n e u r a ln e t w o r k ；i m p l i c a t i o n ；p a t hs e n s i t i z a t i o ni v 哈尔滨理工大学工学硕士学位论文第1 章绪论数字集成电路是当今发展最快的技术领域之一，随着微电子技术的进步，电路结构日趋复杂，集成度日益提高，由此导致数字集成电路的测试生成日益困难，大型集成电路的故障检测用传统的测试生成算法己不再适用，因此迫切需要寻找计算量合理、故障覆盖率较高的测试生成算法。这也是数字集成电路测试生成算法的研究始终没有停止的原因。集成电路的测试生成问题是数学上公认的难题一n p 完全问题。在过去几年中，国内外的一些学者虽然提出了许多新的测试生成算法，但到目前为止还没有一种算法适用于所有的电路，集成电路的测试生成问题已经严重地影响了微电子技术的发展。随着数字计算机的普及和应用，数字集成电路的应用日益广泛，已经渗透到各个领域，为保证其可靠运行，故障检测是必不可少的。在系统故障检测中，一个关键的问题就是确定施加什么样的激励，可以使故障被激活，能够反映出来，并在输出端被观察出来。对于数字集成电路来说，确定激励的问题，正是数字集成电路的测试生成算法需要研究和解决的问题。它成为数字集成电路设计、生产、应用过程中进行故障检测的难点，同时也是电子测量和故障诊断等领域研究的热点之一。数字集成电路的测试生成算法。1 的研究涉及到微电子、计算机、故障检测等学科领域内的理论和技术，必将为这些学科带来新的研究课题，具有很高的理论意义和实际意义。随着计算机和大规模集成电路的飞速发展，数字集成电路已经应用于各行各业，数字集成电路的测试生成算法的研究不仅具有学术意义，还具有巨大的经济效益和社会效益。1 1 数字集成电路测试生成算法的相关概念1 1 1 基本概念1 故障数字系统的故障是指一个电路或系统的物理缺陷，它可以使这个电路或系统失效，也可能不失效，也就是说，存在一定故障的电路或系统仍有可能完成其固有的逻辑功能。2 原始输入在电路中，不接受电路内部任何信号的线，称为电路的原始哈尔滨理工大学工学硕士学位论文输入。3 原始输出电路中，可以将信号送到电路的外部进行测量的线，称为电路的原始输出。4 输入激励输入激励是在电路的原始输入端所加的输入赋值。对于组合电路的一个原始输入赋值，一般称为一个输入矢量( i n p u tv e c t o r ) 或输入模式( m p u t p a t t e r n ) 。对于时序电路，通常是一组原始输入赋值，一般称为输入序列( i n p u ts e q u e n c e ) 。5 输出响应在一组或多组输入激励作用下，电路输出所取的逻辑状态称为电路对输入激励的输出响应，电路可以是单输出，也可以是多输出。6 测试矢量( t e s tv e c t o r )能检测数字集成电路中某个故障的输入激励矢量，叫做该故障的测试矢量。对于组合电路，一个测试矢量只是原始输入信号的一种赋值组合，也称为测试码( t e s tc o d e ) 或测试模式( t e s tp a t c e m ) 。对于时序电路，一个测试矢量是若干组原始输入信号构成的有序排列，称为测试序列( t e s ts e q u e n c e ) 或测试模式( t e s tp a r e m ) 。7 测试生成( t e s tg e n e r a t i o n )测试生成是产生电路的测试矢量或测试序列的方法或算法。8 测试集( t e s ts e t )若干测试码的集合称为测试集。某个故障的全部测试码的集合称为该故障的完全测试集，简称故障的测试集。被测电路的所有可测故障的完全测试集的集合，称为电路的完全测试集，简称电路的测试集。9 可测故障( d e t e c t a b l ef a u l t )至少可被一个测试矢量或一个测试序列所检测的故障，称为可测故障。1 0 不可测故障( u n d e t e e t a b l ef a u l t )没有任何一个测试矢量或一个测试序列能够检测的故障，称为不可测故障，在国外的文献上，有时也称为冗余故障( r e d u n d a n tf a u l t ) 。1 1 扇出一个元件的输出连接多个元件的输入被称为扇出，该输出线被称为扇出点，由扇出点至其它元件的连线称为扇出分支。如果从同一扇出点出发的两条或多条路径经过若干元件后到达同一个门的两个或多个输入端，称为扇出重汇聚，该门称为汇聚门。1 2 路径敏化路径敏化指的是从故障点到原始输出端选择一条通路，当故障效应从此通路向原始输出端传播时，所经过的门的其它输入端应该赋以特定的值，使得故障效应可以传播到原始输出端。此过程也叫故障敏化。1 3 蕴涵在故障驱赶过程中会确定某些信号线上的值，根据这些确定的值可以唯一确定其它一些信号线的值，这个过程口q 做蕴涵。哈尔滨理工大学工学硕士学位论文1 1 2 故障模型为了研究故障对电路或系统的影响，有必要对故障作一些分类，并构造故障模型，故障模型就是将物理缺陷的影响模型化为逻辑函数的逻辑或时滞等方面的特性。构造故障模型的基本原则有两个：一个是故障模型应能准确地反映某一类故障对电路或系统的影响，即故障模型应具有典型性、准确性和全面性。另一个原则是故障模型应该尽可能简单，以便做各种运算和处理。显然这两个原则是矛盾的，因此往往要采取一些折衷的方案。由于解决的问题和研究的侧重面不同而采用的故障模型也不同，因此在决定使用什么样的故障模型时，首先要考虑所研究对象的重点和所研究电路和系统的实现技术以及所采用的器件，最后还应考虑研究用的设备、软件和其它条件。总而言之，故障模型在故障诊断中起着举足轻重的作用，一个好的故障模型往往能使故障诊断的理论和方法得以发展和完善。下面介绍几种目前常用的故障模型。1 。1 1 2 1 固定型故障( s t u c k - a tf 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 ) ，简记为s a _ 0 。固定型故障模型在实际应用中用得最普遍，因为电路中元件的损坏、连线的开路和相当一部分的短路故障都可以用固定型故障模型比较准确地描述出来，而且由于它的描述比较简单，因此处理起来也比较方便。需要着重指出的是，固定故障s a 一1 和s a 一0 都是相对于故障对电路的逻辑功能而言的，而同具体的物理故障是没有直接关系的。它们是指使信号的逻辑电平停留在逻辑高电平或逻辑低电平的各种物理故障的集合。根据电路中固定型故障的数目，可以把固定型故障分为两大类：如果电路中只存在一个固定型故障，则称之为单固定型故障；如果一个电路中存在两个或两个以上的固定型故障，则称之为多固定型故障。1 1 2 2 桥接故障( b r i d g i n gf a u l t s )电路中的信号线短路连接在一起的故障，称为桥接故障。常见的桥接故障有两种：一是元件输入端之间的桥接故障；二是元件输入端和输出端之间的反馈式桥接故障。一个元件输入端之间的桥接故障一般形成线与关系。一个元件输入端和输出端之间的反馈式桥接故障比较复杂，发生这类故障时有可能把组合电路改变堕玺鎏兰三奎兰三兰堡圭兰垡笙苎成时序电路，甚至使电路发生振荡而趋于不稳定。1 1 2 3 时滞故障( d e l a yf a u l t s ) 时滞故障主要考虑电路中信号的动态故障，即电路中各种元件的时滞变化和脉冲信号的边缘参数的变化等。这类故障主要导致时序配合上的错误，因此在时序电路中影响较大。1 1 2 4 转换故障( t r a n s i t i o nf a u l t s ) 转换故障分为o l 转换( s i o w t o r i s e )和l 一0 转换( r i s e t o s l o w ) 。一个两向量序列( v l ，v 2 ) 为信号线七的0 1 转换故障的测试矢量，仅当v l 将膏置为0 ，且v 2 可检测k o ( 由：s a o ) 故障。类似地，一个两向量序列( v l ，v 2 ) 为信号线膏的l o 转换故障的测试矢量，仅当v 1 将丘置为1 ，且v 2 可检测l ( 膏：s a 一1 ) 故障。1 1 2 5 暂态故障( 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 ! t s ) 。瞬态故障不是由电路或系统中硬件引起的故障，而是由电源的干扰和粒子的辐射等原因造成的，因此这一类故障无法人为予以重复出现。间歇性故障是可重复出现的非固定型故障。产生这类故障的原因有：元件参数的变化、接插件的不可靠、焊点的虚焊和松动以及温度、湿度和机械振动等其它环境原因等。因此有些间歇性故障应该在改善使用条件和制造工艺方面来加以防止。1 2 数字集成电路测试生成算法概述早期人们对集成电路的检测和诊断是靠人工查找故障，随着集成电路规模的增大，器件集成度的迅速提高，人工诊断就逐渐为机器诊断所代替，产生了系统的诊断理论和测试系统。现在人们对电路的测试通常在测试系统所提供的硬件，软件环境下实现的。测试的工作框图如图1 1 所示，测试系统的硬件结构如图1 - - 2 所示。在图1 1 中，计算机主要用于为被测电路生成测试矢量，数字信号发生器根据计算机的要求产生测试波形，并加载到被测电路上，逻辑分析仪采集被测电路的响应信号并进行一定的分析，然后将结果送到计算机中进行处理。如果被测电路在测试矢量的激励下响应正常，则说明被测电路无故障；如果为错误响应，即可由测试算法得出被测电路中故障的性质和位置，并通过输出设备显示或打印测试结果。由图l l 可见，测试矢量是影响测试效果的关键，测试矢量主要是通过测试生成算法得到的。下面分别介绍组合电路测试生成算法的研究现状和时序电路测试生成算法的研究现状。哈尔滨理工大学工学硕士学位论文图1 一l 测试的工作框图f i g 1 - 1t h eb l o c kd i a g r a mo f t e s t图l 一2 测试系统的硬件结构f i g 1 - 2t h eh a r d w a r es t r u c t u r eo f t e s ts y s t e m1 2 1 组合电路测试生成算法的研究现状组合逻辑电路是数字电路测试的研究基础，第一篇关于组合电路的测试方法是1 9 5 9 年e l d r e d 提出的，该方法不能解决两级以上组合电路的故障测试问题，因此是一种比较简单的测试生成算法。1 9 6 6 年d b a r m s t r o n g 根据e l d r e d的基本思想提出了一维通路敏化的方法，其主要思想是对多级门电路寻找一条从故障点到原始输出端的敏化通路，使故障信号在原始输出端可以观察到。1 9 6 8 年s e l l e r s 等人提出了布尔差分法，它通过对数字电路布尔方程式的差分运算来求得测试，能获得测试集的一般表达式，可以求出所给故障的全部测试矢量。由于它将电路描述抽象为数学表达式，从而可进行严密的数学推导，翠蓍哈尔滨理工大学工学硕士学位论文因此有较高的理论价值。在布尔差分法的发展中具有代表性的是主路径法5 1 ，主路径法将通路敏化的概念引入到布尔差分算法中，提高了布尔差分法的效率。近年来发展起来的二元判定图( b d d ) 测试生成方法，也利用了布尔差分法的原理。布尔差分法的不足是：对复杂性较高的电路，特别是对l s i ，v l s i 电路，用它进行测试生成时需要做大量的布尔差分运算，而在计算机上对这些运算的处理是一件困难的工作。布尔差分法的优点是可以求得给定故障的全部测试。d 算法是由r o t h 等人于1 9 6 6 年提出的，它克服了一维通路敏化法的局限，采用多维敏化的思想同时敏化从故障位置到电路的所有输出端的全部通路。它用五个值( 0 ，1 ，x ，d ，d ) 来描述电路中各节点的状态。算法由故障激活、故障驱赶和线相容等步骤组成。只要所考虑的故障可测，用d 算法就一定能求得故障的测试矢量。d 算法是第一个建立在严格理论基础上的组合电路测试生成算法，它具有算法上的完备性，且便于在计算机上实现，是比较成功和目前应用较广的测试生成算法之一。d 算法的不足是：它在进行测试生成时把大量时间花费在对许多不同路径的试探上，因此在组合电路的规模较大时，用该算法计算复杂性大，效率不高，特别是对由大量异或门构成的电路，其运算效率低。1 9 8 1 年g o e l 对d算法进行改进提出了p o d e m ( 面向通路判定) 算法0 1 ，这种算法是一种分支限界的隐式枚举算法，它吸收了穷举法的优点，采用逐个地给原始输入赋值的办法为给定故障生成测试。因此避免了许多盲目的试探，减少了d 算法中回退与判决的次数。大量的实验数据表明，对于误差校正型电路p o d e m 算法比d 算法的测试生成速度快若干倍，就是一般的组合电路也有显著的提高。与d 算法相比，p o d e m 算法显著地减少了回退与判决的次数，但它仍然存在回退的问题。为加速测试生成，f u j i w a r a 等人于1 9 8 3 年提出t f a n 算法”。该算法在减少回退次数，降低每一次的回退时间以及对扇出点都做了细致处理，它的主要特点如下：1 搜索空间由头线( h e a dl i n e s ) 和扇出源两类节点构成。2 在每一步中尽可能多地确定已唯一隐含值的信号值。3 故障值分配给由故障唯一确定或隐含的地方。4 在d 边界中只有一个元件时，选择一条唯一确定的敏化通路。5 反向蕴涵到主导线就停止，主导线的值可以推迟到最后再去确认。6 用多路回退的办法对扇出源进行处理。7 使用s c o a p 作为启发性信息来指导搜索。哈尔滨理工大学工学硕士学位论文f a n 算法的运算速度快于p o d e m 算法，不仅回退次数少，而且故障覆盖率较高。f a n 算法丰富和发展了测试生成算法的基本思想，近年来出现的一些较为有效的方法，立1 k i r k l a n d 等在1 9 8 7 年提出来的t o p s 算法“等，大多数都吸收了它的思想，是它的扩充和发展。在f a n 算法的发展中，有代表性的一种算法是m i c h a e l 等人于1 9 8 7 年提出的s o c r a t e s 算法。这种算法将组合电路的测试生成问题描述成一个对判定树的搜索过程，采用了一些新技术，如改进了f a n 算法的蕴涵过程，使蕴涵更加彻底：用控制的概念解释唯一敏化现象，使算法在故障传播时对更多的情况赋予确定值；扩展了多路回退策略，这包括将基本门扩展到x o r 、n x o r 和高级单元，如加法器等。s o c r a t e s 算法对1 0 个电路的实验结果表明，在回退次数限制在1 0 次以内时，它的故障覆盖率全部为1 0 0 ，并找出了每一电路中全部的冗余故障，因此s o c r a t e s 算法是性能较好的测试生成算法。2 0 0 1 年e g i z d a r s k i 等人提出了基于布尔满足性( b o o l e s ns a t i s f i a b i l i t y ，简称s a t ) 的测试生成算法“，该方法用布尔公式表示电路的逻辑函数，用c n f ( c o n j u c t i v en o r m a lf o r m ) 模型来表示。它的缺点是不能充分利用电路的结构信息，开发有效的测试生成算法。接着e g i z d a r s k i 又提出了基于蕴涵图( i m p l i c a t i o ng r a p h ，简称i g ) 的测试生成算法o “，用蕴涵图作为c n f 模型的补充，可以有效地利用电路的结构信息，弥补s a t 算法的缺点。文献“”“”提出了层次式的测试生成算法，用功能块模型加速测试生成中的传播和确认过程，提高了算法的速度。该算法的缺点是故障覆盖率低，一般不能满足实际要求。文献“”提出了r t l 级的测试生成算法。r t l 级的测试生成算法类似软件测试，它的优点是有v h d l 设计语言提供技术支持，速度快；缺点是需要算法设计人员精通v h d l 设计技术，算法的故障覆盖率不高。我国集成电路产业相对落后，从事组合电路测试生成算法研究的人员也比较少。代表性算法有魏道政提出的主路径敏化算法。和曾芷德提出的g f 二值算法1 。在超大规模集成电路出现之前，组合电路的测试生成算法己相当成熟，随着超大规模集成电路的出现，这些传统的算法已经不再适用，迫切需要研究新的有效的组合电路测试生成算法。1 2 2 时序电路测试生成算法的研究现状时序电路中存储元件的存在使得时序电路的测试生成( a t p g ) 比组合电路的测试生成困难得多。由于组合电路的测试生成不仅在理论上比较成熟，而且哈尔滨理工大学工学硕士学位论文有具体的方法和程序可以使用，因此时序电路的测试生成通常使用时序电路的h o f f m a n 模型把时序电路转换成为组合电路，然后再应用组合电路的测试生成算法对其生成测试矢量。时序电路的h o f f m a n 模型如图1 3 所示。图1 3 时序电路的h o f f m a n 模型f i g 1 - 3t h eh o f f m a nm o d e lo f as e q u e n t i a lc i r c u i t图中c ( 幻是组合电路，它的输入信号来自原始输入信号并( f ) 和存储元件5 的输出信号y ( f ) 。c ( 0 的输出信号有两部分，一部分是送到原始输出端的信号z ( f ) ，另一部分是送到存储元件，的输入信号l r ( 幻。如果在t 时段把电路从s n c ( t ) 的反馈线断开，可以得到一个时段的展开模型，然后按时段把它们的各个展开模型首尾相接，得到一个重复的组合逻辑阵列。这样就把时段分割变成了空间的分割，而每一个分割都是组合电路，因此可以把一个时序电路转换成等效的组合电路。m u t h 提出的九值算法“”是对五值d 算法的改进。在使用重复阵列模型时，由于时段的重复故障效应，一个单故障表现为多故障，五值d 算法没有考虑这种情况，因此表现出极大的弊端。九值算法充分考虑了这种故障的重复效应，能够对时序电路生成有效的测试矢量。九值逻辑的九值是：1 ( 1 1 ) 、0 ( 0 0 ) 、u ( x x ) 、s o ( 0 1 ) 、s ( i o ) 、g o ( 0 x ) 、g 。( 1 x ) 、f o ( x 0 ) 、和只( x 1 ) 。九值d 算法的特点是可以大大减少d 算法中路径选择的次数，提高测试生成效率。e b t 算法“”将反向时间处理( r t p ) 技术应用于时序电路测试生成。选择一条从故障点到原始输出( p o ) 的拓扑路径( t p ) 。t p 从电路输出端向故障点反序运行，测试生成从重复阵列模型的一个单时序单元处开始，所选择的原始输入( p i )和伪原始输入( p p i ) 应该在本时序单元使故障效应沿着t p 向p o 输出。回退的目的是为满足目标线上的需要值而确定p i 值和p p i 值。一个时序单元运行完后，选择所有没有初始化的存储元件，在原时序单元继续进行回退直到完成相关的哈尔滨理工大学工学硕士学位论文初始化。当前的时序单元和原时序单元选择相应的存储元件输入以扩大回退，当原时序单元变成当前时序单元时，由于所有必要的赋值已经赋完，p p i 线的赋值不需要向前进行。这就简化了测试生成算法，提高了效率。c h e n g 提出了b a c k算法”1 ，它是e b t 算法的改进，像e b t 算法一样也使用r t p 技术。然而，与e b t算法不同的是，它不事先选择一条路径，而是事先选择一p o ，封凹或万赋给所选择的输出端，然后反向确认其它值。算法电路执行向后的确认过程，没有d算法的前向传播过程，它需要较少的时间就可生成测试。该算法的缺点是其性能受预先选择的输出影响较大，需要精确的可测度来指导。h i t e c 算法。”是使用前向时间处理( f t p ) 技术和r t p 技术的时序电路a ：r p g 算法。还使用其它一些技术以改进钡4 试生成的运行。它把测试生成分为两个阶段。第一个阶段是f t p阶段，在这个阶段中，故障被激活并被传播到p o 端。第二阶段使用r t p 技术确认由第一阶段决定的初始状态。h i t e c 算法还使用了p o d e m 算法的基于蕴含枚举的判定策略和f a n 算法的优先赋值策略。它也使用了一个快速电路仿真器p r o o f s ，这个仿真器集并存算法、差分算法和并行故障仿真算法的优点于一身。e s s e n t i a l 算法”2 1 是组合电路测试生成算法s o c r a t e s 的扩展，它同时工作在两个时序单元上，即当前时序单元和原时序单元。e s s e n t i a l 使用静态学习将两个时序单元包含在学习进程中，学习从p o 端进行。e s s e n t i a l 算法采用的关键技术主要是：在预处理阶段对电路结构进行综合分析，以了解电路的全局结构和定位反馈回路；在帧间采用r t p 技术，帧内采用f t p 技术；除局部隐含外，尽可能在时帧上和重汇聚的扇出点上进行全局隐含。其测试生成阶段分为三个部分：故障相关信息研究，故障效应传播，对未判决线进行判决。f a s t e s t 1算法是只使用f t p 技术的基于p o d e m 算法的时序电路a t p g 算法。对于一个给定故障，f a s t e s t 估计所有用于检测故障的时序单元的数目，这种估计是基于可控度和可观度的s c o a p 算法。它首先确定激活故障所需要的最小数量的时序单元，然后检查激活的故障是否可以在p o 端观察到。然后建立一个带有估计时序单元数目的重复阵列模型。第一个时序单元的p p i 被置成不确定值或由原生成测试序列所提供的值。最初的目标是在所估计的时序单元激活目标故障，一但初始目标被确定，测试生成以与p o d e m 一样的方式进行，当此算法不能找到测试集时，就增加时序单元的数目，在新的重复阵列中，再一次进行测试生成，直到时序单元达到极限为止。f a s t e s t 算法的主要优点是可以快速地确认不能达到的状态，缺点是需要对时序单元的总数和激活故障的时序单元有较准的估计，如果估计不正确，会大大浪费时间和存储资源。第一个基于仿真的测试生成算法是由s e s h u 和f r e e m a n 提出的。基于仿真的方法使用仿真组合和代价函数指导哈尔滨理工大学工学硕士学位论文测试生成进程。c o n t e s t 算法“4 3 是一种典型的基于仿真的a t p g 算法。它通过改变测试矢量的一个位产生试验矢量，所用的代价函数表明了从过程到生成测试的接近程度。在测试生成的不同阶段使用不同的代价函数。使用并行故障仿真方法，它包括三个阶段：初始化阶段，并行故障测试阶段和单故障钡9 试阶段。它的优点是算法简单，缺点是不能识别冗余故障，故障覆盖率较低。最早把遗传算法成功应用到数字集成电路测试生成上的是1 9 6 6 年由c o m o 提出的g a t t o算法o “，从此引起测试领域内一些学者的注意，并进行了广泛的研究。此类算法使用适应度函数，实质上就是代价函数指导生成测试矢量。对群体中的个体，都计算出对应的适应度，在数字电路测试中，适应度与个体检测到的故障数成正比，检测到的故障越多，表示个体越适应生存环境。适应度为群体进化时的选择提供了依据，有了适应度作为进化依据后。对群体进行选择、交叉、变异等操作。这三种操作保证了遗传算法的全局优化性。c r i s 算法”3 使用基于从故障效应到原始输出距离的两种适应度函数和交换分配原则产生测试，可用于组合和时序电路，针对晶体管级、门级和更高级别的电路进行测试，但不易激活难测故障，因而故障覆盖率较低。g a t e s t 算法0 7 1 也是一种基于g a 的时序电路测试生成算法，它通过一个故障模拟器一p r o o f s 计算出每个待测矢量的适应度，g a 根据得到的适应度从中优选出一个最优的测试矢量，此算法故障覆盖率比c r j s 算法故障覆盖率高，但要激活一个难测故障，并把故障效应从触发器传播到原始输出仍然是个难题。s t a l l i o n 算法。”是一种基于状态转换图( s t g )的a t p g 算法。对于一个给定故障，算法寻找一个激活状态和一个故障传播序列，使用s t g 找到一个状态转换序列将电路带到激活状态。算法的优点是适用于s t g 容易获得的控制型电路。缺点是对于大型的电路，s t g 不容易找到。s t e e d算法。”是对s t a l l i o n 算法的改进，在处理大规模电路时，s t e e d 算法比s t a l l i o n 算法有效，缺点是生成测试序列时间长。h i d e of u j i w a r a 提出了时序电路的路径延迟故障的测试生成算法啪1 。此