组合逻辑多故障诊断

通过对布尔差分法的剖析,得到了组合电路单固定故障测试生成的简化方法。该方法不必进行异或运算,只须求解恒等式就能得到组合逻辑电路的８测试矢量。多故障的测试码产生可以对高阶布差分经过变换,转化为一阶布尔差分来处理,从而极大地减少了多故障测试生成的计算工作量。     

Theorems for Fault Collapsing in Combinational Circuits

This paper gives a mathematical approach to fault collapsing based on the stuck-at fault model for combinational circuits. The mathematical structure we work within is a Boolean ring of Boolean functions of several variables. The goal of fault collapsing for a given circuit is to reduce the number of stuck-at faults to be considered in test generation and fault diagnosis. For this purpose we need rules that let us eliminate faults from the considered fault set. In this paper some earlier known rules are proved in the new context, and several new rules are presented and proved. The most important of the new theorems deal with the relationship between stuck-at faults on a fanout stem and the branches. The concept of monotony of Boolean functions appears to be important in most of these new rules. Editor: M. Hsiao Audhild Vaaje received the M.S. degree and the Ph.D. degree in mathematics from University of Oslo in 1971 and 1992, respectively. She is an associate professor of mathematics at Agder University College in Norway, where she has been employed since 1972. She has research interests in mathematics applied to fault detection in digital circuits.     

Model for Transient Fault Susceptibility of Combinational Circuits

Transient faults (TFs) are increasingly affecting microelectronic devices as their size decreases. During the design phase, the robustness of circuits for high reliability applications with respect to this kind of faults is generally validated through simulations. However, traditional electrical level simulators are too slow for the task of simulating the effects of TFs on large circuits. In this paper, we present a new model to estimate accurately the possible propagation of transient fault-due glitches through a CMOS combinational circuit. We will show how the proposed model can be applied in order to estimate the TF susceptibility of a circuit by simply considering the propagation delay of the datapath. Therefore, the proposed model is suitable to be used into a new simulation tool able to provide good accuracy, while significantly speeding up simulations, with respect to electrical level simulation. In particular, our model allows approximately 90% accuracy with respect to HSPICE simulations.     

One-Level Simplification Method for All-Optical Combinational Logic Circuits

We propose a novel one-level simplification method for all-optical combinational logic circuits. With the proposed method, an all-optical gray code to binary coded decimal converter is successfully developed for the first time by using conventional semiconductor optical amplifiers as building elements. In comparison to the construction algorithm based on the conventional two-level simplification method, a significant improvement is observed in the Q-factor.     

PIPBQ Effect Aware SER Analysis for Combinational Logic Circuits

Technology scaling results in the propagation-induced pulse broadening and quenching (PIPBQ) effect become more noticeable. In order to effectively evaluate the soft error rate for combinational logic circuits, a soft error rate analysis approach considering the PIPBQ effect is proposed. As different original pulse propagating through logic gate cells, pulse broadening and quenching are measured by HSPICE. After that, electrical effect look-up tables (EELUTs) for logic gate cells are created to evaluate the PIPBQ effect. Sensitized paths are accurately retrieved by the proposed re-convergence aware sensitized path search algorithm. Further, by propagating pulses on these paths to simulate fault injection, the PIPBQ effect on these paths can be quantified by EELUTs. As a result, the soft error rate of circuits can be effectively computed by the proposed technique. Simulation results verify the soft error rate improvement comparing with the PIPBQ-not-aware method.     

A New Design Method for Self-Checking Unidirectional Combinational Circuits

In this paper, a new method for the design of unidirectional combinational circuits is proposed. Carefully selected non-unidirectional gates of the original circuit are duplicated such that every single gate fault can only be propagated to the circuit outputs on paths with either an even or an odd number of inverters. Unlike previous methods, it is not necessary to localize all the inverters of the circuit at the primary inputs. The average area over head for the described method of circuit transformation is 16% of the original circuit, which is less than half of the area overhead of other known methods. The transformed circuits are monitored by Berger codes, or by the least significant two bits of a Berger code. All single stuck-at faults are detected by the method proposed.     

Synthesis and Optimization of Combinational Interface Circuits

We describe an algorithm for interface synthesis and optimization for embedded system components such as microprocessors, memory ASIC, and network subsystems. The algorithm accepts the timing characteristics of two chips as input, and generates a combinational interface circuitry to implement communication between them. The algorithm consists of two parts. In the first part, we determine the direct pin-to-pin connections employing a 0-1 ILP formulation to minimize wiring area and dynamic power consumption in the resulting interface circuit. In the second part, we use a novel encoding method to synthesize connections between chips which require additional gates in the interface circuit. Experiments show that our algorithm is very effective in practice.     

基于SAT的组合电路自动测试向量生成

实现了基于可满足性(SAT)求解的方法,以解决固定型和时延故障的自动测试向量生成问题.详细讨论了如何利用电路的拓扑结构以及从ATPG到合取范式(CNF)的编码方法.CNF被输入到一个高效的SAT求解器zchaff中求解.在ISCAS85测试实例中验证了该算法的有效性.     

Noise-Error Determination of Combinational Circuits by Walsh Functions

The stochastic behavior of digital combinational circuits is analyzed by the use of Walsh functions. An n-input Boolean function is represented as a Walsh series and the error caused by noise is measured in terms of a distance which is the fraction of the time that the system output due to noise-corrupted signal differs from that due to signal alone. It is shown that the error can be expressed as the sum of two parts: one part depends only on noise statistics, and the other on both signal and noise. Some interesting properties of both parts are discussed and typical examples are given.     

Design Error Diagnosis with Re-Synthesis in Combinational Circuits

A new approach is proposed for removing design errors from digital circuits, which does not use any error model. Based on a diagnostic pre-analysis of the circuit, a subcircuit suspected to be erroneous is extracted. Opposite to other known works, re-synthesis of the subcircuit need not be applied to the whole function of the erroneous internal signal in terms of primary inputs, it may stop at arbitrary nodes inside the circuit. As the subcircuits to be redesigned are kept as small as possible, the speed of the whole procedure of diagnosis and re-synthesis can be significantly increased. A formal algorithm is proposed for the whole procedure. Experimental data show the efficiency of the diagnostic pre-analysis.     

VSF:CMOS组合电路的静态功耗评估模型

为了解决利用晶体管级电路模拟分析CMOS电路静态功耗时模拟时间随电路规模增大迅速增加的问题,在分析晶体管堆叠效应对标准单元泄漏电流影响的基础上,定义了归一化堆叠系数和电路等效堆叠系数的概念,提出了基于电路有效堆叠系数的静态功耗评估模型.该模型可用于CMOS组合电路静态功耗估算和优化.实验结果表明使用该模型进行静态功耗估算时,不需要进行Hspice模拟.针对ISCAS85基准电路的静态功耗优化结果表明,利用该模型能够取得令人满意的静态功耗优化效果,优化速度大大提高.     

Why is Combinational ATPG Efficiently Solvable for Practical VLSI Circuits?

Empirical observation shows that practically encountered instances of combinational ATPG are efficiently solvable. However, it has been known for more than two decades that ATPG is an NP-complete problem (Ibarra and Sahni, IEEE Transactions on Computers, Vol. C-24, No. 3, pp. 242–249, March 1975). This work is one of the first attempts to reconcile these seemingly disparate results. We introduce the concept of cut-width of a circuit and characterize the complexity of ATPG in terms of this property. We introduce the class of log-bounded width circuits and prove that combinational ATPG is efficiently solvable on members of this class. The class of of log-bounded width circuits is shown to strictly subsume the class of k-bounded circuits introduced by Fujiwara (International Symposium on Fault-Tolerant Computing, June 1988, pp. 64–69). We provide empirical evidence which indicates that an interestingly large class of practical circuits is expected to have log-bounded width, which ensures efficient solution of ATPG on them.     

VSF:CMOS组合电路的静态功耗评估模型

为了解决利用晶体管级电路模拟分析CMOS电路静态功耗时模拟时间随电路规模增大迅速增加的问题,在分析晶体管堆叠效应对标准单元泄漏电流影响的基础上,定义了归一化堆叠系数和电路等效堆叠系数的概念,提出了基于电路有效堆叠系数的静态功耗评估模型.该模型可用于CMOS组合电路静态功耗估算和优化.实验结果表明使用该模型进行静态功耗估算时,不需要进行Hspice模拟.针对ISCAS85基准电路的静态功耗优化结果表明,利用该模型能够取得令人满意的静态功耗优化效果,优化速度大大提高.     

量子遗传算法在多输出Reed-Muller逻辑电路最佳极性搜索中的应用

量子遗传算法是一种融合量子计算和遗传算法优点的智能算法,常用于求解组合优化问题.本文给出多输出RM(Reed Muller)逻辑电路最佳极性搜索方案,将量子遗传算法应用到多输出固定极性RM电路逻辑优化中.针对量子遗传算法易陷入局部极值的缺陷,结合群体灾变思想,提出一种基于量子遗传算法的多输出RM逻辑电路最佳极性搜索算法.最后对多个大规模PLA格式基准电路测试表明：该算法与基于遗传算法的最佳极性搜索相比,在优化能力、寻优性能和收敛速度等方面都有不同程度的提高.     

Finding Multiple Equivalence-Preserving Transformations in Combinational Circuits through Incremental-SAT

This paper introduces an approach to effectively exploit incremental SAT in order to search for multiple equivalence-preserving transformations of combinational circuits. Typical applications, such as redundancy removal with observability and external care conditions, adequate abstractions and other optimizations used in a state-of-the-art SAT-based model checker, can reap benefits from the proposed strategies. Our techniques exploit SAT incrementality, by iteratively refining the set of candidate transformations with a counter-example driven analysis, until an unsatisfiable point is reached. The key point of our technique is the ability to address satisfiable instances first, where SAT solvers are generally much faster than with unsatisfiable runs. We also discuss partitioning and problem reduction issues, that are fundamental in order to provide a scalable approach. Experimental results show the effectiveness of the proposed strategies.     

异步组合电路网表优化的研究

根据异步组合电路的特点，本章在传统的工艺映射算法的分解和覆盖两个步骤之间引进了新的一步-“延时再优化”，采用NAND3-Rotation的方法实现，对分解后网表的平均延时进行优化.在标准测试电路上的测试结果表明引进延时再优化能给异步电路的平均延时带来6～25%的改进。     

多输出电路跳变次数(TC)测试算法

本文提出了一种多输出电路的改进TC测试法。该方法根据多输出电路的输入输出的函数关系把电路按输出分解，然后按照各个输出的相关输入，分别测试输出的响应，从而可以实现对多输出电路的测试，进而说明这种检测的完备性，进一步提出了一种加速测试的方法。     

基于翻转信息熵的组合逻辑电路功耗分析

基于信息熵的复杂度分析方法是在VLSI设计流程的高层次抽象阶段对组合逻辑电路功耗和面积进行分析估计的可行方法之一.本文通过提出新的利用翻转信息熵进行电路实现面积和功耗估计的理论方法,改善了面积和功耗估计精度.大量基于随机电路和BENCHMARK电路的实验结果表明,上述方法能够使面积和功耗估计的相对误差分别降低24.3% (从12.74%到9.65%)和15.4% (从13.67%到11.57%).     

基于切片分析的CMOS组合电路贝叶斯动态功耗模型

为改善周期精确级功耗分析的准确度和速度问题,使用多维特征参数建立贝叶斯推理的动态功耗模型.基于功耗分布与电路内部节点状态的分析,发现仅使用端口信息作为参数的不足.定义了门单元级数的计算和对应切片的概念,提出使用切片分析的技术提取电路内部关键层的翻转密度作为参数,与端口信息共同参与贝叶斯推理.基于ISCAS85基准电路的实验结果表明,该方法使原始模型的误差降低21.9%,均方差降低25.0%,同时保持了相对现有门级功耗分析700倍的加速比.     

基于分布估计算法的组合电路测试生成

基于遗传算法生成的测试矢量集的故障覆盖率要低于确定性方法．本文分析指出造成这种现象的一个可能原因在于，组合电路测试生成过程中存在高阶、长距离模式，从而导致遗传算法容易陷人局部极值或早熟收敛．为此，本文首次提出使用分布估计算法生成测试矢量．该方法使用联合概率分布捕捉电路主输人之间的关联性。从而避免了高阶、长距离模式对算法的影响，缓解了算法早熟收敛问题．针对ISCAS-85国际标准组合电路集的实验结果表明，该方法能够获得较高的故障覆盖率．