测试生成算法

4 SOCRATES算法 SOCRATES在FAN算法的基础上提出一种全局的蕴含策略,改进的唯一敏化策略及改进的多路回退策略。这些策略有助于降低回溯次数,尽早地发现信号冲突,识别冗余故障。     

测试生成算法

集成电路技术的迅速发展,测试生成变得越来越困难。往往测试代价比电路设计,生产代价还要高。扫描设计技术将时序电路的测试生成转换成组合电路来处理。组合电路的测试码生成就显得很重要了。D-算法第一次引入了多路径敏化的思想,因而是第一个完全的算法。但由于D-算法对故障校验电路处理所存在的缺陷,使得D-算法在测试码搜索过程中所存在的盲目性逐步表现得非常突出。PO-DEM算法第一次将测试生成问题归结为一个多维空间解的搜索问题。该算法采用隐枚举的方法来处理测试生成,并第一次引入了回退技术,使得测试码生成效率大大提高。FAN算法对PODEM算法作较大的改进。该算法引入了唯一敏化,唯一蕴含及多路回退等技术将测试码生成效率大大提高。不同于PODEM算法的是,FAN算法搜索测试码的回溯不是针对原始输入,而是对头线和扇出。SOCR-ATES算法在FAN算法的基础上,引入了全局蕴含的思想及一系列改进的唯一敏化和改进的多路回退策略。SOCRATES进而将全局蕴含及唯一敏化扩展到动态的策略,进一步提高了测试码生成效率。EST算法第一次提出了测试码搜索状态的概念,并采用E-前沿来描述测试码搜索的不同状态。通过引入状态等价的概念,大大缩小了测试码搜索空间。DST算法将测试码搜索空间的状态等价概念扩展到状态控制的概念,在EST算法的基础上,进一步大大缩小了搜索空间。     

CMOS单元版图生成算法综述

基于库单元的ASIC设计方法对单元版图自动生成工具提出了很高的要求。CMOS单元版图生成可分成MOS管布局、单元内布线和版图压缩三步。文章从不同的单元版图布图样式出发,综述布局、布线及压缩算法的发展现状,具体介绍几个单元版图生成系统,最后指出了该研究领域存在的问题。     

时序电路的模糊化测试生成算法

文章提出的模糊化的时序电路测试生成算法不明确指定故障点的故障值，它将故障值模糊化，并以符号表示。本算法第一阶段通过计算状态线和原始输出端的故障值来寻找测试矢量，通过计算故障点的正常值来 寻找测试矢量对应的故障类型；第二阶段用故障点的正常值作为约束条件计算故障点的另一个测试矢量。与传统的算法不同，它不需要回退和传播的过程。实验结果表明本算法具有较高的故障覆盖率和较少的测试时间。     

数字电路测试生成的基本算法

计算机辅助测试（CAT）工具有助于数字电路测试的自动化，这主要是由于使用了有效的算法和相应的软件结构。文章主要介绍了测试生成领域有重大影响的基本要领和算法。     

基于蚂蚁算法和遗传算法的时序电路测试生成

为提高时序电路的测试生成效率,该文提出一种新的基于蚂蚁算法和遗传算法的时序电路测试矢量生成算法.针对国际标准时序电路的实验结果表明,该交叉算法既充分发挥了两种算法的优点,又克服了各自的缺点,与其它同类测试生成算法相比,获得了较好的故障覆盖率和测试集.说明采用蚂蚁算法和遗传算法的交叉算法是成功的.     

基于混沌搜索的组合电路测试生成算法

基于组合电路测试生成的离散Hopfield神经网络模型，将混沌搜索与Hopfield网络的梯度算法相结合，利用混沌搜索的内随机性及遍历性来克服梯度算法易于陷于局部极小的缺点，形成一种具有全局搜索能力的测试生成有效算法。该算法综合了随机性和确定性算法的优点，其性能优于一般的随机性算法。实验结果验证了该测试生成算法的有效性。     

CMOS单元版图生成中的晶体管布局算法

本文提出了一个基于模拟退火技术的CMOS标准(库)单元版图生成中的单元内晶体管布局算法，在满足高度约束的前提下同时优化单元版图的面积和时延，可处理不局限于静态串并联结构的电路，考虑大尺寸管子折叠等因素，最终生成二维样式标准单元版图。     

神经网络在组合电路故障模拟测试生成算法中的应用

本文在基于故障模拟的测试生成算法基础上,提出了一种初始测试矢量的生成方法,即采用神经元网络模型来生成初始矢量,既避免了随机生成初始矢量的盲目性,又避免了确定性算法使用回溯所带来的大运算量。试验结果证明这种方法是有效的。     

基于遗传算法的自适应测试生成

文章介绍了一种基于遗传算法的自适应测试生成方法，首先讨论了用遗传算法进行测试生成时构造评价函数的一些方法，然后应用组合电路的Hopfield神经网络模型，提出了基于遗传算法的自适应测试生成算法，该方法不同于传统的方法，它不需要故障传播传播、回退等过程，实验结果表明了本算法的可行性。     

基于遗传算法的数字电路测试生成方法

本文提出了一种基于遗传算法的数字电路测试图形生成方法，首先把被测电路的门级描述转化为易于计算的非线性网络，然后用遗传算法找到网络能量函数的最优解，从而得到被测电路的测试集．这种方法对可测故障都能生成测试，能方便地产生多故障的测试图形，同时具有较好的并行性，易于在多处理机上实现．     

Test Generation for Mixed-Signal Devices Using Signal Flow Graphs

We describe a new reverse simulation approach to analog and mixed-signal circuit test generation that parallels digital test generation. We invert the analog circuit signal flow graph, reverse simulate it with good and bad machine outputs, and obtain test waveforms and component tolerances, given circuit output tolerances specified by the functional test needs of the designer. The inverted graph allows backtracing to justify analog outputs with analog input sinusoids. Mixed-signal circuits can be tested using this approach, and we present test generation results for two mixed-signal circuits and four analog circuits, one being a multiple-input, multiple-output circuit. This analog backtrace method can generate tests for second-order analog circuits and certain non-linear circuits. These cannot be handled by existing methods, which lack a fault model and a backtrace method. Our proposed method also defines the necessary tolerances on circuit structural components, in order to keep the output circuit signal within the envelope specified by the designer. This avoids the problem of overspecifying analog circuit component tolerances, and reduces cost. We prove that our parametric fault tests also detect all catastrophic faults. Unlike prior methods, ours is a structural, rather than functional, analog test generation method.     

An Improved Genetic Algorithm for Test Cases Generation Oriented Paths

This paper discusses a method that can automatically generate test cases for selected paths using a special genetic algorithm. The special algorithm is called Queen-bee evolutionary genetic algorithm（QBEA）. In this algorithm, sequences of operators iteratively executes for test cases to evolve to target paths. The best chromosome called queen among the current population is crossover with drones selected according to a certain crossover prob- ability, which enhances the exploitation of searching global optimum. A comparative experiment results prove that the proposed method is actually a great improvement in opti- mization efficiency and optimization effect.     

用线性码构造伪穷尽测试集

在本文中，我们给出了一种用线性码构造伪穷尽测试集的测试码生成方法。这种方法在减小测试时间方面较以往的方法又进了一步。实验结果表明这种方法是完全可取的。     

组卷算法研究与实现

研究并实现了一种符合实际需求的组卷算法,它是题库建设及计算机自动生成考核试卷的核心技术。该组卷算法的目的是保证自动组卷的快速、合理并符合试卷基本要求和教师专门要求,采用的方法是反复随机筛选法,搜索本卷未抽取的试题,逐一用多个要求的条件判断该题是否符合要求,每搜索一次后若题量未够,则进行下一次搜索并放松条件（即去掉一个判断）。在对多门课程题库的多次组卷结果的分析后,该算法能很好地满足在知识点上分布平均,最近曝光度低、难度符合要求,一次抽出的各套试卷之间重复题少。该算法已应用于在电大多门课程的考核出题中,结果表明其减轻了教师的大量重复性工作,而且能保证考核的有效性和合理性。     

Functional Fault Equivalence and Diagnostic Test Generation in Combinational Logic Circuits Using Conventional ATPG

Fault equivalence is an essential concept in digital design with significance in fault diagnosis, diagnostic test generation, testability analysis and logic synthesis. In this paper, an efficient algorithm to check whether two faults are equivalent is presented. If they are not equivalent, the algorithm returns a test vector that distinguishes them. The proposed approach is complete since for every pair of faults it either proves equivalence or it returns a distinguishing vector. The advantage of the approach lies in its practicality since it uses conventional ATPG and it automatically benefits from advances in the field. Experiments on ISCAS’85 and full-scan ISCAS’89 circuits demonstrate the competitiveness of the method and measure the performance of simulation for fault equivalence.