论文部分内容阅读
随着数字集成电路技术的飞速发展,集成电路的测试生成变得越来越困难,花费的时间也越来越多。对于大规模的集成电路,传统的测试生成算法已不再适用,寻找新型、有效的测试生成算法已成为一个重要的研究课题。 DNA计算是在计算科学和分子生物学的基础上发展起来的一个新颖而极具发展潜力的学科。它与遗传算法(GA)天生就具有某种必然的联系。本文采用GA作为DNA计算进行复杂优化问题求解的桥梁,在基于故障模拟的基础上,建立了应用DNA-GA解决组合电路测试生成问题的算法流程。针对基于模拟的测试生成流程的特点,在算法流程中引入了两个启发性过程。本算法通过DNA的四字符集Σ={A, C, G, T}的编码,引入基因级的遗传操作,保证了种群的多样性;控制测试生成不同阶段中DNA链生成测试集的大小,减小了测试集的冗余,加快了测试生成速度。为将本算法与其他算法进行比较,在国际标准电路iscas’85上对该算法进行了验证,并对结果进行了分析。实验结果表明本文算法获得到了较高的故障覆盖率,同时生成的测试矢量集大幅度缩小,证明本算法用于组合电路测试生成是有效的。 从DNA生化实验实现计算的角度,本文研究了组合电路测试生成的SAT解决方法,并建立了基于表面型的DNA生化计算模型。通过分析组合电路测试生成的CNF特点,引入了两点改进方法。在DNA计算模型中将原电路CNF和故障电路CNF的变量分别编码,降低了DNA编码的复杂度,使原电路CNF的DNA解链重复使用,降低了耗材。最后给出了应用DNA计算解决组合电路测试生成的算法流程。由于DNA计算所具有的高度并行性、海量存储能力等特点,本文算法将在特大规模组合电路测试生成中显现出优越性。