下载文档原格式
收稿日期:2005-09-02;修返日期:2005-11-25基金项目:国家“973”计划资助项目(2004C B 318003);国家自然科学基金资助项目(60373113)利用FAN 算法进行组合电路的等价性检验*曾 琼1,2(1.中国科学院成都计算机应用研究所,四川成都610041; 2.成都信息工程学院计算机基础教学部,四川成都610041)摘 要:讨论了组合电路的等价性检验方法,分析了FAN 算法的关键技术。
利用该算法进行了组合电路的等价性检验,实验结果表明了该方法的有效性。
关键词:等价性检验;ATPG;D-算法;PODEM 算法;FAN 算法中图法分类号:TP301 文献标识码: A 文章编号:1001-3695(2006)12-0025-03Equ iva lence Checking for Combin ation al Circuit s w ith FU N AlgorithmZE NG Qiong 1,2(1.Chengdu Ins titute of Computer Ap plication,Chines e Academy of Sciences,Chengdu Sichuan 610041,China;2.Fundamental Teaching Dept.of Computer,Chengdu University of Infor mation Technology,Chengdu S ichuan 610041,China)Abst ract :This paper discusses equiva lence checking for com binat iona l circuits and analyz es t he key techniques of FAN algo-rithm .We check equiva lence of com bina tional circuit s w it h F UN algorit hm ,and experim enta l res ult s show that FAN a lg orithmis efficient.Key wo rd s:E quiva lence C hecking;AT P G(Autom at ed T es t Pa t tern Generat ion);D-algorit hm ;POD EM Alg orit hm ;FA N Alg orithm 等价性检验是数字电路形式化验证技术的主要验证方法之一。
集成电路测试生成算法综述摘要：随着集成电路芯片向深亚微米、特大规模集成电路和高密度方向发展，进行测试所需要的成本也越来越高，因此寻找计算量合理、故障覆盖率较高的测试生成算法已成为电路测试领域十分重要的研究课题。
本文对目前电路测试生成算法做了一些介绍。
关键词：集成电路；测试生成算法1．引言随着电子技术的飞速发展，集成电路的规模不断扩大，而引脚数却有一定的限制，许多电路被封装在芯片内部，外部可达到的测试点、原始输入、原始输出所占的比例越来越少，导致集成电路的测试和故障诊断越来越困难。
故障诊断中最重要的是要找到故障的测试矢量，即测试生成。
集成电路的测试生成问题是数学上公认的难题——NP完全问题，在过去几年中，国内外的一些学者虽然提出了许多新的测试生成算法，但是到目前为止还没有一种算法适用于所有的电路，集成电路的测试生成问题己经严重地影响了微电子技术的发展。
2．集成电路测试生成算法的分类(1)按照被测电路来分可以分为组合电路测试生成算法和时序电路测试生成算法两类。
组合电路测试生成算法的研究对象是组合电路，时序电路测试生成的研究对象是时序电路。
(2)按照获取测试矢量集的方法来分可以分为确定性测试生成算法和非确定性测试生成算法。
非确定性测试生成主要是伪随机测试和加权随机测试算法。
确定性测试生成算法是通过算法确定出测试矢量或测试序列。
(3)按照故障模型来分可以分为高级测试生成算法和低级测试生成算法两大类。
高级测试生成算法的故障覆盖率一般不如低级测试生成算法的高，但是测试时间要比低级的测试生成时间少。
(4)按照算法采用的技术或理论来分可以分为层次式的测试生成算法、符号化的测试生成算法、基于遗传算法的测试生成算法、启发式的测试生成算法等。
层次式的测试生成算法将电路的无故障部分用功能块表示，有故障的部分用门电路表示；符号化的测试生成算法基于二进制判决图(BBD)；基于遗传算法的测试生成算法通过确定能量函数的最小值点求得测试矢量；启发式的测试生成算法使用一些启发式的技术。
《集成电路测试》实验指导书南通大学集成电路重点实验室2009年6月实验一 测试图形生成及验证一、实验目的熟悉对被测电路给定故障生成测试图形的过程，掌握异或法和D 算法的具体运用。
二、实验原理参考教材P74 4.2.1 异或法， P82 4.4 D 算法三、实验内容abcd(1) 用异或法对5/0故障生成测试图形；(2) 用D 算法对6/0故障生成测试图形；(3) 对以上所产生的测试图形进行验证；（在Quartus II 中进行验证）四、实验报告写出测试图形生成的具体过程，给出整个实验的原理图和运行结果，分析实验结果的正确性。
f实验二伪随机序列生成一、实验目的了解随机测试和伪随机测试的基本概念；掌握LFSR的基本结构和M序列的基本特性。
二、实验原理基于故障的确定性测试方法是指用专门的算法对给定的故障生成测试图形，优点是生成的测试图形长度短，但生成过程比较复杂，测试施加比较困难。
由微处理器的测试软件算法或者专用的测试电路可容易生成随机的或伪随机的测试图形，并具有较高的故障覆盖率，因此在集成电路测试中得以广泛应用。
如果一个序列，一方面它是可以预先确定的，并且是可以重复地生产和复制的；一方面它又具有某种随机序列的随机特性（即统计特性），我们便称这种序列为伪随机序列。
因此可以说，伪随机序列是具有某种随机特性的确定的序列。
它们是由移位寄存器产生确定序列，然而他们却具有某种随机序列的随机特性。
因为同样具有随机特性，无法从一个已经产生的序列的特性中判断是真随机序列还是伪随机序列，只能根据序列的产生办法来判断。
伪随机序列系列具有良好的随机性和接近于白噪声的相关函数，并且有预先的可确定性和可重复性。
伪随机序列的电路为一个反馈移位寄存器，它可分为线性反馈移位寄存器（简称LFSR 计数器）和非线性反馈移位寄存器，由线性反馈移位寄存器（LFSR）产生的周期最长的二进制数字序列称为最大长度线性反馈移位寄存器序列，通常简称为M序列。
组合电路的故障测试生成并行ATPG算法研究秦李青;颜学龙【期刊名称】《大众科技》【年(卷),期】2015(017)004【摘要】Automatic test pattern generation (ATPG) is the automatic process of generating test vector for the circuit under test according to the test generation algorithm by computer or other tools. This paper presents a bit-level parallel (split-into-W-clones) automatic test vector generation algorithm, which decisions convert into bit-wise logic operation. It selects the optimal path for the forward and backward implication, increases the probability of per backtrace successfully in order to reduce the number of backtrace , accelerate test vector generation and improve the fault coverage by combining the algorithm with the SCOAP testability measure . The improved algorithm has a good performance by the experiment.%自动测试向量生成(ATPG)是借助计算机或者其他工具根据一定的测试生成算法自动的为被测电路生成测试向量的过程.文章给出了一种位级并行(split-into-W-clones)自动测试向量生成算法,该算法的判决按照位逻辑操作运算进行.通过将该算法与SCOAP 可测性测度结合起来,为该算法前后向蕴涵选择最优路径,提高每次回溯成功的概率,达到减少回溯次数、加速测试向量的生成和提高故障覆盖率的目的.通过实验看出改进后的算法具有良好的性能.【总页数】2页(P17-18)【作者】秦李青;颜学龙【作者单位】桂林电子科技大学电子工程与自动化学院,广西桂林 541004;桂林电子科技大学,广西桂林 541004【正文语种】中文【中图分类】TP206【相关文献】1.组合电路的故障测试生成D算法研究 [J], 陈永刚;张彩珍2.组合逻辑电路多故障测试生成算法的研究 [J], 吴丽华;商庆华;俞红娟3.神经网络在组合电路多故障测试生成算法中的应用 [J], 杨兴;谢志远;冯力娜4.组合电路桥接故障诊断的测试生成及优化 [J], 李蕙;竺红卫5.一种数字组合电路多故障测试生成的高效算法 [J], 曹宁;杨巨前因版权原因，仅展示原文概要，查看原文内容请购买。
