A cubical logic circuit modelling for reliability studies

A deeper insight into the problem of reliability analysis for combinational logic circuits is presented. Reliability is defined as the probability that the logic circuit correctly processes a given set of inputs. While the straightforward approach to this evaluation requires a formidable amount of computations, the presented approach is fast, easy to implement, memory efficient and applicable to circuits of any size and complexity. This is due to a new concept for logic circuit modelling, which allows the covering of all possible faults in a circuit by a relatively small number of sets of logically equivalent faults.For modelling purposes the excitations of inputs and the states of terminals in logic gates are presented in the form of a state vector. The logically equivalent state vectors are merged to form highest-order cubes which are mapped onto a gate equivalent graph (GEG). According to the connections among gates in the logic circuit this graphical model is extended to the circuit equivalent graph (CEG), which comprises the highest-order cubes for a circuit in the form of appropriate subgraphs, the so called state graphs (SGs).     

Determination of combinational logic circuit reliability through generation of fault diagnosis tests

This paper investigates the relationships between a given set of excitation vectors and the test sets for faults occuring in combinational circuits, in order to obtain new conditions for determining the redundant cubes of terminal states. The analysis presented is concluded with two new algorithms for the evaluation of combinational logic circuit reliability.     

A hierarchical test generation methodology for digital circuits

A new hierarchical modeling and test generation technique for digital circuits is presented. First, a high-level circuit model and a bus fault model are introduced—these generalize the classical gate-level circuit model and the single-stuck-line (SSL) fault model. Faults are represented by vectors allowing many faults to be implicitly tested in parallel. This is illustrated in detail for the special case of array circuits using a new high-level representation, called the modified pseudo-sequential model, which allows simultaneous test generation for faults on individual lines of a multiline bus. A test generation algorithm called VPODEM is then developed to generate tests for bus faults in high-level models of arbitrary combinational circuits. VPODEM reduces to standard PODEM if gate-level circuit and fault models are used. This method can be used to generate tests for general circuits in a hierarchical fashion, with both high- and low-level fault types, yielding 100 percent SSL fault coverage with significantly fewer test patterns and less test generation effort than conventional one-level approaches. Experimental results are presented for representative circuits to compare VPODEM to standard PODEM and to random test generation techniques, demonstrating the advantages of the proposed hierarchical approach.     

基于概率转移矩阵的时序电路可靠度估计方法

传统的概率转移矩阵(Probabilistic Transfer Matrix,PTM)方法是一种能够比较精确地估计软差错对门级电路可靠度影响的方法,但现有的方法只适用于组合逻辑电路的可靠度估计.本文提出基于PTM的时序电路可靠度估计方法(reliability estimation of Sequential circuits based on PTM,S-PTM),先把待评估时序电路划分为输出逻辑模块和次态逻辑模块,然后用本文提出的时序电路PIM计算模型得到电路的PIM,最后根据输入信号的概率分布计算出时序电路的可靠度.用ISCAS 89基准电路为对象进行实验和验证,实验表明所提方法是准确和合理的.     

Fast test generation and partial testing for combinational logic circuits

A simple, yet effective fast test generation algorithm by using the real value boolean difference is given for combinational logic circuits along with a short review of several fast test generation algorithms. Because no recursive operation is involved, it can be carried out as a parallel algorithm. In the second part of this paper, the concept of the partial testing is discussed. A new partial testing method, weighted point testing, is presented in this paper. Every line or node in the combinational logic circuit has a weight assigned to it. The weight at a point is determined by several factors, such as the fault occurrence found by experience or prior-knowledges, the number of fan-in or fan-out at that point, and the depth of the point in the circuit. Only those points with relatively high weights are considered in the test generation and testing. Because testing is more effectively done and directed to the point, the test coverage is higher.     

判奇电路实现方法探讨

以三输入判奇电路设计为例,通过对其输出函数表达式的形式变换,分别采用多种门电路及译码器、数据选择器等74系列器件进行电路设计,给出了7种电路实现形式,并分析了各种电路实现的优缺点。此例说明了组合逻辑电路设计的灵活性及电路实现的多样性。所采用的设计方法对其他组合逻辑电路设计具有一定的启发与指导意义。     

The probability of error detection in sequential circuits using random test vectors

In this article a method is presented for evaluating the probability of detecting (PD) a single stuck-fault in a sequential circuit as a function of the number of random input test vectors. A discrete parameter Markov-model is used in the analysis to obtain closed-form expressions for PD. The circuit is partitioned into three parts, the input and output combinational logic and the memory. The analysis is based upon the stationary-state transition matrix associated with a circuit, and the probability that a fault in one of the partitions produces an error at the output of that partition when a random input vector is applied. Results are presented to show how this problem can be reduced to that of testing an equivalent combinational circuit.     

Reconvergent fanout analysis and fault simulation complexity of combinational circuits

The detectability of reconvergent fanout stem faults in a combinational logic circuit can be determined by explicitly simulating the faults within limited regions of the circuit. These regions are defined, and an estimate of the fault simulation complexity of the circuit is obtained. Results are presented for ten benchmark circuits.     

Modeling for bridging faults in nMOS combinational circuits

A transistor level model that fully describes the logical behavior of a circuit in the presence of bridging faults is presented for the nMOS combinational circuits. The proposed model is suitable for the circuits having static enhancement/depletion (E/D) load. Thus, the model can be applied to circuits like pseudo nMOS and CMOS non-threshold-logic (NTL). The model employs a logic transistor function (LTF) to examine the behavior of such circuits. The LTF model developed earlier for stuck faults in nMOS circuits is extended for bridging faults. Algorithms that were developed for the stuck faults in pseudo nMOS combinational circuits can be applied to generate the test vectors for bridging faults.     

A test methodology for finite state machines using partial scan design

This paper presents an efficient automatic test pattern generation technique for loop-free circuits. A partial scan technique is used to convert a sequential circuit (finite state machine) with arbitrary feedback paths into a pipelined circuit for testing. Test generation for these modified circuits can be performed with a modified combinational automatic test pattern generator (ATPG), which is much faster than a sequential ATPG. A combinational model is obtained by replacing all flipflops by buffers. It is shown that a test vector for a fault in this model obtained by a combinational test generator can be expanded into a sequence of identical vectors to detect the same fault in the original sequential circuit. This technique may abort a few faults which can then be resolved with a sequential ATPG. Experiments on the ISCAS89 circuits show that only 30% to 70% of flipflops require scanning in larger circuits and 96% to 100% fault coverage for almost all the circuits without resorting to a sequential ATPG.This research was sponsored by the Semiconductor Research Corporation, Contract 90-DP-142.     

一种新型二元判定图器件和电路

提出了一种基于二元判定图(BDD)原理的新型逻辑器件和电路．BDD器件以电流模式的开关电流存储器为基本单元，具有符合二元判定图的两向通路的特点．用这种器件按照BDD树形图可以构成任意形式的组合逻辑电路．给出了或门、异或门及四位加法器电路的例子，并使用HSPICE仿真器进行了仿真，验证了这种器件及其电路的正确性．     

Synthesis of multiple input-change hazard-free combinational switching circuits without feedback†

This paper deals with hazards on outputs of combinational circuits without feedback for multiple input changes. A procedure is given to decompose a Boolean function into a feedback free circuit. The procedure either gives a logic hazard-free circuit or shows that the Boolean function cannot be broken down into a feedback free circuit which is free of logic hazards for multiple input changes. The procedure proves that all multiple input change combinational circuits cannot be implemented without dynamic logic hazards with no internal feedback. The result is therefore considerably different than the single input change and multiple input change static logic hazard cases.     

A stuck fault model for dynamic CMOS combinational circuits

This paper utilizes the logic transistor function (LTF), that was devised to model the static CMOS combinational circuits at the transistor and logic level, to model the dynamic CMOS combinational circuits. The LTF is a Boolean representation of the circuit output in terms of its input variables and its transistor topology. The LTF is automatically generated using the path algebra technique. The faulty behavior of the circuit can be obtained from the fault-free LTF using a systematic procedure. The model assumes the following logic values (0, 1, I, M), where I, and M imply an indeterminate logical value, and a memory element, respectively. The model is found to be efficient in describing a cluster of dynamic CMOS circuits at both the fault-free and faulty modes of operation. Both single and multiple transistor stuck faults are precisely described using this model. The classical stuck-at and non classical stuck open and short faults are analyzed. A systematic procedure to produce the fault-free and faulty LTFs for different implementations of the dynamic CMOS combinational circuits is presented.     

Physical design of testable VLSI: techniques and experiments

It is shown that the layout of VLSI circuits can affect testability and in some cases reduce the number of faults likely in a design, easing test generation. A method for analyzing circuits at the symbolic layout level and enhancing testability using local transformations is presented. To demonstrate the application of the technique a set of CMOS standard cells was redesigned. The standard cells are used in the MIS synthesis system, allowing the designer to modify interactively designs to perform tradeoff analysis on testable designs. To show the usefulness of the technique, an experiment was performed: example circuits were synthesized, and test vectors were generated and then used in a transistor-level fault simulator. It was found that the modified designs have significantly higher fault coverage than unmodified designs. A strategy for the synthesis of easily testable combinational random logic circuits is presented     

Redundancies and don't cares in sequential logic synthesis

The relationships between redundant logic and don't care conditions in combinational circuits are well known. Redundancies in a combinational circuit can be explicitly identified using test generation algorithms or implicitly eliminated by specifying don't cares for each gate in the combinational network and minimizing the gates, subject to the don't care conditions.In this article, we explore the relationships between redundant logic and don't care conditions in sequential circuits. Stuck-at faults in a sequential circuit may be testable in the combinational sense, but may be redundant because they do not alter the terminal behavior of a nonscan sequential machine. These sequential redundancies result in a faulty State Transition Graph (STG) that is equivalent to the STG of the true machine.We present a classification of redundant faults in sequential circuits composed of single or interacting finite state machines. For each of the different classes of redundancies, we define don't care sets which if optimally exploited will result in the implicit elimination of any such redundancies in a given circuit. We present systematic methods for the exploitation of sequential don't cares that correspond to sequences of vectors that never appear in cascaded or interacting sequential circuits. Using these don't care sets in an optimal sequential synthesis procedure of state minimization, state assignment, and combinational logic optimization results in fully testable lumped or interacting finite state machines. We present experimental results which indicate that medium-sized irredundant sequential circuits can be synthesized with no area overhead and within reasonable CPU times by exploiting these don't cares.     

Fault detection in programmable logic arrays

When designing fault-tolerant systems including programmable logic arrays (PLAs), the various aspects of these circuits concerning fault diagnosis have to be taken into account. The peculiarity of these aspects, ranging from fault models to test generation algorithms and to self-checking structures, is due to the regularity of PLAs. The fault model generally accepted for PLAs is the crosspoint defect; it is employed by dedicated test generation algorithms, based on the fact that PLAs implement a two-level combinational function. The problem of accessing inputs and outputs of the PLA can be alleviated by augmenting the PLA itself so as to simplify the test vectors to be applied, making them function independent in the limit. A further step consists in the addition of the circuitry required to generate test vectors and to evaluate the answer, thus obtaining a built-in self-test (BIST) architecture. Finally, high reliability can be achieved with PLAs featuring concurrent error detection.     

Synthesis for logical initializability of synchronous finite-statemachines

Logical initializability is the property of a gate-level circuit whereby it can be driven to a unique start state when simulated by a three-valued (0, 1, X) simulator. In practice, commercial logic and fault simulators often require initialization under such a three-valued simulation model. In this paper, the first sound and systematic synthesis method is proposed to ensure the logical initializability of synchronous finite-state machines. The method includes both state assignment and combinational logic synthesis steps. It is shown that a previous approach to synthesis-for-initializability, which uses a constrained state assignment method, may produce uninitializable circuits. Here, a new state assignment method is proposed that is guaranteed correct. Furthermore, it is shown that combinational logic synthesis also has a direct impact on initializability; necessary and sufficient constraints on combinational logic synthesis are proposed to guarantee that the resulting gate-level circuits are logically initializable. The above two synthesis steps have been incorporated into a computer-aided design tool, SALSIFY, targeted to both two-level and multilevel implementations     

Method for evaluation of transient-fault detection techniques

This work introduces a simulation-based method for evaluating the efficiency of detection techniques in identifying transient faults provoked in combinational logic blocks. Typical fault profiles are simulated in campaigns of injections that reproduce output scenarios of fault-affected combinational circuits. Furthermore, a detection technique is proposed and compared to state-of-the-art strategies by using the method presented herein. Results show the capabilities of all studied techniques, providing a rank in terms of their efficiencies in detecting transient faults induced in combinational logic circuits, and analyzing the situations in which soft errors are produced in memory elements.     

BILCO: built in testing method for combinational logic circuits

The testing of digital logic circuits has become quite complex owing to miniaturisation and its associated increase in circuit function per unit area. Methods have been devised for testing ASIC products and, latterly, board level products. A new method (BILCO) is presented for probing asynchronous combinational logic circuits using a novel development of scan path principles