大型组合电路测试码的产生

本文讨论大型组合电路中固定型单故障测试码的产生方法。我们可以从建立和求解测试码方程的观点把一维路径敏化法、D-算法和布尔差分法等几种基于路径敏化概念的方法统一起来。随后我们引进跳变算子的概念,并且由此建立单路径敏化的充分必要条件和相应的测试码方程。这种单路径敏化法并不要求封锁其他有关的路径。这种方法差不多和一维路径敏化法一样简单,同时对扇出后又重新会聚的多路径情形也是适用的。对于从被测引线到电路输出端有m条不同路径的情形,这种方法最多只要计算m次就可以求得测试码,而不需要考虑所有2~m—1种不同的路径组合情形。在计算机中,这种方法可以和布尔差分法一样,用布尔表达式的运算来实现,也可以和D-算法一样,对一些表格和向量的加工来实现,或者可以兼取两者之长。最后用例子说明整个计算过程。     

多变元布尔差分及多通路敏化定理

迄今,对多扇出再聚合情况,缺少一个计算布尔差分的有效公式。布尔差分法作为故障诊断测试生成的算法的竞争能力因此受到很大的损害。 本文给出的多通路敏化定理是一个计算布尔差分的有效公式,能使布尔差分法变得效率既高又节省内存。     

基于函数分类和布隆过滤器的布尔匹配方法

在现场可编程门阵列的自动化综合流程中,布尔匹配是核心子问题之一。基于布隆过滤器的布尔匹配方法需要消耗大量存储空间并牺牲部分可实现函数的覆盖率。针对该问题,提出一种布尔匹配方法,给出布尔函数的规则表达形式,对布尔函数进行分类,并在布尔匹配的过程中进行动态学习。实验结果表明,通过对函数分类可以使布尔匹配库所需的存储空间降低96%,而动态学习策略可以使电路在逻辑再综合算法应用中额外节省13%的LUT数目。     

蚁群优化在组合电路测试生成中的应用

如何高效地解决数字电路测试生成问题是VLSI领域中的核心。通过对蚁群算法在不同类型的组合优化和搜索问题上的应用研究,基于组合电路测试的路径敏化方法,借助SAT确定性算法工具,提出了一个新的蚁群算法模型来解决组合电路测试生成问题,并通过实验验证其可行性。     

基于引力搜索的布尔函数生成算法

布尔函数是在密码学、纠错编码和扩频通信等领域有着广泛应用的密码函数,寻找性能优良的布尔函数一直是密码学领域的重要问题之一。基于引力搜索算法设计了一种搜索布尔函数的新算法。该算法模仿万有引力定律,以n维空间中的质量点表示布尔函数,以布尔函数的密码特性作为目标适应度函数进行搜索。实验结果表明,算法使用新设计的目标适应度函数可以直接生成具有1阶弹性、1阶扩散准则和高非线性度、高代数次数以及低自相关指标等多种密码学指标的平衡布尔函数,并且进一步给出了直接生成2输出平衡布尔函数的计算机搜索算法。     

基于BDD的组合电路等价性检验

本文分析了基于BDD的组合电路等价性检验；讨论了构造输出函数的二叉判定图BDD的不同方法，并分析了BDD间布尔操作的不同的算法的异同；然后给出了一种基于BDD的组合电路等价性检验方法。     

电路宽度制导的布尔推理

在基于逻辑电路的布尔推理过程中，经常用到二又判决图(BDD)与布尔可满足性(SAT)相结合的算法．由于电路宽度能很好地反映电路的复杂性，提出了一种基于电路宽度的启发式策略，根据电路宽度来实现SAT算法与BDD算法的交替．充分发挥两者的优势，不仅可以防止因构造BDD可能导致的内存爆炸，而且还能避免SAT算法可能遇到的超时现象．与以往同类策略相比，该启发式策略更节省计算资源，提高算法性能．针对组合电路的测试产生实验，证实了其在布尔推理中的效率．     

适用于扫描测试中的测试响应压缩电路设计

测试向量响应压缩电路分为组合压缩电路和时序压缩电路两种．提出一种新的时序压缩电路：锥一压缩器．由于该电路是单输出的,所以总能保证最大压缩率．根据扫描测试中故障出现的特点,通过引入等价概念和两条设计规则来保证该响应压缩电路能够避免2,3和任何奇数个错误位抵消的情况．这两条设计规则同样适用于处理测试响应中出现未知位的情况．提出的基于随机选取生成算法可以自动生成该压缩电路．最后用实验数据从性能和代价两方面分析了锥一压缩器的适用性．     

产生功能级数字电路测试码的一种算法——主路径敏化法

本文提出了产生数字电路测试码的一种算法——主路径敏化法。这种算法适用于以功能块为基本单元的组合电路和时序电路。这个算法吸收了布尔差分法和D-算法的优点,把这两种方法统一起来并作了改进。根据这个算法编制的程序在实际使用中取得了比较满意的结果。     

基于二分图完善匹配的布尔匹配算法

提出了一种改进的基于二分图完善匹配的布尔匹配算法。该算法通过把布尔变量之间的匹配问题转换为二分图的完善匹配问题,避免了原算法中因乘积项过多而导致计算时间过长的缺点。对MCNC标准测试电路的实验结果表明;与原算法相比,改进后的算法可以减少21％左右的计算时间。同时,文中提出了布尔变量强匹配的概念,它是对传统布尔匹配概念的引申。     

一个适于形式验证的ATPG引擎

自动测试产生(ATPG)不仅应用于芯片测试向量生成，也是芯片设计验证的重要引擎之一．提出了一种组合电路测试产生的代数方法，既可作为组合验证的ATPG引擎，又可用于通常的测试产生．该算法充分发挥了二叉判决图(BDD)及布尔可满足性(SAT)的优势，通过启发式策略实现SAT算法与BDD算法的交替，防止因构造BDD可能导致的内存爆炸，而且使用增量的可满足性算法，进一步提高了算法的效率．实验结果表明了该算法的可行性和有效性．     

Near-minimal test sets for the detection of single gate faults

A new algorithm is presented for the detection of single gate faults in combinational networks. A gate fault is any unknown transformation of the Boolean function realized by a particular gate or single-output subnetwork. Detection of such faults is accomplished by verifying the truth table of the correct gate function.The concept of real transform of a Boolean function is utilized to obtain in each iteration an optimal test, namely, a test that performs as much of the fault detection task as possible. The resulting test set is near-minimal and complete.The algorithm can handle multi-output networks, integrated network components and mixed (gate, stuck-at) fault models.     

A Complete Critical Path Algorithm for Test Generation of Combinational Circuits

It is known that critical path test generation method is not a complete algorithm for combinational circuits with reconvergent-fanout.In order to made it a complete algorithm,we put forward a reconvergent-fanoutoriented technique,the principal critical path algorithm,propagating the critical value back to primary inputs along a single path,the principal critical path,and allowing multiple path sensitization if needed.Relationship among test patterns is also discussed to accelerate test generation.     

Orthogonal Algorithm of Logic Probability and Syndrome-Testable Analysis

A new method,orthogonal algoritm,is presented to compute the logic probabilities(i.e.signal probabilities)accurately,The transfer properties of logic probabilities are studied first,which are useful for the calculation of logic probability of the circuit with random independent inputs.Then the orthogonal algoritm is described to compute the logic probability of Boolean function realized by a combinational circuit.This algorithm can make Boolean function “ORTHOGONAL”so that the logic probabilities can be easily calculated by summing up the logic probabilities of all orthogonal terms of the Booleam function.     

Complete test-set generation for bridging faults in combinational-logic circuits

The present paper describes some algorithms for generating complete test sets for bridging faults in combinational logic circuits. It is shown how the concept of Boolean difference, which is well understood in the case of stuck-type fault situations, can be employed to generate the complete test set for bridging faults in combinational networks. The cases of single bridging fault and multiple input bridging fault are dealt with. An algorithm is also described for generating the complete test set of a combinational logic circuit in which a single stuck-type fault occurs in the presence of a bridging fault.     

Design for Testability for Complete Test Coverage

Some design-for-testability techniques, such as level-sensitive scan design, scan path, and scan/set, reduce test pattern generation of sequential circuits to that of combinational circuits by enhancing the controllability and/or observability of all the memory elements. However, even for combinational circuits, 100 percent test coverage of large-scale circuits is generally very difficult to achieve. This article presents DFT methods aimed at achieving total coverage. Two methods are compared: One, based on testability analysis, involves the addition of test points to improve testability before test pattern generation. The other method employs a test pattern generation algorithm (the FAN algorithm). Results show that 100 percent coverage within the allowed limits is difficult with the former approach. The latter, however, enables us to generate a test pattern for any detectable fault within the allowed time limits, and 100 percent test coverage is possible.     

Computing with planar toppling domino arrangements

A method for implementing Boolean logic functions using arrangements of toppling dominoes is described. Logic functions are implemented using only lines of dominoes and fork junctions. Using a dual-rail representation for Boolean values, any desired combinational function can be implemented. Circuits constructed using this method have no timing or order constraints on their inputs and require no out-of-plane bridges for passing one line of dominoes over another. Since they are built using toppling dominoes, circuits can be used only once.     

下三角矩阵神经网络逻辑电路的设计

由于人工神经网络的卓越优点，为制造超高速，高可靠和可编程的数字集成电路提供了新途径，具有下三角形连接矩阵的Ｈｏｐｆｉｅｌｄ模型在同一输入下仅有唯一的平衡点。本文将讨论基于这种网络模型的组合逻辑电路的逻辑设计方法，以最小化神经元个数为目标的启发式优化算法及权电阻网络参数的计算方法。     

An Effective Test Generation Algorithm for Combinational Circuits

In this paper,an analysis of backtrack behavior in PODEM(the test generation algorithmfor combinational circuits presented by P.Goel)is given.It is pointed out that there are stillmany unnecessary backtracks in PODEM on some occasions.A new test generation algorithmnamed IPODEM is therefore proposed in this paper.IPODEM is an improvement over PODEMwith emphasis on backtrack of decision tree.A new backtrack approach is developed in thisalgorithm.It is shown that only O(j)of backtrack consumption is needed in IPODEMcompared with O(2~j)in PODEM on certain occasions.Experiments pointed out that theseoccasions appear in not small proportion.Several other techniques are applied in IPODEM toaccelerate test generation process in other aspects.Experimental results demonstrated thatIPODEM is faster than PODEM for both hard-testing and easy-testing single stuck fault,andthat the former has higher test coverage than the latter.