基于分布估计算法的组合电路测试生成

Automatic Test Pattern Generation with Estimation of Distribution Algorithms for Combinational Circuits

基于遗传算法生成的测试矢量集的故障覆盖率要低于确定性方法.本文分析指出造成这种现象的一个可能原因在于,组合电路测试生成过程中存在高阶、长距离模式,从而导致遗传算法容易陷入局部极值或早熟收敛.为此,本文首次提出使用分布估计算法生成测试矢量.该方法使用联合概率分布捕捉电路主输入之间的关联性,从而避免了高阶、长距离模式对算法的影响,缓解了算法早熟收敛问题.针对ISCAS-85国际标准组合电路集的实验结果表明,该方法能够获得较高的故障覆盖率.

The fault coverages achieved by the test generation procedures based on genetic algorithms are smaller than the deterministic test generation procedures for combinational circuits.One of the possible causes for this deficiency is the high,long-distance schema, which exists in the process of automatic test pattern generation. Thus genetic algorithms in dealing with such problems easily fall into local optima or premature convergence.In this work,we firstly propose the test generation procedures based on estimation of distribution algorithms. Estimation of distribution algorithms are able to capture the interrelations between the primary inputs by joint probability distribution. And therefore obviate the influence of the high, long-distance schema;alleviate the problem of premature convergence. The experimental results for benchmark circuits prove that the proposed procedure can achieve higher fault coverage.