月. 煤矿机械.pdf

第 2 9 卷第 1 期 ．2 O O 8年 1 月 煤矿机械 Co a l Mi n e Ma c h i n e r y Vo 】 ． 2 9 No ． 1 J a n．20 08 基于三值神经网络的数字电路多故障测试生成算法 韩之刚。高兰芝，宫海艳，常大徽 北华大学 电气信息工程学院，吉林 吉林 1 3 2 0 2 1 摘要 针对数字电路 中多故障测试生成较难的问题 ， 提 出了基于三值神 经网络的数字电路 多故障测试生成算法。该算法先把 多故障转换成为单故障， 再用三值神 经网络的方法对单故障电 路构造故障的约束网络， 最后 用遗传算法求解故障约束网络能量 函数的最小值 点获得原 电路 中多 故障的测试矢量。在一些国际标准电路上的实验结果表明本算法的可行性。 关键词 神经网络 ；遗传算法；约束网络；能量函数 中图分类号 T P 1 8 3 文献标志码A 文章编号 1 0 0 3 0 7 9 4 { 2 0 0 8 0 1 0 2 0 5 0 4 M u l tip l e F a ult Te s t i n g Ge n e r a tio n Al g o r i t h m Ba s e d Th r e e v a l u e d Ne u r a l Ne t wo r k s f o r Di g i t a l Ci r c u i t s HAN Z h i g a n g，GAO L a nz l fi，GONG Ha i y a n，CHANG Dah u i E l e c t r i c a l a n d I n f o r m a t i o n E n g i n e e r i n g C o l l e g e ，B e i h u a U n i v e r s i t y ， J i l i n 1 3 2 0 2 1 ， C h i n a Ab s t r a c t A mu l t i pl e f a u l t s t e s t i n g g e n e r a t i o n a l g o r i t h m b a s e d t h r e e - v a l u e d n e u r a l n e t wo r k s f o r d i g i t a l c i r c u i t s i s p r o p o s ed b e c a u s e t h e t est i n g g e n e r a t i o n fo r m u l t i p l e f a u l ts i n d i git a l c i r c u i t s i s m o r e d i f fi c u l t ． T h i s al g o ri t h m c h a n g e mult i p l e f a ults i n t o s i n g l e f a ult fir s tl y an d c o n s t r u c ts the c o n s t r a i n t n e t wo r k o f the f a u l t for the s i n g l e f a u l t c i r c u i t w i th m e th o d o f t h r e e v al u e d n e u r a l n e two r k s ． The t e s ti n g v e c t o r s fo r m ul t i p l e f a u l t s i n the o r i gi n al c i rcu i t C an b e o b t a i n e d b y s o l v i n g the mi n i mu m o f e n e r g y f u n c t i o n o f the c o n s t r a i n t n e t wo r k for the f a ult with g e n e ti c alg o r i t h m ．Th e e x p e r i me n t a l r e s ults o n s o me i n t e ma t i o n al s t an d a r d c i rcu i t s d e mo n s t r a t e the f e a s i b i l i t y o f the alg o r i t h m ． Ke y wo r d s n e u r a l n e two r k s ；g e n e t i c a l g o r i t h m；c o n s t r a i n t n e tw o rk ；e n e r g y f u n c t i o n 0 引言 够方便地得到多故 障的测试生成矢量， 并且具有较 随着集成 电路技术的发展 ， 数字电路的复杂性 高的故障覆盖率和较短的测试生成时问。 和集成度在不断地提高 ， 这使对数字电路 的测试生 1 多故障转换为单故障 成越来越困难。国内外学者对此进行 了大量的研 本文提到的多故障是指多固定故障， 单故障是 究， 取得了一定进展 ， 但这些研究大多是以单 固定故 指单固定故障。通过插入附加门的方式就可以把多 障为基础 的， 研究多故障测试生成 的非常少。而电 故障转换成为单故障， 这里的附加 门包括 2种 ， 一种 子系统中的某些元件有时必须进行完全测试 ， 以保 是线上 门， 另一种是故 障门。如图 1 a 所示 ， 电路 证系统的可靠性 ， 因此研究数字 电路 的多故障测试 存在一组多故障 ， 口、 b 、 C 、 d为输入 ，A、 B、 c、 D为 生成非 常重要。本文 首先 把多故障转换成为单故 输 出。 、 两根故障线上存在 固定 1 s 一口一1 障， 这样就把多故 障的测试生成问题转化成为单故 故障 ， c C、 d D两根故障线上存在 固定 0 s 一口一0 故 障的测试生成， 大大简化了算法 。由于 电路测试生 障。为了把多故障转换成为单故 障， 需要插入 附加 成问题属于 N P完全问题 ， 鉴于神经 网路在解决 N P 门 完全问题上的成功应用， 本算法在单故障测试生成 线上门 上采用了神经网络的方法。1 9 9 0年 ， 13本学者 F u i i _ 在每一根故障线上插入一个两输入的门， 固定 w a r a 提出了三值神经网络模型 ， 用三值神经 网络表0故障 固定 1 故障 插入与 门 或 门 ， 故障线 的输 示数字电路 ， 可以减小搜索空间， 避免很多不必要 的 入端与插入 的线上 门的一个输入端相连， 线上 门的 赋值 ， 因此三值神经网络应用于数字 电路多故 障的 输出对应原电路故障线的输出。 测试生成 ， 具有很 大优势。实验结果表明该算法能 故障门 ． - ． 20 5．-． 维普资讯 V o l 2 9 N o ． 基于三笪掉经网络的数字电路多故障i贝 0 试生成算法韩之刚， 等 第 2 9 卷第 1 期 故障门是一个 ／ “t 输入的与门， 这里 ／ “t 是指多故 障的数 目。如果线上门是或 门， 故障门的输 出直接 与线上门的另一端相连 ； 如果线上门是与门， 则故障 门通过一个非 门与线上门的另一个输入端相连。如 果故障线上存在的是固定 1 故障， 则故障线的输入 端直接连到故障门的输入端 ， 如果故障线上存在的 是固定 0 故障， 则故障线的输入端通过一个非门与 故障门的输入端相连。故障门的输出端上 的单 固定 故障与故障线上的多故 障等价 ， 这样就把多故 障转 换成为单故障。如图 1 b 中 e处的固定 1 故 障与 图 1 a 中的多故障等价 ， 转换后的电路功能不变。 下面分 2个方面证明该转换方法的正确性。 电路的等价性转换后的电路与原电路功能等 价。 对图 1 b ， 有如下关系 4 0 o 0 6 n 6 CC 口 dC bC d CC 瓦b c Dd口 dd bC d dd b C d 这与图 1 a 的电路功能完全一致。 隐 【 b j蒋 秧 为罩 故障 册 巳 野 图1 多故障电路转换为单故障电路 故障的等价性转换后 的单故障与原电路的多 故障等价 对图 1 a 存在的多故障 ， 输出为 A 1 ； B 1 ；C0； D 0 对图 1 b 存在的单故障， 输出为 A a 1 1 ； B b 11； C C 00； D d 00 可以看出图 1 a 的多故障与图 1 b 故 障门输 出端上的单故障等价。这样就把多故障的测试生成 转换成为单故障的测试生成。 2 单故障测试生成的神经网络模型的建立 数字电路的测 试生成属 于 N P完 全问题 ， 鉴于 神经网络方法在 N P完全问题 上的成 功应用 ， 本文 把神经网络引入到数字电路 的测试生成 中， 这里使 用的是三值神经网络模型， 三值神经网络模型的能 量函数为 1 N ， v N E 一 号∑∑T V i b一∑， f 一 一i 1 1 i 1 N ， v ∑ ∑ 1 一 v j 1 一v i K i I 』 I 式中 Ⅳ 神经网络 中神经元的数 目； 神经元 i 和 ． 之间的权值； 神经元 i 的状态值 ； 神经元 i 的内部参数 ； 当 、 都是 时 i 与 ． 之间的权值 ； 常量。 神经元 状态值可 以取 0 、 1 、 ， 假定 ， ， ，Ti 0。 任何一个基本逻辑门电路的节点 信号线 都可 以用一个神经元来表示 ， 且节点 的值是神经元的状 态值 ， 相互有连接关系的神经元用具有权值的直线 连接起来 ， 电路的逻辑 函数则 可以由规定 的神经元 阈值和其相互连接的权值来实现。根据文献[ 3 ] 中 的方法可得到基本 门电路 的神经网络模型 ， 并得到 对应的能量函数。 对符合一种基本门电路功能函数的取值称为这 种门电路的一个相容状 态， 其他不符合功能函数的 取值称为门的非相容状态 ， 对一种门电路的一个相 容状态 ， 能量函数的值 为 0 ， 否则不为 0 。这样就可 以用能量函数来表示基本门电路的传输特性。对任 一 组合电路 ， 利用构成它的基本 门的神经 网络模 型 能获得一种与组合电路相对应的神经网络模型。 数字 电路 中一个节点有故障 ， 如果存在 电路 的 一 组输入使电路的输 出在无故障与有故障时相异， 则这组输入就为该故障的一个测试矢量。用神经 网 络进行测试时需要构建电路的约束网络。约束网络 由故障电路 已注入故障 ， 无故障 电路和一个接 口 电路组成 。对单输 出电路接 口由一个非 门组成 ； 对 m个输 出端的电路 ， 接 口由 m个二输入 的异或门和 一 个或门构成 ， 并且或 门的输 出为 1 ， 这样的限制是 为了当约束 网络 的输入矢量为故障的测试矢量时， 妻 维普资讯 第 2 9 卷第 1 期 基于三值神经网络的数字电路多故障测试生成算法韩之刚， 等 V o 1 ． 2 tg N o ． i 被测电路 C U T 的故障输出与无故障输出不同。图 2是单输出电路的约束网络 ， 图 3是多输 出电路的 约束网络。 图 2 单输出电路的约束网络 等策略 ， 能提供并行全局搜索和鲁棒性搜索 ， G A常 用于求给定问题的一个全局最优解。 具体算法如下 1 初始化。 2 把多故障电路转换成为单故障电路， 对单 故障电路设置种群规模为 Ⅳ， 设定交叉概率 P 。 ， 变 异概率为 尸 m 。 3 计算种群中每个个体的适应度值。 4 找出适应度值最大的和适应度值最小的个 体。 5 用适应度值最大的个体代替适应度值最小 的个体 。 6 根据轮盘规则选出 2个个体 ， 按概率 P ， 进 申 一 ～ 一 一 翅 维普资讯 V o 1 ． 2 9 N o ． 1 基于三值神经网络的数字电路多故障测试生成算法韩之刚， 等 第 2 9 卷第 1 期 { s t r u c t i n d i v i d u a l*t e m p ； i n i t i al i z e ； ／ ／ 初始化 c h a ng m t s ；／ ／ 多故障转换为单故障 f o r g e n 0 ； g e n m a x g e n ； g e n { save v e c t o r ； ／ ／ 保存得到的故障测试矢量 g e n e r a t i o n ； ／ ／ 产生新一代种群 r e p o r t ； ／ ／ 输出新一代统计信息 t e mp o l d po p； o l d popn e w p o p ； ／ ／ 更新新一代为当前代 n e wp o p t e mp { } 4实验结 果 根据 上述算 法 ， 在 p e n t i u m 4计算 机 上 内存 5 l 2 M 对 I S C A S 8 5国际标准电路集合 中的部分 电路 进行了试验 ， 用 c语言对本文算法编制程序结果如 表 1 所示 。从 表 中数据可见本算法故障覆盖率较 高 ， 故障平均测试时间较短。 表 1 实验结果 5 结语 本文将三值神经网络应用于数字电路多故障测 试生成， 首先把多故障转换成与之等效的单故障， 再 用三值神经网络方法表示单故障电路， 最后用遗传 算法求解能量 函数的最 小值点得到故 障的测试矢 量。实验结果表明本算法具有较高的故障覆盖率和 较短的测试时间。 参考文献 [ 1 ] Y o n g C h a n g K i m， V i s h w ani D． A g r a w a1． Mu l t i p l e F a u lt s M o d e l i n g ， S i m u l a t i o n and t e s t [ C ] ． P r o c ． o f 1 5 t h I n t e r n a ti o n a l C o n f e r e n c e o n V L S I D e ． s i g n， 2 O O 2 5 55 8 ． [ 2 ] H i d e o F U J I WA R A ． 1 1 a r e e V al u e d N e u r al N e tw o r k s f o r T es t G e n e r a t i o n [ C ] ． P r o c ． o f 2 0 t h F a u l t T o l e r ant C o m p u t i n g S y m p o s i u m． 1 9 9 0 6 6 6 7． [ 3 ] 陈朝 阳， 丁明跃 ． 基于神经网络测试码生成 的一个鲁棒算法[ J ] ． 华中理工大学学报 ， 1 9 9 9 ， 2 7 9 9 09 1 ． [ 4 ] 徐建斌 ， 李智 ． 神经 网络在组合电路故障模拟测试生成算法中的 应用 [ J ] ．电路 与系统学报 ， 2 0 0 1 ， 6 4 1 0 91 1 0 ． 作者简介韩之刚 1 9 5 1 一 ， 吉林 吉林市人 ， 北华大学 电工电子 部主任 ， 副教授 ， 毕业于原北 京钢铁学院 ， 电气工程及 自动化专业 ， 主 要从事电 工 电子 技 术应 用 工作 ， 电话 0 4 3 26 1 8 1 6 0 1 ， 电 子信 箱 J m n z h i g a n g j l 1 2 6 ． c o i n z h a o y i n g j l 1 2 6 ． c o n． 收稿 日期 2 0 0 7 ． 1 0 - 2 9 本刊声明 煤矿机械 杂志连续 4次被认定为中文核心期刊 ， 黑龙江省优秀期刊， 列入 剑桥科学文 摘 、 文摘杂志 来源期刊。我刊已人编 中国学术期刊 光盘版 ， 并加入“ 中国期刊网” 和万 方数据网， 作者稿酬由本杂志社一次付清。本杂志社属 自负盈亏单位 ， 在本刊发表文章收发表 费， 同时也付给作者稿酬 ， 如有不同意上述 3 条者， 请来函说明， 本杂志社将做适当处理。投稿 必须通过 Em a i l 发来 ， 投稿只能用 wo r d排双栏版并请仔细阅读 ， 字数在 3 0 0 0～5 0 0 0字为 宜。投稿之前 ， 请查看 m k j , , ． c n 网址投稿须知 ， 在第一作者简介文末留下联系电话 、 电子信箱。 2 0 0 8年本刊仍为国际标准 A 4开本 ， 2 0 8页， 胶订， 定价每册 l 5 元 ， 全年 l 2册 1 8 0元 ， 订阅 者可到当地邮局订阅， 也可来函索取征订单， 欢迎订阅、 投稿。 2 0 0 8年本刊发布广告价格如下 老客户老价格， 新客户执行新价格， 多登优惠 元／ 版 封面 彩色 1 0 0 0 0 封二 彩色 8 0 0 0 插页 彩色 7 0 0 0 封底 彩色 9 0 0 0 封三 彩色 7 5 0 0 插页 黑白 4 0 0 0 插页 黑白半版 2 4 0 0 内页 黑白 2 4 0 0 内页 半版 1 2 0 0 维普资讯