Search

In this paper the detection of permanent faults in sequential circuits by random testing is analyzed utilizing the circuit partitioning approach together with a continuous parameter Markov model. Given a large sequential circuit, it is partitioned into several smaller partitions using either series or parallel decomposition. For each partition with certain stuck faults specified, the original state table and its error version are derived from an analysis of the partition under fault-free and faulty conditions, respectively. A random testing strategy that uses a three-state Markov model is used for detecting permanent stuck faults. Experimentation on various sequential circuits has shown that a significant saving in testing or test generation time can be achieved if we can partition the circuit and then test each of its components as opposed to testing the circuit in its original form. >

General-purpose distributed systems comprised of computing nodes with different characteristics and connected by high-speed communication networks are very popular these days. The development of a dependable distributed system, however, necessitates the use of various techniques including fault tolerance to avert occurrences of failures or system malfunction. The ad hoc techniques of adding redundancy to improve reliability are not always suitable in these circumstances because of excessive design cost. Redundancies have to be allocated at various hardware and software levels in order to optimize their utilization in the system. This paper considers the design of general-purpose fault-tolerant distributed systems based on a layered approach. The benefits of the layered approach in the process of allocation of redundancy and fault tolerance at various system levels are presented and analyzed in the paper.

The authors propose a syndrome signature particularly well suited for exhaustive testing of VLSI circuits. Given an n-input combinational circuit, a syndrome signature is defined by an (n+1)-element vector consisting of the primary syndrome of the function as originally defined by J. Savir (1980) and n other subsyndromes corresponding to the subfunctions obtained by setting each of the n input variables to 0. A multiple-output syndrome signature generation is also discussed that preserves all the desirable properties of the single-output response analyzers. The signature generators can be easily implemented using the current VLSI technology. >

In this paper we describe a space compression technique for realizing ultimate compression in multiple-input signature registers (MISRs), commonly used in built-in self-test (BIST) applications. The technique uses nonexhaustive test sets and is based on the inherent properties of the output sequences of a circuit under test (CUT) and the failure probabilities. The proposed technique guarantees a very high fault coverage for single stuck-line faults, with low CPU simulation time, and acceptable hardware overhead. Extensive simulation runs on ISCAS 85 combinational benchmark circuits with ATALANTA and COMPACTEST confirm the novelty of the suggested approach under conditions of both stochastic independence and dependence of single and double line errors.

In this paper, we propose a space compression technique for digital circuits for minimizing the storage for the circuits under test while maintaining the fault coverage information. In this technique, a compaction tree is generated based on the circuit under test. The detectable error probability is calculated by using the Boolean Difference Method. The output modification is employed to minimize the number of faulty output data patterns which have the same compressed form as the fault-free patterns. The compressed outputs are then fed into a syndrome counter to derive the signature for the circuit. Simulations were performed on known combinational circuits and the results indicate that the loss in fault coverage caused by compression is in the range of 0-10% which is rather small.

This paper suggests a novel approach to designing zero-aliasing space compactors utilizing switching theory concepts of Hamming distance, sequence weights, cover table and frequency ordering, together with concept of Nth order missed error probability estimates under stochastic dependence of line errors for detectable single stuck line faults of the CUT. The advantages of aliasing-free space compaction over earlier techniques are evidently clear-zero-aliasing is achieved without any modifications of the CUT, the area overhead and signal propagation delay are relatively less compared to conventional parity tree linear compactors, and the approach used works equally well with both deterministic and pseudorandom test sets.

In this paper, we propose a new transparent built-in self-test (TBIST) method to test multiple embedded memory arrays with various sizes in parallel. First, a new transparent test interface is designed to perform testing in the normal mode and to cope with nested interrupts in a realtime manner. The circular scan test interface facilitates the processes of both test pattern generation and signature analysis. By tolerating redundant read/write/shift operations, we develop a new march algorithm called TRSMarch to achieve the goals of low hardware overhead, short test time, and high fault coverage.

We present novel test set encoding and pattern decompression methods for core-based systems. These are based on the use of twisted-ring counters and offer a number of important advantages-significant test compression (over 10/spl times/ in many cases), less tester memory and reduced testing time, the ability to use a slow tester without compromising test quality or testing time, and no performance degradation for the core render test. Surprisingly, the encoded test sets obtained from partially-specified test sets (test cubes) are often smaller than the compacted test sets generated by automatic test pattern generation programs. Moreover, a large number of patterns are applied test-per-clock to cores, thereby increasing the likelihood of detecting non-modelled faults. Experimental results for the ISCAS benchmark circuits demonstrate that the proposed test architecture offers an attractive solution to the problem of achieving high test quality and low testing time with relatively slower, less expensive testers.

It was recently suggested by Jone and Das that given a multiple-output combinational circuit, a parity bit signature for exhaustive testing of VLSI circuits can be generated by first EXORing all the outputs to produce a new output function and then feeding this resulting function to a single-output parity bit signature generator. Based on the aforesaid concepts of Jone and Das, this paper proposes a multiple-output parity bit signature for built-in self-testing of VLSI circuits using nonexhaustive or compact test sets. The feasibility of the developed approach is demonstrated by extensive simulation experiments on ISCAS 85 combinational benchmark circuits using simulation programs FSIM, ATALANTA, and COMPACTEST, showing a high fault coverage for single stuck-line faults, with low CPU simulation time, and acceptable area overhead.

Extrapolating the von Neuman's (binary) random-pulse machine concept, the paper discusses the generalized (multi-bit) random-data concept and shows how it can be used for a modular design of robust instrumentation for statistical signal parameter and, especially, of hardware neural networks.

This paper suggests a novel approach to designing aliasing free space compactors with maximal compaction ratio utilizing concepts of strong and weak compatibilities of response data outputs together with conventional switching theory concepts of cover table and frequency ordering for detectable single stuck line faults of the circuit under test (CUT), based on the assumption of generalized sequence mergeability. The advantages of aliasing free space compaction as developed in the paper over earlier techniques are obvious since zero aliasing is achieved here without any modifications of the CUT, while the area overhead and signal propagation delay are relatively less compared to conventional parity tree linear compactors. The approach used works equally well with both deterministic compacted tests and pseudorandom test sets.

In view of the recent paradigm shift from system-on-board to designs embracing embedded cores-based system-on-chips (SOCs), the complexity of digital circuits has enormously increased. This growing complexity has resulted in a huge challenge in developing their appropriate and efficient fault testing environment. Despite significant efforts directed toward implementing effective testing strategies of very large scale integrated circuit chips with reasonable cost, new frontiers emerged with advances in technology. The subject paper endeavors to develop method to test verify circuit architecture under hardware software co-design environment, targeting specifically embedded cores-based SOCs. The concept of design-for-testability is utilized in the paper together with ModelSim simulation and verification tool to test synthesize the entire design. Some simulation results on the International Symposium on Circuits and Systems (ISCAS) 85 combinational and ISCAS 89 full-scan sequential benchmark circuits are also included with a comparison of the results with some earlier works.

Usage of Automatic Speech Recognition (ASR) systems is increasing day-by-day for voice centric applications in mobile handheld and Voice over Internet Protocol (VoIP) devices. The necessity is also increasing to find out the ASR performance under different network impediments. Among them, speech and audio coding standards is the one, which affects the ASR performance greatly, when, using them with different sampling and bit rates in the practical systems. Another common impediment which influences the ASR accuracy is the bit errors in the wireless networks and packet drop conditions in the VoIP networks. ASR performance with some of the speech coding standards under noise conditions for the wireless networks is reported in the literature. However, each study is reporting the ASR performance for few narrowband codecs with different speech databases and different ASR toolkits like RAPHEL, HTK, SPHINX, etc. In this paper, the analysis on ASR performance while using both narrowband and wideband speech...

The design of space-efficient support hardware for built-in self-testing is of immense significance in the synthesis of present day very large-scale integration circuits and systems, particularly in the context of design paradigm shift from system-on-board to system-on-chip (SOC). The authors revisit the general problem of designing zero-aliasing (or aliasing-free) space compression hardware in relation to embedded cores-based SOC for single stuck-line faults in particular, extending the well-known concepts of conventional switching theory and of incompatibility relation to generate maximal compatibility classes utilising graph theory concepts, based on optimal generalised sequence mergeability, as developed by them in earlier works. The authors briefly present the mathematical basis of selection criteria for merger of an optimal number of outputs of the module under test for realising maximum compaction ratio in the design, along with extensive simulation results on ISCAS 85 combinational and ISCAS 89 full-scan sequential benchmark circuits, with simulation programs ATALANTA, FSIM and COMPACTEST.

On modifying a given sequential machien through augmentation of extra inputs and extra outputs, efficient techniques are developed in the present paper for its fault diagnosis and for the design of checking sequences, taking into consideration the case where faults may cause an increase in the number of states of the machine. Improved bounds on the lengths of checking sequences are also established.

For large combinational networks, the problem of fault detection and location is of great importance. Deterministic methods available for this purpose are rather expensive because of the amount of computation and storage required to generate possible test sets, particularly in large circuits. Probabilistic methods for fault detection and location can overcome some of the disadvantages inherent in the deterministic methods. In this paper, the applicability of random test generation for fault

This paper develops a matrix approach to the solution of the measurement and control problems in synchronous sequential machines. The control problem in sequential machines is concerned with finding input sequences that take a given machine from a known initial state to a predesignated terminal state. There may be many different measurement problems of interest in sequential machines. One important measurement problem is the identification of the unknown initial state of the machine, called the initial-state identification problem or diagnosing problem; another important measurement problem is the identification of the terminal state of the machine, known as the terminal-state identification problem or homing problem, of which a special case is the synchronizing problem. These measurement problems may be solved by applying predetermined input sequences to the machine and noting the resulting output sequences. The conventional approach to the solution of these measurement and control problems is to make use of the information contained in the transition table of the machine in conjunction with its response tree, which is basically an exhaustive tree search process. In the present paper, instead of using the transition table and the corresponding response tree, we use only the transition matrix representation of the machine and its higher order forms to solve the aforementioned problems. The suggested approach is very systematic and completely algorithmic, and thus lends itself to easy computer implementation.

This paper develops an algorithm for finding all maximal complete subgraphs or cliques of an undirected graph. The algorithm is simple, and is based on a refinement of the technique of successive splitting described by Paull and Unger in the determination of maximal compatibles of states in the context of minimization of incomplete sequential machines. The proposed algorithm tends to reduce computation in generating the subgraphs for problems most generally encountered, particularly in relation to the applicability in sequential switching theory.

Given a particular ROM specification, and word dimension, control memory can be reduced by reducing the bit dimension, at the expense of flexibility. This problem of bit dimension reduction of control memory in a microprogrammed digital computer was first considered by Schwartz. The problem was later reformulated by Grasselli and Montanari in the framework of switching theory, reducing the main minimization problem to a set covering problem of the prime implicant type. Starting with the same basic formulation as of Grasselli and Montanari, Das et al. subsequently developed an approach that helps to arrive at a solution with less computation in general. The present paper investigates the problem of bit dimension reduction in a control memory specification based on the switching theory formulation of Das et al. , and develops a simplified methodology for a good “engineering reduction”, or, if necessary, to arrive at a minimal solution.

In a recent paper an algorithm for generating maximal minimally strongly connected subgraphs or cliques in undirected graphs has been proposed by Das et al This algorithm is based on a refinement of the technique of successive splitting described by Pauli and Unger in the determination of maximal compatibles of states in the context of minimization of incomplete sequential machines. The present paper discusses the implementation of the above subgraph generation algorithm in a Cyber System 172 using FORTRAN IV, and attempts to evaluate its performance characteristics as well as complexity for both small and large graphs, with particular reference to cluster analysis.

In this paper multiple fault detection in sequential circuits by random testing is discussed. The concept of modified transition diagram initially proposed by Sheng and Das in the context of sequential machine identification is used as the model, and based on this, the upper and lower bounds on the length of the random test-input pattern to detect all faults in sequential circuits with a specified confidence degree are derived, assuming mat the faults result in at least one error transition of the circuits. The modified transition matrix and its higher-order forms are utilized to find the number of required test-input patterns to attain a sufficiently good confidence degree.

An undirected or a symmetric graph consists of a set of nodes and a set of nonoriented edges connecting between pairs of nodes. In widely differing disciplines of science and engineering, symmetric graphs find important uses. In many of these application areas, an often encountered problem is that of finding all the maximal complete subgraphs of a symmetric graph. In this paper, borrowing the concept of strong connectedness in a nonsymmetric graph, the idea of minimally strongly connected (MSC) and maximal minimally strongly connected (MMSC) subgraphs in a symmetric graph is introduced. The MMSC subgraphs play a kind of role identical to that played by maximal complete subgraphs in symmetric graphs. Many important properties of MMSC subgraphs are discussed in the paper, and an explicit, computer-oriented algorithm is developed for finding all the MMSC subgraphs, given an undirected graph.

Based on the concept of entropy, the present paper develops an approach for finding the state identification sequences in sequential machines. An algorithm called first-order optimal algorithm is developed in the paper, which is applied to the transition table representation of the machine in finding the different state identification sequences, following an approach developed recently by Das et al. A good criterion is provided for candidate selection in the process of expansion along the table entries, which eliminates the necessity of expanding along all entries, thereby considerably reducing the computational needs. The storage requirements in the actual computer implementation are also substantially reduced.

The sequential machine is a well-established model for discrete information processing devices and systems. Under many circumstances, it is necessary to identify the state of the machine. Usually an appropriate sequence of input symbols is found and fed the machine; then, based on the corresponding output sequence, the state is determined. The major problem lies in finding the input sequence for the experiment. The usual approach to solve this problem is to use the response tree in conjunction with the transition table of the machine under consideration, then determine the growth and truncation of each branch according to a set of rules which necessitates comparison with each existing node. The answer is eventually reached through complying with certain rules. In general, the comparison process is slow and wasteful and there is no way of controlling computing space; also, there is no framework to implement fast solution techniques. In this paper, in order to solve the same problem, the concept of transition table is extended, operations are defined, and, in order to solve the problem quickly, some techniques and heuristics are introduced. This proposed approach can save a lot of computing time and memory space.

For a large combinational circuit, the problem of multiple fault detection and location is of great importance in the sense that, by such detection and location, we may find some fault-free sensitized paths between the primary inputs and some embedded points so that the signal values on these embedded points can be controlled through those paths. Furthermore, for VLSI chips, if some multiple faults frequently occur in certain chip area, fault location may provide some useful insight for redesigning that part of the chip so as to eliminate those multiple faults. In the present paper we develop an approach to multiple fault location which is adaptive scheduled and applicable to large combinational circuits. It is well known that unlike fault detection, adaptive scheduled fault location, in general, yields a shorter experiment. The relative advantages of the suggested approach in the context of some of the existing approaches to the solution of the problem are also discussed.

This paper considers the general problem of designing and analyzing efficient space compression techniques for built-in self-testing of VLSI circuits using compact test sets. The techniques are based on identifying certain inherent properties of the test output responses of the CUT and the knowledge of failure probabilities. The generalized mergeability criteria of output sequences are developed utilizing the concepts of Hamming distance, sequence weights, cover table and frequency ordering for an arbitrary number of outputs and the effect of failure probabilities on the mergeability criteria is analyzed as well. The techniques proposed achieve a very high fault coverage for single stuck-line faults, with low CPU simulation time, and acceptable hardware overhead, as evident from extensive simulation results on ISCAS 85 combinational benchmark circuits, under conditions of both stochastic independence and dependence of single and multiple line errors.

Recently, in connection with the measurement and control of synchronous sequential machines, Das et al. proposed an approach to the solution of the problems using the transition matrix representation of the machine and its higher-order forms. In the proposed approach, however, the authors restricted themselves to only simple and preset experiments. Generally speaking, a simple preset experiment is rather easy to implement, though it suffers from the disadvantage that it tends to be lengthy, and sometimes does not provide the experimenter with the desired information. The letter develops a new approach to the solution of the initial state identification problem or diagnosing problem, which happens to be an important measurement problem in sequential machines through multiple preset experimentation, using the transition-matrix representation of the machine and other related concepts as provided in the paper by Das et al. The present approach, like the one suggested before, is also very systematic and completely algorithmic, and thus lends itself to easy computer implementation.

In a recent paper, Fujiwara et al. presented an efficient procedure for designing checking experiments for sequential machines. In this procedure any arbitrary sequential machine is augmented to an easily testable machine by adding only two special input symbols to the original machine. An easily testable machine is defined by the authors as a reduced and strongly connected machine which possesses a distinguishing sequence as well as a synchronising sequence of length [log2 q], and a transfer sequence with a length that is at most [log2 q] to take the machine from a specific state S1, to a state St for all i, where q is the number of machine states, and [r] denotes the smallest integer greater than or equal to r. For a q-state, p-input symbol easily testable machine, the authors' procedure provides an upper bound on the length of the checking experiment that approximately equals pq[log2 q]. Furthermore, the entire checking experiment happens to be preset. This letter reports an extension of the aforementioned work of Fujiwara et al. In the procedure developed through this extension, any arbitrary sequential machine is augmented to an easily testable machine, by adding not two special input symbols alone, but simultaneously adding [log2 q] output terminals to the original machine. This modification gives a reduced upper bound on the lengths of the checking experiments, and also permits coverage of fault types that may cause an increase in the number of machine states.

This letter develops an approach for fault detection and checking sequence design of sequential machines based on the principle of machine modification through augmentation of extra input and extra outputs, taking into consideration the case where faults occurring in a machine may cause an increase in its number of states.