（测试计量技术及仪器专业论文）基于遗传优化的三值神经网络测试生成算法.pdf

啥尔滨理工大学工学硕士学位论文 基于遗传优化的三值神经网络测试生成算法 摘要 数字集成电路是当今发展最快的技术领域之一。随着数字电路设计及 工艺技术的发展，电路的规模和复杂度日益增大，使得电路的测试生成日益 困难。对于复杂的大规模集成电路，传统的测试生成算法已不再适用，因此 研究新型有效的数字集成电路测试生成算法具有十分重要的理论价值和实际 意义。 集成电路的测试生成问题是数学上公认的难题- n p 完全问题，在过去的 几年中，国内外的学者虽然提出了许多新的测试生成算法，但是到目前为止 还没有一种算法能适合所有的大规模集成电路，集成电路的测试生成问题已 成为一个重要的研究课题 本文采用固定故障模型和三值神经网络模型，对数字集成电路的测试生 成进行研究，为提高故障覆盖率，减小测试生成时间，重点研究了以下内 容： 1 在深入研究二值神经网络测试生成算法基础上，将遗传算法引入到 组合电路的测试生成算法中基于遗传算法是一种全新的寻优方法，本文采 用遗传算法求解约束网络对应能量函数的最小值点在遗传算法中，适应度 函数是影响算法性能的一个主要因素，它主要影响问题的求解空间，本文在 比较其他适应度函数的基础上，提出本文的适应度函数，利用本文的适应度 函数，在基准电路上得到测试矢量。同时，交叉、变异概率是影响收敛速度 的一个重要的指标，本文将提出一个合理的交叉和变异的概率。 2 在二值基础上，建立基本逻辑门电路的三值神经网络模型和组合电 路的三值神经网络模型用三值神经网络表示数字电路，可以减小搜索空 间，避免很多不必要的赋值，因此可以在保证具有较高故障覆盖率的情况 下，减小测试生成时间。在三值神经网络模型中，二值模型的能量函数不能 适用于三值模型，因此需要求解三值模型的能量函数，在此本文对三值神经 网络测试生成算法与二值神经网络测试生成算法进行比较 3 研究遗传算法的软件实现方法。在软件构建的标准电路基础上，用 适当的编程方法实现遗传操作，可以有效的缩短程序的执行时间。在仿真过 程中，根据程序运行状况，优化程序结构，调整遗传操作参数，以提高算法 哈尔滨理工大学工学硒士学位论文 的测试速度。 关键词测试生成算法；三值神经网络；遗传算法 兰玺鎏圣三查耋三茎堡老耋竺丝三 r e s e a r c ho ft e s tg e n e r a t i o na l g o r i t h mo f t h r e e v a l u e dn e u r a ln e t w o r k sb a s e d o nt h eg e n e t i c a l g o r i t h m a b s t r a c t d 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 em o s tr a p i dd e v e l o p i n gt e c h n i q u e s 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 e t 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 s b 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 d c 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 t t l e n e c ko ft h e p r o d u c t i o no fi n t e g r a t e dc h i p 1 1 圮i x 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 s i n e 伍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 fn e wa n de f f e c t i v et e s t g e n e r a t i o na l g o r i t h m sh a sv e r y i 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 d s 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 n p r o p o s e di nt h el a s tf e wy e a r s t h e r ei s n oo n et h a ti se f f i c i e n tf o ra uv l s i c i r c u i t s n 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 s b e c o m ea l li 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 h t a r g e ti nt h i sd i s s e r t a t i o n t h es t o c k - a tf a u l tm o d e la n dt h et h r e e v a l u e dn e u r a l n e t w o r k sm 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 d r 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 a f t e rt h o r o u g hs t u d yf o rt h et e s tg e n e r a t i o na l g o r i t h mo ft w o v a l u e d n e u r a ln e t w o r k s ，g e n e t i ca l g o r i t h mi sa p p l i e di nt h et e s tg e n e r a t i o na l g o r i t h mf o r c o m b i n a t i o n a lc i r c u i t s b a s e do nt h a tg e n e t i c a l g o r i t h m i sab r a n dn e w o p t i m i z i n gm e t h o d ，t h i sd i s s e r t a t i o na d o p t sg e n e t i ca l g o r i t h m t of i n dt h e m i n i m u mp o i n to ft h ec o r r e s p o n d i n ge n e r g yf u n c t i o nf o rt h ec o n s t r a i n tn e t w o r k i ng e n e t i ca l g o r i t h m ，f i t n e s sf u n c t i o ni sam a i nt e c h n o l o g yt oa f f e c tt h e p e r f o r m a n c eo ft h ea l g o r i t h m i ta f f e c t sm a i n l yt h es o l u t i o ns p a c eo fo n ep r o b l e m 1 1 1 - 哈尔滨理工大学工学硕士学位论文 b a s e do nt h ec o m p a r i s o nw i t ho t h e rf i t n e s sf u n c t i o n s ，t h ef i t n e s sf u n c t i o no ft h i s p a p e ri sp r o p o s e d w i t ht h ef i t n e s sf u n c t i o no ft h i sp a p e r ，t e s tv e c t o r sc a l lb eg o t o nt h er e f e r e n c ec i r c u i t s a tt h es a m et i m e ，i n t e r s e c t i o no rv a r i a t i o n t h e p r o b a b i l i t yi s a ni m p o r t a n tp a r a m e t e rt oa f f e c tt h ec o n v e r g e n ts p e e d a n dt h i s p a p e rw i l lp r o p o s ear a t i o n a lp r o b a b i l i t yf u rt h ei n t e r s e c t i o na n dv a r i a t i o n 2 b yt h et e s tg e n e r a t i o na l g o r i t h mo ft w o - v a l u e dn e u r a ln e t w o r k s ，t h r e e v a l u e dn e u r a ln e t w o r k sm o d e l sa r es e tu pf o rb a s i cl o g i cg a t ec i r c u i t sa n d c o m b i n a t i o n a lc i r c u i t sr e s p e c t i v e l y d i g i t a lc i r c u i tc a nb ee x p r e s s e dw i t ht h r e e v a l u e dn e u r a ln e t w o r k s ，w h i c hc a nr e d u c et h es e a r c hs p a c ea n da v o i d sm a n y u n n e c e s s a r ya s s i g n m e n t s ot h a ti tc a nr e d u c et h et e s tg e n e r a t i o nt i m ei ns e c u r i t y f o rh a v i n gh i g h e rf a u l tc o v e r a g e i nt h r e e - v a l u e dn e u r a ln e t w o r k sm o d e l ，t h e e n e r g yf u n c t i o no ft w o - v a l u e dn e u r a ln e t w o r k sm o d e lc a l ln o tb ea p p l i e d ，s ot h e e n e r g yf u n c t i o nn e e dt ob ef i n df o rt h et h r e e - v a l u e dn e u r a ln e t w o r k sm o d e l ，a n d h e r et w ok i n dm o d e la l g o r i t h m sa r ec o m p a r e di nt h i sp a p e r 3 s o f t w a r er e a l i z a t i o nm e t h o do fg e n e t i ca l g o r i t h mi ss t u d i e di n t h i s d i s s e r t a t i o n b a s e do nb e n c h m a r kc i r c u i t sc o n s t r u c t e db ys o f t w a r e ，g e n e t i c o p e r a t i o n sa r ea c t u a l i z e dw i t ha p p r o p r i a t ep r o g r a m m i n gm e t h o d ，c a ne f f e c t i v e l y a b b r e v i a t et h et i m e o ft h ep r o g r a m e x e c u t i v e d u r i n gs i m u l a t i o n p r o c e s s ， p r o g r a ma r c h i t e c t u r ec a l lb es t r e a m l i n e g e n e t i co p e r a t i o np a r a m e t e r sc a nb e a d j u s t e da n dg e n e t i co p e r a t i o nm e t h o di sc h a n g e dt oi m p r o v et h et e s ts p e e do f a l g o r i t h mb a s e d o nt h ep r o g r a mr u n i n gs i t u a t i o n k e y w o r d s t e s tg e n e r a t i o na l g o r i t h m ：t h r e e v a l u e dn e u r a ln e t w o r k ；g e n e t i c a l g o r i t h m 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于遗传优化的三值神经网 络测试生成算法，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间 独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含 他人已发表或撰写过的研究成果对本文研究工作做出贡献的个人和集体，均 已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：王磁 日期：爿年罗月小 哈尔滨理工大学硕士学位论文使用授权书 基于遗传优化的三值神经网络测试生成算法系本人在哈尔滨理工大学攻 读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔 滨理工大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了 解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部 门提交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可 以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密厂 ，在年解密后适用授权书。 i _ j 不保密冈 ( 请在以上相应方框内打) 作者签名： 王。砖 新躲颞竿 日期：2 1 年弓月f 只 日期：0 7 年；月形日 哈尔滨理工大学工学硕士学位论文 1 1 研究背景及意义 第1 章绪论 数字集成电路是当今发展最快的技术领域之一，随着集成电路的集成度 和复杂性有了大幅度的提高，而引脚数却有一定的限制，许多电路被封装在 芯片内部，外部可达到的测试点、原始输入、原始输出所占的比例越来越 少，导致了数字集成电路的测试日益困难【l l 。 集成电路的测试生成问题是数学上公认的难题- n p 完全问题。在过去几 年中，国内外的一些学者虽然提出了许多新的测试生成算法，但到目前为止 还没有一种算法适用于所有的电路，因此集成电路测试研究的重点主要集中 于研究新的有效的测试生成算法和电路可测性设计( d f t ) 技术。在系统故障 检测中，一个关键的问题就是确定施加什么样的激励，可以使故障被激活， 能够反映出来，并在输出端被观察出来。对于数字集成电路来说，确定激励 的问题，正是数字集成电路的测试生成算法需要研究和解决的问题【2 】。它成 为数字集成电路设计、生产、应用过程中进行故障检测的难点，同时也是电 子测量和故障诊断等领域研究的热点之一 神经网络已应用到许多领域，在优化、故障诊断、模式识别、参数提取 和人工智能等许多问题上，都取得了很好的效果。尽管目前人们对大脑的神 经网络结构和运行机制的工作原理的了解还很肤浅，但是基于生物神经系统 的分布式存储、并行处理、自适应学习这些现象，已经构造出有一定初级智 能的人工神经网络【3 j 。从8 0 年代初神经网络的研究再次复苏并形成热点以 来，发展非常迅速，从理论上对它的计算能力、对任意连续映射的逼近能 力、学习理论以及动态网络的稳定性分析上都取得了丰硕的成果。鉴于 h o p f i e l d 神经网络模型在解决n p 完全问题方面的成功应用，国内外的一些 学者提出了基于h o p f i e l d 神经网络模型的组合电路测试生成方法，将测试 生成问题数学化，并作为一个优化问题来解决。 虽然人工神经网络的应用日益广泛，但是仅仅依靠神经网络的自身构成 的各种算法往往未能显示其突出的优点。而将人工神经网络与其它计算智能 算法相互结合有可能产生很好的应用效果。人工神经网络的主要应用领域之 一是求解优化问题，而遗传算法也是一种求解优化的有效方法。遗传算法最 哈尔滨理t 人学丁学琐j 。学位论之 主要的特点是利用适应度提供的信息进行搜索，小需要其他的辅助信息，遗 传算子都是随机操作不需要确定规则控制i ”遗传算法将适肯生存原| j ! i l 与 随机信息，逆换结合起来，i j i 者力图消除解中的小适应性冈素，后行继承了原 有解中已有的知识，从而有力地加快算法的搜索过程。将遗传算法和神绛l 藕 络结合起来引进到测试乍成算法中，将有力的促进测试生成算法的发腱。 1 2 组合电路测试生成算法的研究现状 组合逻辑l 【i 路是数字电路测试的研究基础，第篇关j ：组合r u 跻的测试 方法是1 9 5 9 | e 1 d r c d 提：n 的，i 发方法只能解决两级以内组合r 乜蹦的收障测试 方法，因此是一种比较简单的测试生成算法。1 9 6 6 年d b a r m s t r o n g 根抛 e l d r e d 的基奉心想提山了一维通路敏化法，该厅法足对多级fj i u 路哥找一条 从放障点到原始输出端的敏化通路，使原始输出端可以) c ! i l 察到放障偷0 当 时人们以为放障指要沿菜条通路就可以传输到原始输端，1 9 7 6 年。 s c h n e i d e r 提山j ，一个反例，证明某些敞障信弓必须同时沿两条以i | 的通路 传输j 。能存原始输出端测造到故障信号i s l 。 d 算法足山r o l h 等人一j ：1 9 6 6 年提出的，它克服了维通路域化法的局 龈，采用多维敏化的思想同时敏化从故障位置到也路的所有输出端的全部通 路m 它用“个位( o ，1 ，x ，d ，d ) 来描述电路中备节点的状态算法山放障激 活、故障驱赶带l 线桐容等步骤组成。只要所考比的敞障可测，用d 算泓、就一 定能求得敞障的测试久星d 算法足第一个建帝在格艘沧肚f i j | ：i - f f l 组合电 路测试生成箨法，它h 仃算法j 二的究备性，且便丁在汁并机上实现，足比较 成功和日莳应用较广的测试生成算法之一d 算法的不足足：它存进行测试 生成时把大量时i 丌j 花赞在对许多不同路径的试探匕，因此在编合也跺的舰模 较大时，用该算法计算复杂性大，效率不高，特 ；l j 是对“j 大缎芹或门构成的 电路，其运算效率低。1 9 8 1 年g o e l 对d 算法进行改进提! f 1 了p o d e m ( 而向通 路判定) 算法，这种算法是一种分支限界的隐式枚举算法，它吸收了穷举法 的优点，采用逐个地给原始输入赋值的办法为给定故障乍成测试。因此避免 了许多卣目的试探，减少了d 算法中回退与判决的次数。大量的实验数扼表 明，对于误差校正型电路p o d e m 算法比d 算法的测试生成速度快符干倍， 就是一般的组合电路也有显著的提高。 1 9 6 8 年s e l l e r s 等人提出了布尔差分法，它通过对数字电路布尔方程式 的差分运算束求得铡试，能获得测试集的一般表达式，可以求；h 所给故障 哈尔滨理t 人学t 掌硕卜学位论文 的全部测试矢量。由。邑将ll l 路描述抽象为数学表达式，从而川进行严密 的数学推导，因此有较高的理论价值。在布尔羞分法的发展1 1 具有代表性 的是主路径法，t 路径法将通路敏化的概念引入到钳尔差分算法中，提岛 了佰尔差分法的效率。近年束发展起来的二元削定图( b d d ) 测试，上成方法， 也利用了伽尔等分法的原理。 布尔差分法的不足是：对复杂性较高的电路，特别是埘l s i ，v l s i l l i 路，用它进ij ：测试乍成| f f 需做大带的布尔羊分运算，i 斫存计何机卜对这拙 运算的处理足一件困难f 向上作。 布尔差分法的优点是u j 以求得给定故障的伞部测试。 p o d e m 算法显著地减少了回退与判决的次数，但它仍然存征阴退的问 题。为加速测试q 三成，f u j i w a r a 等人于1 9 8 3 年提出了f a n 算法i ”恢并法住 减少驯退次数。降低每次的p l j 迭时u j 以及划扇出点都做了细致处理，它的 主要特点如f ： 1 搜索个f u j 头线( h e a dl i n e s ) 和扇m 源两类节点构成。 2 ：在每步一i 赆可能多地确定已唯一隐岔值的信号值。 3 故障值分配给出故障唯一确定或隐含的地方。 4 在d 边蚪i 一只有一个元件时，选择一条唯一确定的敏化通路。 5 反向蕴涌到主导线就停止，主导线的值可以推迟到晟后再去确认。 6 用多蹄问退的办法对扇 源进行处理。 7 使| j s c o a p 作为启发性信息来指导搜索。 f a n 算法的运算速度快于p o d e m 算法，不仪| _ u 1 退次数少，i f u 设障粳 盖牢较商。f a n 算法f 富和发展了测试生成算法的一谩本思想近 f 宋出现的 一些较为仃放的方法，如k i r k l a n d 等在1 9 8 7 年提出来的t o p s 钎法等，大多数 部吸收了它的思想，是它的扩充和发展一i 在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 算法的蕴涵过程，使蕴 涵更加彻底；用 牢制的概念解释唯一敏化现象，使算法在故障传播时对更多 的情况赋予确定值：扩展了多路回退策略，这包括将基本门扩展至t j x o r 、 n x o r 和高级单元，如加法器等。s o c r a t e s 算法对l o 个电路的实验结果表 明，在回退次数限制在1 0 次以内时，它的故障覆盖率全部为1 0 0 ，并找出 了每一电路中全部的冗余故障，因此s o c r a t e s 算法是性能较好的测试生成 算法。 啥尔滨理工大学工学硕士学位论文 2 0 0 1 年e o i z d a r s l d 等人提出了基于布尔满足性( b o o l e a 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 n 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 ) 的测试生成算法，用蕴涵图作为c n f 模型的补 充，可以有效地利用电路的结构信息，弥补s a t 算法的缺点m 】。 文献【1 l 】提出了层次式的测试生成算法，用功能块模型加速测试生成中 的传播和确认过程，提高了算法的速度该算法的缺点是故障覆盖率低，一 般不能满足实际要求文献【1 2 】提出了r t l 级的测试生成算法。r t l 级的测 试生成算法类似软件测试，它的优点是有v h d l 设计语言提供技术支持，速 度快；缺点是需要算法设计人员精通v h d l 设计技术，算法的故障覆盖率不 高 我国集成电路产业相对落后，从事组合电路测试生成算法研究的人员 也比较少代表性算法有魏道政提出的主路径敏化算法和曾芷德提出的g f 二值算法l ”i 。 在超大规模集成电路出现之前，组合电路的测试生成算法已相当成熟， 随着超大规模集成电路的出现，这些传统的算法已经不再适用，追切需要研 究新的有效的组合电路测试生成算法。 神经网络模型是新兴的技术，它在模式识别与图像处理，控制及优化、 预测与管理等方面的应用非常的广泛。鉴于其在求解n p 完全问题的成功运 用，将其引进到测试生成算法中，加快了测试生成算法的发展。 人工神经网络的研究从2 0 世纪6 0 年代末就开始研究，2 0 世纪8 0 年代开始 蓬勃发展。其中j j h o p f i e l d 的两篇经典论文提出了h o p f i e l d 神经网络的概 念，他和d t a n k 将其用于优化问题时取得了令人瞩目的成果1i t s l 。h o p f i e l d 神经网络的基础构架实施网络中每一个神经元的输出在乘以某些权值后送到 其他所有神经元的输入端，从而形成一种全反馈结构，此外，每个神经元还 各自接收一个外部输入 针对组合电路的测试生成，采用神经网络进行了建模平台的研究与实现 ( 1 6 l 。对基于神经网络的组合电路进行了研究，将组合电路的测试矢量对应 于神经网络，计算能量函数的最小值点，从而将测试矢量的生成问题转化成 数学问题，通过相应的优化算法便可求得测试矢量1 1 7 l 。为解决组合电路的 测试生成问题提供了新的途径，引起了众多学者的广泛兴趣 基于混沌神经网络的自动测试生成算法采用具有衰减步长的混沌模拟退 哈尔滨理工大学工学硕士学位论文 火算法来找到能量函数的最小值点，实现了组合电路的自动测试生成l 。 基于混沌搜索的组合电路测试生成算法将混沌搜索与h o p f i e l d 网络的梯 度算法相结合，利用混沌搜索的内随机性即遍历性来克服梯度算法容易限于 局部极小的缺点，形成一种具有全局搜索能力的测试生成算法i 。 2 0 世纪后期，利用进化算法的优化方法引起人们的巨大兴趣，应用臼益 广泛。它的原理是根据自然界的生物进化理论，通过模拟生物的遗传过程在 代与代传递最优解信息，完成搜索任务。这类方法可进一步划分为遗传算法 ( g a ) 、进化策略( e s ) 、进化规则( e p ) 等三种方法i “。它们共同的特点是可以 对优化问题进行全局搜索，算法性能具有很好的鲁棒性，算法具有灵活性。 从2 0 世纪6 0 年代，美国密歇根大学的j h o l l a n d 教授对这种模仿自然进化 系统而设计人工优化系统的方法进行了广泛深入地研究。1 9 7 5 年他的专著 0 容 0l o 0 状 l oo o llo o 态 f 定义2 2 户i 。b 。f r 和p j 。蛔是与神经元i 和网络的相容状态有关的三 个点集。如果一个点只有一个相容状态。且神经元f 的状态值为l ，则该点 属于p i 。如果一个点只有一个相容状态，且神经元f 的状态值为0 ，则该 点属于p i 。f f 。p i 咖是由除去只。和，io f r 中的点，与网络的相容状态对应 的点组成。 定义2 3 把7 ：和t 作为常数，+ 巧匕= o 是神经元j 在一l 维空间 - i i 柚 的一个超平面，如果点集p j 。和p io f f 中的点分别位于这个超平面的两侧， 而p io t h e r 中的点位于超平面上，则称这个超平面为神经元f 的决定超平面。 定理2 1 对一个端电路，存在一个由个神经元组成的h o p f i e l d 神 经网络与它对应的必要条件是：这个神经元中的每一个神经元都存在一 喻尔茯理丁大学工学预卜学位论史 个决定超平叫。 根据定义2 3 和定理2 1 ，对于基本门电路把p 。和只n 玎q 1 的点分别 入它所对心的h o p f i e l d 神经网络的超平面中，则这炳个点集i i 的点使超 平向的值的符号j 1 f 反，尸i 。h c f 中的点使超平而的倩为0 。冉根捌基本门屯路 中的相容状念使它所刘应的能量函数为0 ，非们容状念使l z 所对应的能量函 数大丁0 ，这样便可得到参数7 = f 1 和，= 【，f 1 ，从而得剑能基函数。下丽以 幽2 1 为例蜕l i j j 水解神经网络模型参数的方法。 首先婴得刊各神经元相关的点集。根掘表2 1 给出的 容状念- q 。分别得 到k ，、以f l g 点集名，珞和只。j c r 为： ，= ( = o ，= 1 ) ) 以一m = ( = 0 ，嵋= o ) ，- 加= ( = 1 ，吒= 1 ) b ，= “_ = o ，= 1 ) ，：一。“= ( k = 0 ，= o j b - = ( k = l ，= 1 ) ) b 。= ( k = 0 ，吒= 1 ) ，( k = l ，= 0 ) ，( k = l ，= 1 ) 只一。= ( k = o ，= o ) ，：。k = f 空) 根据定义2 3 将以七9 个点分b u 代入到，+ l 矿，中，使j _ i ：i ，乙大f 爱 零。点小j i 零点k 等f 零，月：将或f - i f i 94 种耳h 容状态代入到，( 2 2 ) 中，通过计算可以得到式( 2 3 ) 式( 2 3 ) 的解有多个，令彳，b 为大于零的常数，可得式( 2 3 ) 的解为 瓦2 = 口-正j = 一( 彳+ 口) ，瓦l = 曰，e 3 = - ( a + 口) 五i = - ( a + 口) ， 五2 = 一( 彳+ b ) ，i = f ，2 = 爿，1 3 = b 同理可求得与非门，或门，或非门，非门等基本门 i = l 路对应的神经网络 模型。它们的模型参数见表2 ，2 。 对于两输入同或门和异或门。由于它们不满足定理2 1 中关于端电路 存在一个由个神经元构成的神经网络的必要条件，因此它们的神经网络 堕玺堡矍二尘茎三耋堡! ：耋竺篁兰 模型中含有4 个自9 经元，其模型参数如表2 - 3 。 瓦3 + 1 i 0 + ，2 0 五2 + ，3 0 五2 + j 2 + ，j = 0 五l + ，l + i j = 0 瓦2 + 瓦3 + 瓦，+ ，i + ，2 + ，= 0 k = 0 袭2 - 2 筚本r l 电路的i i o p f i e l d 神经网络模础参数 t a b 2 - 2t h en e u r a ln e t w o r km o d e lp a r a m e t e r so f s e v e r a lb a s i cg a t e s rj i b 路输入输j | 权矩阵阑值k o一8彳+ 口o 与rj n ，nn 一8oa + 80 o 彳+ 口一+ 占o2 彳一丹 0口一( + 口l 一 或rj n ，n j，0 一彳+ 口) 0 一( 彳+ 研一( 一+ 口) 0 口 -。 _ 0一占一+ 口 爿+ 8 非rjnn 一b o + 8彳+ 口 别+ 口 爿+ 口+ 口02 爿+ 口 - 。0 一口 一( j + 口y 口 与1 f f j n 魄n 一口0 一“+ b ) 占 b 一( 一+ 占) 一( 彳+ 口) 0 冉 - o一2 1 彳 或1 f 】n 圪吒 【一2 a 6j爿 _ 竺尘堡矍三銮茎：耋堡! 兰丝堡兰 捉2 - 3 异或fj 和同或fj 对应的h o p f i e l d 神经网络模喇参数 t a b 2 - 3t h en e u r a ln e t w o r km o d e lp a r a m e t e r so f x o ra n dx n o rg a t e s f 川! 路输入输山权矩阵 i 瞳i 值k 0砧r 冉b 忙i - b 0j c 舢吕k | f 。0 。 0畀或rji ，i 吩嵋 【一2 , 4 ， r0 盯l “吕k 舢自c c 矿l -_ 0一ba + b4 + 占 同或fj p 1 n 一口o彳+ 口彳+ 占 2 f + 厅 i + 口爿+ b0 2 彳+ 口 丛本i jr 乜路的神经网络模型参数确定之肝，代入式( 2 2 ) 能展雨数表达 式一_ p ，并墩a = 疗= 2 ，c = 1 ，从而得剑儿个摹本门叱j ! 的能锗函数，见农 2 4 。 衷2 - 4 儿个基本rj i u 路们能地蛹散 + i a b 2 - 4 f h ee n e r g yf u n c t i o no fs e v e r a lb a s i cg a t e s fj i u 路输入输出 能蟥函数 与f 】n ，n 巧 4 匕( k + ) + 2 以+ 6 或rjn ，吩n 一4 ( _ + y 2 ) + 2 k + 2 + 2 + 2 以 j“ 圪 4 一2 2 + 2 与舻jn t 坞n 4 ( + ) + 2 u 匕一4 一4 一6 + 6 或l r fjn nn 4 匕( _ + ) + 2 _ 一2 一2 一2 以 2 1 3 组合电路的h o p f i e l d 神经网络模型 对一组合电路c ，利用构成它的基本门的神经网络模型，能获得一种与 电路c 对应的h o p f i e l d 神经网络。方法是把具有十日同杯号的神经元合并成 一个神经元合并时将神经元的闽值相加，相同标号的神经元之n u 的连接权 值也相加。例如对如图2 2 所示组合电路，分别得到与门和或门对麻的 h o p f i e l d 神经网络模型如图2 - 3 中a ) b ) ，c ) 所示，再按照【：述方法便可 得到组合电路对应的h o p f i e l d 神经网络模型，如图2 - 4 中所示由这种构造 方法可知，一个组合电路对应神经网络的能量函数足电路中各个基本门的能 哈尔滨理丁人学t 学坝1 学位论文 量函数之和，i 呵且只有各个基本门的能量函数值均为零时，电路对应网络的 能量函数彳+ 取零。 匕 图2 - 2 细台电路 f i g 2 2c o m b i n a t i o n a lc i r c u i t 山基本逻辑门的h o p f l e l d 神经网络模型，获得表迭仃一升l 合电路的 h o p f i c l d 神经网络模型，这种神经网络模型不仅易于伽i i 算机i ：对其进行操 作，而r 【是神经网络方法实现组合电路测试生成的基础。 吲2 - 3l 警i2 - 2i u 路i i l 备逻车蚌f j 的h o p f i e l d ：值种经网络梭锂 f i g 2 - 3t w o v a l u e dn e u r a ln e t w o r km o d e lt oc o r r e s p o n dw i t ht h el o g i cg a l e si nf i g 2 2 糊2 - 4图2 - 2 电路的h o p f i e l d 神经网络模州 f i g 2 4t h eh o p f i e l dn e u r a ln e t w o r kc i r c u i to ff i g 2 - 2 哈尔滨理工大学工学硕士学位论文 2 1 4 组合电路测试生成的神经网络模型 通过对组合电路神经网络模型的构造方法得知，任一组合电路都存在与 之相对应的h o p f i e l d 神经网络，网络的能量函数为构成它的各基本门的能 量函数之和，而且电路的逻辑特性可以由神经网络的能量函数e 来描述。 电路的相容状态就是一组使e 为零的神经元激活值。在一定条件下，这个 相容状态中所有主输入神经元的激活值就可以成为电路中一个给定故障的测 试矢量。 电路中的某一个节点有故障，如果存在电路的一组输入使电路的输出在 无故障时与有故障时相异，则这组输入就为该故障的一个测试矢量。约束网 络就是当测试矢量输入到该网络时故障电路的输出与无故障电路的输出相 异。用h o p f i e l d 神经网络进行测试时需要构建电路的约束网络。约束网络 由故障电路( 已注入故障) 、无故障电路和一个接1 3 电路组成。对单输出电 路，接口由一个非门构成，如图2 5 所示。 输出接口 图2 5 单输出电路的约束网络 f i g 2 5c o n s t r a i n tn e t w o r kf o ras i n g l e o u t p u tc i r c u i t 对卅个输出端的电路，接口由m 个二输入的异或门和一个或门构成， 并且或门的输出为1 ，如图2 - 6 所示。 输出接口 图2 - 6 多输出电路的约束网络 f i g 2 - 6c o n s t r a i n tn e t w o r kf o ram u l t i - o u t p u tc i r c u i t 1 4 - 哈尔滨理t 人学t 学坝i 学位论_ ! ：【： 2 2 基于三值神经网络的组合电路测试生成算法 2 2 1 三值神经网络模型 1 9 9 0f f ，卜1 本学嚣f u j i w a r a 对神经网络模型进 j 了l 叟进，提出了二二位 神经网络模性，哪川0 ，1 、1 ，2 柬表示神经元n 勺激活值，姨l ，1 ，2 为f r 意 值，f ! | 】可以足0 ，也呵以是1 。如l 斟2 - 7 所示的与fj ，嘤f 止o j fj 的愉值为 0 ，加墩r ：j 1 1o 戏1 & 示，邢么我们就必须从( 0 0 ) ，( 0 1 ) ，( 1 0 ) i f i 选个作为 j 门的输入，似如粜我们使j 1 j0 ，1 ，l ，2 表示的话，我们就i u 以从( o i 2 ) ， ( i 2 、o ) 中选。个作为与j 的输入，减小了搜，索窄j ”5 i 。 品一田。 l 鳘i2 7 输入与i i f i g 2 - 7t w o i n p u ta n dg a t e i 值神经l 叫络f j 能请函数见式( 2 4 ) ： f = 一1 峻互巧仍一，k 一泓巧( 1 一) k ( i - ) + k ( 2 - 4 ) ，i ，一l瞄i b l = 1 j c ，| 址 i i i 经叫络- i 呻f i 绛元的数口楚 l i i 经冗，与之m 的权值 址种纾元，的状怠值，址利l 经元f | q i q 邴参数彬，惩“1i ，n 耶硅i 2 州 ，jj 之f i l j 的校位，k 址常壁。神经元状态值i l j 以取0 、l ，1 1 2 ，我们假定 t h = t w t i = w ”r | ；= w 。i = 0 。 2 2 2 基本逻辑门电路的三值神经网络模型 与：值州i 经旧络模 牲十d