bdd在组合电路测试中的应用研究

《bdd在组合电路测试中的应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、哈尔滨工程大学硕士学位论文BDD在组合电路测试中的应用研究姓名：刘新会申请学位级别：硕士专业：计算机软件与理论指导教师：马光胜20060101哈尔滨工程大学硕士学位论文摘要随着集成电路设计规模不断增大，其出现故障的可能性也相应增加，这导致故障测试变得越来越重要。准确快速地检测出故障，可以加快电路设计的进程，进而产生巨大的经济效益。二元判决图是一种表示布尔函数的有效方法，在计算机科学以及数字电路与系统等领域中有广泛的应用。本文主要研究二元判决图在组合电路测试中的应用。首先，介绍y--元判决图的原理，说明了变量排序对于二元判决图体积的影

2、响。在此基础上，提出了一种启发式变量排序算法，它能够用较短的运算时间得到良好的变量排序。其次，介绍y-元判决图的操作，举例说明使用apply与reduce算法建立逻辑函数的二元判决图方法，比较了该方法和ITE算法的优缺点，并对ITE算法提出了两条改进的措施。再次，研究了二元判决图在组合电路的故障检测中的应用。二元判决图测试生成方法克服了传统测试方法需要多次回溯的缺点，减少了测试生成的时问，节省了测试的成本。但是现有的二元判决图测试生成方法复杂度比较高，本文将BDD与通路敏化法相结合，提出了一种改进的方法IBDDT。它降低了BDD测试

3、生成算法的复杂度，实验结果表明IBDDT有良好的使用性。最后，研究了二元判决图在测试矢量优化中的应用。本文利用二元判决图对测试矢量集进行压缩，得到了一个压缩的测试集，减少了测试矢量，有利于降低开发成本。关键词：组合电路；二元判决图；变量排序；ITE算法；测试生成哈尔滨工程大学硕士学位论文AbstractWiththedevelopmentoftheintegratedcircuits，theprobabilityofemergingfaultsishigherandhi曲er,andthefaultdetectionbecomesm

4、oreandmoreimportantThep；'ocessofcircuitdesigncanbespeededupandtheenormousbenefitofeconomycanalsobebrougIltwhenthefaultsallfastandcorrectlydetected．Binarydecisiondiagram(BDD)isaneffectivedatastructureforrepresentingBooleanfunctions．1tiswidelyusedinthefieldsofcomputersci

5、enceanddigitalcircuitandsystem．ThemainworkofthispaperistheapplicationsofBDDincombinationalcircuits．First,theprincipleofBDDisintroducedinthispaper．TheimportanceofvariableorderingtoaBDDisalsoilluminated．Aheuristicvariableorderingalgorithmispresented,whichcangenerategoodv

6、ariableorderinginashorttime．Second，theoperationsofBDDareintroducedinthispaper．ApplyalgorithmandreducealgorithmcaIIbeusedtoconstructtheBDDofBooleanfunctions．Itsexampleisgiveninthispaper．ComparedwiththeITEalgorithm，itislesseffective．低suggestionsallmadetotheIrEalgorithm．眦

7、meapplicationofBDDton圮testgenerationforcombinationalcircuitsisstudied．ThetestgenerationmethodsofBDDavoidenormousbacktrackingprocess．Theyspeedupthe、testgenerationandsavethecostoftestHowever,theircomplexityisveryhigh．AnimprovedmethodnamedIBDDTispresentedinthispaper．Itcom

8、binesBDDandthepathsensitizedmethodandreducesthecomplexity．Theexperimentalresultsdemonstratetheefficiencyofthismethod．