申延强，韩华亭

（空军工程大学防空反导学院，西安　710051）

基于免疫粒子群文化算法的数字电路故障诊断

申延强，韩华亭

（空军工程大学防空反导学院，西安710051）

为改善粒子群算法摆脱局部极值点的能力，提升种群进化的多样性，将免疫算法中免疫机制引入到粒子群算法中形成免疫粒子群算法；为有效提高故障覆盖率和缩短测试生成时间，将免疫粒子群算法引入文化算法框架中形成免疫粒子群的文化算法。将其应用于数字电路故障模型仿真实验并与其他测试生成算法进行对比，结果表明该算法能够有效提高故障覆盖率，缩短测试生成时间，在大规模电路测试生成与故障诊断中更具优势。

数字电路，测试生成，测试矢量，免疫粒子群算法，文化算法

0　引言

随着电子技术的发展，数字电路的规模越来越大，结构越来越复杂，这使得数字电路的测试生成与故障诊断变得越发困难。数字电路的测试生成，就是寻找能激活电路中的故障并将其传播到原始输出端的故障测试输入矢量。而最关键的部分是找到故障覆盖率高、测试时间短的测试生成算法。传统的测试生成算法需要回退、传播和确认，过程复杂，测试时间长，已无法满足现代高集成度数字电路的测试要求。近几年，仿生学算法发展迅速，可以有效地解决组合优化问题，而测试生成问题本质就是组合优化问题，因此，很多仿生优化算法被用到数字电路的测试中，例如，粒子群算法、免疫算法等。将仿生优化算法应用于测试生成，可以使测试生成问题得到简化。本文将免疫粒子群算法引入到文化算法的框架中，很好地解决了免疫粒子群算法和文化算法中存在的不足，结合它们各自的优点，更加有效地进行数字电路的测试生成。

1　免疫粒子群的文化（CA-IA-PSO）算法

1.1粒子群（PSO）算法

其中，i=1，2，…，n；d=1，2，…，D；t表示第t代；w为惯性权重；r1，r2是［0，1］上的随机数。

1.2免疫（IA）算法

免疫算法基于生物免疫系统机理。仿照人工免疫系统的高频变异、免疫记忆、克隆复制等优势，使系统能逃逸出局部最优解，获得全局最优解。克隆免疫算法主要有克隆扩增选择、交叉、变异、进化替代以及局部灭绝5部分。

克隆复制是克隆适应度高的粒子，粒子克隆的概率与适应度成正比。粒子适应度函数为：

对于克隆扩增后的子群体，进行高概率的超变异。变异概率P（Xi）=kfi，其中k为归一化系数。

为利于群体间信息交互，提高群体协作能力，引用免疫系统中的交叉极值对微粒群个体进行交叉。随机两两粒子进行杂交，产生同样数目的子粒子。子粒子的位置由父粒子的位置的算数加权来计算。交叉算子如下：

其中，X为d维的位置向量；X1（t）和X2（t）为选择进行杂交操作的粒子；r为d维均匀分布且每个分量都在［0，1］取值的随机向量。速度用同样的公式计算，只是将r取不同的随机向量。

抗体种群在克隆算子的作用下的演化过程如图1所示。

图1　粒子群免疫算法过程

1.3免疫粒子群的文化（CA-IA-PSO）算法

文化算法（CA）是模拟人类社会进化过程的计算方法。文化被社会成员全面地接受，指导社会成员的行为，吸纳成员个体的先进经验而不断地更新自己，且为个体行为在社会中的表现提供说明。CA由群体空间（Population Space，PS）和信仰空间（Belief Space，BS）两部分组成，二者相互独立。PS在微观层面模拟个体按照一定规则进化的过程，通过进化规则和性能评价进行迭代求解问题。BS在宏观层面通过自身的演化，模拟文化形成、传递的进化过程。文化算法的基本模型如图2所示。

文化算法框架提供了一种多进化过程的计算模型，传统的CA中，PS由EP（有限状态机模型）来优化，BS由GA（遗传算法）来优化。CA算法全局搜索能力强，算法复杂，但其弱点是收敛速度慢，求解时间过长。

粒子群算法全局搜索能力弱，易于“早熟”，但是其算法简单，收敛速度快。为改善粒子群算法摆脱局部极值点的能力，提升种群进化的多样性，将免疫算法中免疫机制引入粒子群算法中形成免疫粒子群算法。

图2　文化算法的基本模型

在此基础上，本文将免疫粒子群（IA-PSO）算法引入文化算法的框架中，以解决免疫粒子群中存在的问题以及数字电路测试生成问题。基于IA-PSO的文化算法程序结构流程如图3所示。

图3　基于IA-PSO的文化算法程序结构流程

在进化过程中，粒子跟踪个体最优与全局最优两个极值来更新自己。将PS中利用适应度函数计算求得的全局最优传递到BS，替代BS中适应度差的粒子，再利用IA-PSO更新BS，当满足影响条件时，利用得到的新的BS群体继续指导PS中的粒子演化。不断循环直到满足算法结束条件为止。

2　基于CA-IA-PSO的测试生成

2.1典型数字电路模块功能和工作原理

码形成器是某机电设备上角速度编码器的重要部件，码形成器电路分为主路和辅路两部分。辅路电路完成主路电路所需非控制信号的输入和时钟的控制；主路电路将8组7位并行二进制代码转化为串行二进制代码并分别输出到延迟器和设备上的控制单元。本文以主路部分作为研究对象。主路部分电路利用7个54LS151芯片和2个54295芯片把8组7位并行二进制代码转换为串行二进制代码。54LS151芯片是LSTTL型8选1数据选择器，包含全芯片的二进制译码，完成8选1数据输出。它含一个选通输入G，低电平有效；输出W是根据输入管脚ABC的输入数字信号选择D0-D7输入中的一位数据输出。54295芯片的功能优点类似移位寄存器，是将54LS151芯片选通输入的8组7位并行二进制代码分别转化为串行二进制代码输出。

对主路电路进行深入分析，分析结果如表1所示。该电路输入激励较多，输出响应少；门的个数较少，但不都是基本门，功能较复杂；故障总数较多，但由于门的类别不是单纯的与门之类的基本门，电路中每根设定的故障线都有其实际的作用，没法进行等效压缩。总的来说，该电路较典型，能较好完成整个测试生成过程。

表1　主路部分电路分析结果

2.2数字电路模块测试方案

数字电路测试生成与故障诊断方案的设计框图，如图4所示。

图4　测试生成与故障诊断方案设计框图

数字电路的故障诊断，采用基于故障字典的诊断方法。故障字典的主要思想包括。①测试矢量集的生成。预先根据实际需要，基于测试生成算法确定测试矢量集。②编制故障字典。设定电路存在某一故障，将激励的响应特征作为故障特征，将所有可能的故障响应编制成故障与特征对应的故障字典。③故障定位与故障字典完善。对电路施加与测前模拟时同样的激励，取得故障响应的特征，最后在故障字典中查找对应的故障，若无，则故障字典未收录此故障，将其收录完备。

角速度编码器数字电路测试与故障诊断以主控计算机为测试系统主机，通过编制各电路或芯片的测试程序、诊断控制程序，建立故障字典实现对板级数字电路的故障诊断。主控机通过接口适配器连接测试诊断平台完成待测电路的预处理、故障建模、故障表的生成、基于测试生成算法的测试矢量集的生成、对相应的故障仿真、故障表与测试矢量集中测试矢量对应关系表的生成。同时对被测电路施加测试数据（测试矢量），并把响应数据采集到计算机上进行综合分析、处理；最后完成故障字典的生成，以便定位故障。对有相同故障测试矢量集的故障，能进一步压缩则压缩，否则一般通过测取测点信号，采用倒序方式确定。

故障诊断的核心在于诊断定位，就是根据电路响应，利用故障仿真结果进行比较、检索、测试。

2.3数字电路模块测试生成与故障诊断过程

主路电路测试生成与故障诊断步骤如下：

（1）通过输入辅路电路拓扑结构模拟仿真其正确的输出信号，以此确保主路在进行测试与故障诊断时不受其他干扰。

（2）对主路电路输入引脚、输出引脚、门和芯片、故障端进行节点编号。将求元件的故障转化为求元件输入输出端线的故障，即把定位故障元件转化为确定有故障的端线，以避免出现漏测等错误，同时将该电路进行分块并略去无用引脚。

（3）利用组合测试系统搭建测试诊断平台，将算法集成到组合测试系统软件模块中，在主控计算机的控制下运用本文所述数字电路测试生成方法进行该板级电路模块的测试生成。

（4）整理故障测试集。通过测试集的压缩、故障仿真等对测试集进行整理，尽量使单个故障只与测试向量对应且每个故障对应的测试向量不同。对于一个测试生成对应几个故障可以使用探针确定具体故障节点。对测试集进行处理后，生成故障与测试矢量集相对应的测试表。

（5）通过计算机仿真将生成的测试矢量集加入无故障的主路部分仿真电路并采集相应的输出响应，生成标准故障字典。

在检测电路板实物某个节点是否有故障时，查询故障字典，将该故障对应的测试矢量加入故障电路板，所得输出结果与故障字典中正确值相同，则是该节点故障否则是该节点无故障，从而定位故障元件。

3　实验结果及分析

分别将PSO算法、IA-PSO算法和CA-IA-PSO算法用于主路电路的测试生成，结果如表2所示。

表2　主路部分电路测试生成结果

电路虽然故障数较多，但运用仿生测试生成算法同样能达到100%的故障覆盖率，表明该电路的故障都能被激活，且能传播到输出端被测试出来。电路中有芯片54LS151、54295，比门电路复杂，测试生成时间比基本门电路长。基于免疫粒子群文化算法在相同的仿真环境下，得到的测试生成时间比粒子群算法所耗时间更短，证明了算法有效。

主路部分电路是在时钟控制下输出的，不同的时钟控制，测试生成时间会略有不同，本文中时钟控制设置为20 ns。

由于时钟控制和电路结构的特殊性，将电路分块，在测试生成过程，控制时钟，每次只用一个芯片的4个输入和后面门电路的3个输入即可完成后半部分门电路节点的测试生成，后面门电路的节点测试生成完后再分别进行剩余芯片上节点的测试生成，能节省测试生成时间。表3为电路分块后的测试生成结果。

表3　电路分块后的测试生成结果

分析电路的结构对电路进行合理的分块对缩短测试时间具有一定作用。

4　结论

将免疫粒子群文化算法用于编码器电路主路部分的测试生成，得到以下结论：

（1）根据不同仿生算法的优缺点，可以将其结合使用。本文利用粒子群算法与免疫算法的优势互补性，同时利用免疫算法的特点，提出免疫粒子群算法文化算法，克服单一算法的缺陷。

（2）基于免疫粒子群文化算法在相同初始条件、仿真环境和适应度函数下能提高故障覆盖率，缩短测试生成时间，在用于大规模电路时，优势更明显，因而具有实用价值和应用前景。

（3）分析电路的结构并将电路进行合理分块对缩短测试时间具有一定作用。

［1］刘小东，孙圣和.基于遗传算法的自适应测试生成［J］.微电子学与计算机，2002，31（3）：14-16.

［2］王宇，付立平，周广田，等.面向数字电路测试生成的智能方法研究［J］.黑龙江大学自然科学学报，2010，27（6）：827-831.

［3］杨士元.数字系统的故障诊断与可测性设计［M］.2版.北京：清华大学出版社，2000：39-49.

［4］徐建斌，李智.神经网络在组合电路故障模拟测试生成算法中的应用［J］.电路与系统学报，2001，6（4）：109-110.

［5］高鹰，谢胜利.免疫粒子群优化算法［J］.计算机工程与应用，2004，6（3）：5-7.

［6］潘中良，张光昭.数字电路多故障测试生成的神经网络方法研究［J］.仪器仪表学报，1999，20（3）：232-234.

［7］赵莹，吴丽华.基于三值神经网络的多故障测试生成算法［J］.哈尔滨理工大学学报，2004，9（8）：20-23.

［8］黄鑫，常天庆，邢士勇.数字电路板自动测试与故障诊断系统的设计［J］.计算机测量与控制，2010，18（7）：1512-1514.

［9］王灵，俞金寿.基于离散粒子群和支持向量机的故障诊断方法［J］.华东理工大学学报：自然科学版，2005，31（5）：697-700.

［10］赵莹，吴丽华，马怀俭.基于三值神经网络的组合电路测试生成算法［J］.哈尔滨理工大学学报，2004，9（4）：20-23.

Test Pattern Generation for Digital Integrated Circuits Based on CA-IA-PSO Algorithm

SHEN Yan-qiang，HANHua-ting
（Air Defense and Antimissile Institute，Air Force Engineering University，Xi’an 710051，China）

In order to improve the ability to get rid of partial extreme spot and the diversity in evolution，IA algorithm is imported into PSO algorithm to form IA-PSO algorithm.For the purpose of raising fault rate and shortening test pattern generation time，CA algorithm into is imported IA-PSO algorithm to form CA-IA-PSO algorithm.Finally，single stuck-at fault is adopted and different algorithms is used to the simulation experiment of test pattern generation，the result is that CA-IAPSO algorithm can solve the problem of test pattern generation more practically and efficiently，especially in large digital circuits.

digital integrated circuits，test pattern generation，test vector，IA-PSO algorithm，CA algorithm

TN407

A

1002-0640（2016）08-0192-04

2015-05-04

2015-07-09

申延强（1991-），男，河北邯郸人，硕士研究生。研究方向：地空导弹发射系统故障诊断。