试论基于dna计算的组合电路测试生成研究

《试论基于dna计算的组合电路测试生成研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号密级UDC编号桂林电子科技大学硕士学位论文题目:基于DNA计算的组合电路测试生成研究(英文)ResearchonAutomaticTestGenerationofCombinationalCircuitBasedonDNAComputing研究生姓名：马丽指导教师姓名、职务：许川佩教授申请学科门类：工学硕士学科、专业：检测技术与自动化装置提交论文日期：2008年4月论文答辩时间：2008年6月15日年月日万方数据独创性（或创新性）声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别

2、加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得桂林电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切相关责任。本人签名：日期：关于论文使用授权的说明本人完全了解桂林电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属桂林电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为桂林电子科技大学。学校有权

3、保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。（保密的论文在解密后遵守此规定）本学位论文属于保密在年解密后适用本授权书。本人签名：日期：导师签名：日期：万方数据摘要摘要随着数字集成电路技术的飞速发展，集成电路的测试生成变得越来越困难，花费的时间也越来越多。对于大规模的集成电路，传统的测试生成算法已不再适用，寻找新型、有效的测试生成算法已成为一个重要的研究课题。DNA计算是在计算科学和分子生物学的基础上发展起来的一个新颖而极具发展潜力的学科。它与遗传算法（GA

4、）天生就具有某种必然的联系。本文采用GA作为DNA计算进行复杂优化问题求解的桥梁，在基于故障模拟的基础上，建立了应用DNA-GA解决组合电路测试生成问题的算法流程。针对基于模拟的测试生成流程的特点，在算法流程中引入了两个启发性过程。本算法通过DNA的四字符集§=fA;C;G;Tg的编码，引入基因级的遗传操作，保证了种群的多样性；控制测试生成不同阶段中DNA链生成测试集的大小，减小了测试集的冗余，加快了测试生成速度。为将本算法与其他算法进行比较，在国际标准电路iscas'85上对该算法进行了验证，并对结果进行了分析。实验结果表明本文算

5、法获得到了较高的故障覆盖率，同时生成的测试矢量集大幅度缩小，证明本算法用于组合电路测试生成是有效的。从DNA生化实验实现计算的角度，本文研究了组合电路测试生成的SAT解决方法，并建立了基于表面型的DNA生化计算模型。通过分析组合电路测试生成的CNF特点，引入了两点改进方法。在DNA计算模型中将原电路CNF和故障电路CNF的变量分别编码，降低了DNA编码的复杂度，使原电路CNF的DNA解链重复使用，降低了耗材。最后给出了应用DNA计算解决组合电路测试生成的算法流程。由于DNA计算所具有的高度并行性、海量存储能力等特点，本文算法将在特大

6、规模组合电路测试生成中显现出优越性。关键词：组合电路；自动测试生成；故障模拟；DNA计算；SAT问题.{I{万方数据桂林电子科技大学学位论文AbstractWiththedevelopmentofmicroelectronicstechnologyandtheincreasingIC(Integr-ateCircuit)scale,ICtestisbecomingincreasinglydi±cultandtakesmoreandmoretime.Forlarge-scaleIC,thetraditionaltestgenerati

7、onalgorithmisnolongerapplica-ble.Soitneedsto¯ndanewande®ectivetestgenerationalgorithm.DNAcomputingisanovelandhighlypotentialsubjectsdevelopedonthebasisofcomputerscienceandmolecularbiology.Onceitwasborn,ithasainherentlinkwithGA(GeneticAlgorithm).ThispaperusesGAasthebrid

8、geofDNAcomputingsolvingthecomplexoptimizationproblems.Itproposesanewalgorithm°owexploitedDNA-GAtosolvetestgenerationf