We propose a testable design method of level shifters inside a liquid crystal display driver IC. The design method enables us to detect open defects in level shifters by supply current testing that are difficult to be tested by voltage testing. Also, we show by circuit simulation that more resistive open defects may be detected by supply current testing than voltage testing, if the level shifter is designed by using the proposed DFT method.

High power dissipation can occur when the response to a test vector is captured by flip-flops in scan testing, resulting in excessive JR drop, which may cause significant capture-induced yield loss in the DSM era. This paper addresses this serious problem with a novel test generation method, featuring a unique algorithm that deterministically generates test cubes not only for fault detection but also for capture power reduction. Compared with previous methods that passively conduct X-filling for unspecified bits in test cubes generated only for fault detection, the new method achieves more capture power reduction with less test set inflation. Experimental results show its effectiveness.

Scan-based at-speed testing is a key technology to guarantee timing-related test quality in the deep submicron era. However, its applicability is being severely challenged since significant yield loss may occur from circuit malfunction due to excessive IR drop caused by high power dissipation when a test response is captured. This paper addresses this critical problem with a novel low-capture-power X-filling method of assigning 0's and 1's to unspecified (X) bits in a test cube obtained during ATPG. This method reduces the circuit switching activity in capture mode and can be easily incorporated into any test generation flow to achieve capture power reduction without any area, timing, or fault coverage impact. Test vectors generated with this practical method greatly improve the applicability of scan-based at-speed testing by reducing the risk of test yield loss.

Research on low-power scan testing has been focused on the shift mode, with little or no consideration given to the capture mode power. However, high switching activity when capturing a test response can cause excessive IR drop, resulting in significant yield loss. This paper addresses this problem with a novel low-capture-power X-filling method by assigning 0's and 1's to unspecified (X) bits in a test cube to reduce the switching activity in capture mode. This method can be easily incorporated into any test generation flow, where test cubes are obtained during ATPG or by X-bit identification. Experimental results show the effectiveness of this method in reducing capture power dissipation without any impact on area, timing, and fault coverage.

This work proposes a new per-test fault diagnosis method based on the X-fault model. The X-fault model represents all possible behaviors of a physical defect or defects in a gate and/or on its fanout branches by using different X symbols on the fanout branches. A novel technique is proposed for analyzing the relation between observed and simulated responses to extract diagnostic information and to score the results of diagnosis. Experimental results show the effectiveness of our method.

In this paper, an I/sub DDQ/ test time reduction method is proposed which is suitable for BIST approaches. Also, a BIST circuit for I/sub DDQ/ tests, based on the method, is proposed. The layout of a CMOS logic circuit having the BIST circuit is designed and the performance is evaluated by SPICE simulation. The results show us that I/sub DDQ/ test time can be reduced by using this test circuit.

This paper proposes an X-fault model for fault diagnosis of physical defects with unknown behaviors by using X symbols. An efficient X-fault simulation method and an efficient X-fault diagnostic reasoning method are presented. Based on these, an X-fault diagnosis method is described to improve the failure analysis for a wide range of physical defects in complex IC circuits.

In this paper, a new method for reducing scan shifts is presented. Scan design is one of the most popular design for test technologies for sequential circuits. However, it requires much test application time and test data when applied to circuits with many flip-flops. The new scan method utilizes two configurations of scan chains, a folding scan tree and a fully compatible scan tree. A test pattern including many don't care values is used to configure a fully compatible scan tree in order to reduce the scan shift without degrading fault coverage. And then a folding scan tree is configured to reduce the length of the scan chain and thus reduce the scan shift. Experimental results for benchmark circuits shows this scan method can reduce many scan shifts.

In recent years, domino logic has received much attention. But in the case of standard domino logic, only non-inverting gates are allowed. Then, clock-delayed (CD) domino logic, that realizes any logic gate, has been proposed. Moreover, the domino logic has another drawback in that it is very sensitive to noise induced by crosstalk. Therefore, we focus our attention on crosstalk faults in CD domino circuits. In order to realize an efficient fault simulation, in this paper we propose a new method of target fault reduction, considering conflicts of signal values in the circuit and dominance of faults. In addition, we introduce a faster fault simulation method, which uses only logic values without handling details of the timing events of circuits.

We consider the problem of testing of interconnect open defects in combinational circuits with large fanout nodes. We propose a gate level fault model for interconnect opens. The number of interconnect open faults using the proposed model can be very large, being exponential in the fanout size. We describe methods to effectively consider the very large numbers of open faults. These methods include techniques for implicit consideration of open faults, and the use of information about fanout branches driving each primary output to reduce the list of faults. We present experimental results to demonstrate that fault simulation and test generation for the modeled open faults can be carried out efficiently using these techniques.

With the movement into deep submicron (DSM) technology and GHz clock frequencies, signal integrity problems have become important. Signal integrity problems are induced by circuit noise such as crosstalk, power supply noise. substrate noise. In this paper, we consider crosstalk in such noise and propose a new built-in self-test method for faults induced by crosstalk, called crosstalk faults.

In this paper, a useful technique is proposed for realizing high speed IDDQ tests. By using the technique, load capacitors of the CMOS logic gates can be charged quickly, where the output logic level changes L to H by applying a test input vector to a circuit under test. The technique is applied to built-in I/sub DDQ/ sensor design and external I/sub DDQ/ sensor design. It is shown experimentally that high speed I/sub DDQ/ tests can be realized by using the technique.

Abstract| This paper surveys recent research related to IDDQ testing, particularly focuses on fault models and test generation methods.(1) The paper pro videsa taxonomy of fault models that hav e been studied in literature, and classi es these models into a small set of faults.(2) The paper describes ecient test generation methods and fault simulation methods.T est compaction methods, including reduction of the total number of test v ectors and selection of IDDQ measurement v ectors, are also described.

This paper presents an effective IDDQ sensor design implemented using a 0.35 /spl mu/m process. A straightforward feedback scheme minimizes the effect of process variations. Independent structures permit one to monitor the basic characteristics of the IDDQ sensor, i.e., resolution and speed, and to carry out a 20k-gate floppy-disk controller IDDQ test separately. Simulation and test results show accuracy better than /spl plusmn/10 /spl mu/A at 50 MHz in a 1 mA IDDQ measurement range.

Proposes a static test compaction method for sequential circuits with reset states under a single stuck-at fault assumption. The proposed method first finds unremovable vectors by fault-dropping fault simulation or by non-fault-dropping fault simulation. Next, a subset of test vectors other than unremovable vectors are replaced with a reset signal. Detection of faults detected by an original test sequence is guaranteed by logic simulation and fault simulation for test subsequences. Experimental results for benchmark circuits demonstrate the effectiveness of the proposed method.

This paper presents an efficient procedure to improve logic testing for bridging faults (BF) in CMOS circuits. A unified procedure is presented that extracts the test vector from transistor level networks, which will reduce the occurrence of intermediate voltage that leads to Byzantine General's problems and feedback oscillation. By using this procedure according to fault location, the fault coverage of logic testing will increase without using both simulation and a complex calculation for predicting bridging voltage or logic threshold of the driven gates.

I/sub DDQ/ testing is an effective method for bridging faults of CMOS circuits. Since the measurement of current in I/sub DDQ/ testing takes a long time, a short test sequence is strongly desirable for reducing test application time. In this paper we present a test compaction method for an I/sub DDQ/ test sequence using a reassignment method for all bridging faults in sequential circuits. Since a large memory space is required to treat all bridging faults, an effective fault list is required. We propose the test compaction method using an assignment list of signal values. The proposed method is realized with small size memory and runs fast for many large sequential circuits. Experimental results on the benchmark circuits show that it is effective in reducing test length for given weighted random sequences.

In this paper we propose a new method to detect resistive bridging faults by logic testing considering fault effects that depend on the gate threshold voltage and gate input vectors. First we show that some bridging faults can be missed to be detected by the traditional test generation method which generates O and 1 at the bridging signal lines, and then propose a novel method to detect resistive bridging faults by logic testing method, which is complete in the sense that the undetectable resistive bridging fault by this algorithm gives correct result in logical operation. A heuristic method using a random pattern has also been proposed for experimental purpose. In order to show the effectiveness of the proposed method some experimental results for benchmark circuits have been shown.

This paper presents fault simulation techniques for selecting a small number of IDDQ measurement vectors from a given test sequence while maintaining the original fault coverage. The proposed method covers a class of bridging faults and uses parallel fault simulation wherever possible. Experimental results are presented to demonstrate the effectiveness of the proposed method.

In IDDQ testing, it is important to reduce the number of time-consuming IDDQ measurements. Therefore, it is necessary to select a small number of IDDQ measurement vectors in a test sequence for a sequential circuit while fault coverage is nearly maximum. In this paper, we address the selection problem of measurement vectors by introducing a cost function which is defined by the number of measurement vectors and fault coverage. The proposed method for selecting measurement vectors optimizes the cost function so that high fault coverage is obtained by a small number of measurement vectors.

The resistance of a bridge fault is critical in determining whether the fault can be detected. In order to simulate the effects of a bridging fault it's necessary to determine the intermediate voltage of the shorted nodes and compared it to the logic threshold voltage of the driven gates. We present an algorithm, which can be used to overcome the Byzantine General's problem during the fault simulation and test pattern generation. The algorithm applies to very low bridging fault resistance, and modifies it to apply for different values of BF resistance. This algorithm applies to external and internal inter-gate bridging faults. Moreover, the algorithm is much faster than previous ones since no SPICE simulation is required. The accuracy is /spl plusmn/0.01 V compared with SPICE simulation in the interval of intermediate voltage.

In this paper, we focus on how the I/sub DDQ/ current value varies depending on the test vectors and the resistance of bridging faults. Detection of a large I/sub DDQ/ is easier than a small I/sub DDQ/ because the value of I/sub DDQ/ is normally of the order of microamperes. If suitable logic values are assigned to the faulty nodes, a small channel resistance will be obtained and then a large I/sub DDQ/ will flow. We have performed the simulation to show that the value of I/sub DDQ/ depends on the test vectors that applied to the faulty nodes for external and internal bridging nodes. As a result, I/sub DDQ/ at the low resistance-bridging fault increased bp 26%-36% for external bridging faults between different gates. For the internal bridging fault between any gates, the increased I/sub DDQ/ is 27%-159% for all resistive bridging faults.

This paper considers a new test generation scheme in which a limitation of the number of tests exists. Since, in this scheme, correct fault coverage cannot be calculated by the representative faults, we present a method for calculating the correct fault coverage by using the weighted fault list. And then we propose a selection-based test generation method which derives a limited number of tests with higher fault coverage. The experimental results for IDDQ testing shows that our test generation method can generate tests with fault coverage close to the maximum fault coverage.

A new high speed Built-In Current (BIC) sensor is proposed, which is applicable for I/sub DDQ/ tests of low power ICs. The layout of the sensor is designed with CMOS 1.2 /spl mu/m technology. By using this sensor, resistive bridging faults in a circuit, whose supply voltage is 3.3 V, can be detected at the test speed of 66.7 MHz.

One of the major unsolved and ignored but significant problems is the reduction of the long testing time for IDDQ testing of CMOS circuits. Since IDDQ must be observed after dynamic current disappears, testing time is much longer than logic testing. This paper presents a method to reduce the observation time for IDDQ testing. The proposed method is a static method which focuses on selection of vectors to be observed instead of removing vectors. Experimental results are presented to demonstrate the effectiveness of the proposed method.

The procedure used in static learning extracts implication relations of the logic circuit. The number of extracted implication relations depends on the order of signal lines processed. In this paper we propose an efficient method to extract implication relations by considering the order of signal lines to be processed. Experimental results show that the proposed order finds more implication relations than others and is effective for redundancy identification.

A new Built-in Self Test (BIST) method for multiple configurable logic block (CLB) faults of SRAM-Look-Up-Table (LUT) type FPGA is reported. In this method, self test is performed concurrently for every test block containing eight CLBs. Faulty FPGA which includes up to five faulty CLBs in one test block can be detected completely even if each faulted CLB includes unlimited number of faults.

This paper presents a new approach to improving the diagnosability of a CMOS circuit by dividing it into independent partitions and using a separate power supply for each partition. This technique makes it possible to implement multiple I/sub DDQ/ measurement points. As a result, the diagnosability of the circuit can be improved. The problem of partitioning a circuit is addressed and optimum and heuristic solutions are proposed. The effectiveness of our approach is demonstrated through experimental results.

We present a procedure to reduce sequential circuits by removing undetectable faults based on unreachable states. Procedures for obtaining unreachable stares and for identifying undetectable faults which can be the target of fault removal are presented. Experimental results for ISCAS benchmark circuits are shown.

In logic synthesis the multi-level logic optimization methods using implication analysis has high performance but it needs a lot of computational time because of using test pattern generation to identify redundant faults. In this paper we proposed a fast redundancy identification method using implication relation instead of test pattern generation. Experimental results for benchmark circuits clearly show that the proposed method can accelerate the speed to identify redundancies without declining of the ability of the optimization.

As VLSI circuits become high-speed and high-density, a crosstalk fault becomes an important problem. In a synchronous sequential circuit, since the crosstalk fault between a data line and a clock line is important, we described an algorithmic test generation technique for the fault. Some simulation results of our method for the ISCAS bench mark circuits are reported.

This paper presents a design-for-testability technique aimed at test length reduction for scan designed circuits. A new concept, called partially parallel scan chain, is introduced. In the partially parallel scan chain, some flip-flops are arranged in parallel so that the number of scan shift clocks is reduced. Retiming techniques are used to select the flip-flops arranged in parallel. The flip-flops are repositioned only during test vector generation, but not actually. Then the test vectors generated for the retimed circuit are applied to the original circuit. In this paper, the difference in detectability of faults between the retimed circuit and the original circuit is also discussed. Finally experimental results are shown.

This paper presents a method to compact test sequences for full scan designed circuits by using the reduced scan shift and the retiming. The reduced scan shift, which we previously proposed, can compact test sequences by omitting unnecessary scan shifts. In this work, retiming, which repositions flip-flops, is introduced to enhance the effect of the reduced scan shift. When the number of flip-flops is reduced by the retiming, the test length is also reduced. Furthermore, this paper shows that the test length can be reduced even when the number of flip-flops is not reduced by the retiming. Under applying the reduced scan shift, the change of the control requirement to flip-flops by the retiming causes the reduction of scan shifts. Test vectors for the retimed circuit can be obtained by modifying the test vectors for the original circuit. Then the computing time to newly generate test vectors can be saved. Finally experimental results are given to show the effectiveness of the proposed method.

In this paper, we propose a power reduction tool named PORT, which evaluates the power dissipation factor /spl Phi/ by utilizing the transition probability, and which reduces /spl Phi/ by utilizing sets of permissible functions. Experimental results show the usefulness of PORT. Next, we will consider on the testability of circuits transformed by PORT. The size of the test set generated by compact test set generator, the number of redundant faults and the number of paths are used as testability parameters for detecting stuck-at and delay faults. Experimental results show that the test size of the circuit transformed by PORT is smaller than or equal to that of original one, but transformations by PORT increase the number of paths.

This paper discusses the problem of locating transistor leakage faults with only I/sub DDQ/ measurement. A new approach of equivalence fault collapsing is proposed for reducing the number of faults that must be considered. Fault location is performed by using both random and deterministic tests in order to obtain a high diagnostic resolution with a small number of tests. The experimental results show that the diagnosed faults are confined to only a few gates in many cases and that a very high average diagnostic resolution can be achieved for a gate-array circuit.

This paper presents a retiming and redundancy removal method for a sequential circuit with a specified initial state so that the resynthesized circuit has a state corresponding to the initial state and gives same behavior for any input sequences of the original circuit. Experimental results show the proposed method can optimize circuits as well as the method which does not consider the specified initial state.

This paper presents new cost-effective heuristics for the generation of minimal test sets. Both dynamic techniques, which are introduced into the test generation process, and a static technique, which is applied to already generated test sets, are used. The dynamic compaction techniques maximize the number of faults that a new test vector detects out of the yet-undetected faults as well as out of the already-detected ones. Thus, they reduce the number of tests and allow tests generated earlier in the test generation process to be dropped. The static compaction technique replaces N test vectors by M < N test vectors, without loss of fault coverage. During test generation, we also find a lower bound on test set size. Experimental results demonstrate the effectiveness of the proposed techniques.

Many recent ASICs include both analog and digital circuits, called mixed-signal integral circuits, to realize required functions on one chip. The comparator circuit is a principal element in the mixed-signal integrated circuit. In this paper we discuss a method for testing CMOS comparators. The method is current testing using both the upper limit and the lower limit. Bridging faults and break faults are assumed on the circuit layout and are analyzed by a circuit simulator. We examine the efficiency of fault detection by current testing. The result of the test shows that the proposed testing method has the highly fault coverage more than 94 percent.>

This paper presents a new testing method for sequential circuits, called reduced scan shift, which generates short test sequences. In this method, only part of flip-flops close to the scan input line are controlled and another part of flip-flops close to the scan output line are observed by scan shift operations as small as possible. For the purpose of reducing scan shift operations, the following points are considered: (1) how to decide target faults which each test vector should detects, (2) how to arrange flip-flops in the scan chain, (3) how to decide the order of test vectors. Experimental results for ISCAS'89 benchmark circuits are given to show the effectiveness of this method.

This paper presents a method of test compaction for stuck-at faults in combinational circuits, that complements previously proposed methods and allows further reduction in test set size in a cost-effective way. A given test set is compacted by generating additional test vectors. Each test vector added allows the removal of two or more test vectors from the existing test set, thus reducing its size. Experimental results for benchmark circuits demonstrate the effectiveness of the method.>

The continuous reduction of the device size in integrated circuits and the increase in the switching rate cause parasitic capacitances between conducting layers to become dominant and cause logic errors in the circuits. Therefore, capacitive couplings can be considered as potential logic faults. Classical fault models do not cover this class of faults. This paper presents a logic level characterization and fault model for crosstalk faults. The authors also show how a fault list of such faults can be generated from the layout data, and give an automatic test pattern generation procedure for them.>

Article Cost-effective generation of minimal test sets for stuck-at faults in combinational logic circuits Share on Authors: Seiji Kajihara View Profile , Irith Pomeranz View Profile , Kozo Kinoshita View Profile , Sudhakar M. Reddy View Profile Authors Info & Claims DAC '93: Proceedings of the 30th international Design Automation ConferenceJuly 1993 Pages 102–106https://doi.org/10.1145/157485.164617Online:01 July 1993Publication History 45citation336DownloadsMetricsTotal Citations45Total Downloads336Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

This paper presents a method for generating test sets to detect multiple stuck-at faults in combinational circuits. The proposed method is based on parallel vector pair analysis which finds faulty status of each line. The parallel analysis can bring higher fault coverage and smaller test sets than the serial vector pair analysis. In our method, redundant lines are removed firstly. An then a compacted test set for single stuck-at faults is generated in order to construct vector pairs used in the parallel analysis. Experimental results show that test sets to detect all multiple stuck-at faults were generated for 25 benchmark circuits and the parallel analysis was very effective for test generation.

In current testing, the number of test vectors is usually A testing circuit for built-in current testing is proposed and a test generation method using the testing circuit is described. The function of the testing circuit is to measure the integral of the current including the dynamic current during a certain time interval and to judge whether the Cuir is fault-free or not by the measured value. The function01 speed of the testing circuit is rapid because this measuring method is not influenced by any dy,rlamic current. We also describe the test generation method briefly. The test sequences cause almost equal dymmic current between every two test vectors. The number of test vectors in each test sequence is less than that of the traditional testing for stuck-at faults.

It is assumed that the outputs of all gates in a circuit are observable under the highly observable condition. This paper presents two kinds of testable sequential circuits: k-UCP sequential circuits and k-UCP scan circuits, under the highly observable condition. The combinational portions in both kinds of circuits are k- UCP circuits which consist of only k-input gates and inverters. All stuck-at faults in a k-UCP sequential circuit and a k-UCP scan circuit can be tested by 3(k + 1) and k + 1 test vectors respectively under the highly observable condition.

The concept of k-UCP circuits is proposed. In a k-UCP circuit, all stuck-at faults and stuck-open faults can be detected and located by k+1 and k(k+1)+1 tests, respectively, under the highly observable condition. A method of modifying an arbitrary combinational circuit into a k-UCP circuit is also proposed.>

Some algorithms and applications of inductive fault analysis (IFA) for the design of process-induced fault-tolerant VLSI CMOS circuits are presented. Starting from a mask-level IC design, the IFA procedure extracts all circuit-level faults which may result in the induction of a parasitic physical defect owing to an impure process fabrication. Algorithms concerning the fault list extraction, the density-fault map, and layout-to-schematic tools are detailed and illustrated through comprehensive examples. Applications of IFA cover validation of fault models, better fault coverage of test pattern sets, optimization of process fault-tolerant designs, and evaluation of the effectiveness of new design strategies.>

Two methods for modifying an arbitrary CMOS combinational circuit into a testable CMOS combinational circuit, called a k-UCP circuit, are discussed. All stuck-at faults and stuck-open faults in a k-UCP circuit can be detected by a test pattern which is a combination of no more than 2(k+1) kinds of basic sequences of fixed-length k(k +1)+1 under highly observable conditions. And all single stuck-open faults in a k-UCP circuit can be located efficiently. Experimental results show that the NAND (NOR) circuit modification is better than the general circuit modification in terms of the number of additional transistors. Experimental results also show that setting a proper backtrack limit can reduce computation time greatly. From a practical point of view, the results obtained are of value for developing CMOS ASICs (application-specific integrated circuits), where hardware overhead is allowed to some extent, but a fast diagnostic procedure is required.>

A novel fault model is developed for random-access memories for a class of pattern-sensitive faults called row/column weight-sensitive faults. A test procedure is developed to detect faults from the defined fault model. This test sequence also tests the memory array for the 5-cell-neighborhood static pattern-sensitive faults and other faults, such as stuck-at-faults and coupling faults. A built-in self-test (BIST) version of the algorithm has been implemented by completing the logic design and layout in 2- mu m CMOS technology. The silicon area overhead for a 4M RAM is as little as 0.8%. The number of extra pins can be as low as one if clock is available on-chip. The number of extra pins can be as low as one if clock is available on-chip. The delay introduced to the normal paths, as estimated by simulation tools, is small and can be reduced even further.>

An algorithmic test pattern generation method named ZALG* for circuits including tri-state modules that have been extensively used in recent MOS VLSI is presented. For the circuits, special attention must be paid to bus clash and memory retention in order to avoid device destruction in testing. Since ZALG* takes complete measures against bus clash and memory retention and uses a multiple-path sensitization method, like PODEM, it is a complete algorithm in the sense that all possible combinations of input values will be tried in the worst case. ZALG* is implemented by FORTRAN, and some experimental results for circuits with two to three thousand gates are reported.>

A test pattern generating system, CONT (CONcurrent Test generation) is discussed. The CONT system consists of two modes for test generation, TGM-C (CONT algorithm) and TGM-S. The TGM-C (test generation mode with concurrency) generates fault lists concurrently in order to speed up test generation. In the process of test generation with TGM-C, the primary input value is not changed but a target fault is switched to another one using the fault list when backtrack occurs. The TGM-S (test generation mode with a single target fault) generates a test pattern without changing a target fault. Experimental results show that the CON system is an efficient test generation system.>

In this paper we study the problem of testing RAM. A new fault model, which encompasses the existing fault models, is proposed. We then propose a scheme of testing faults from the new fault model using built-in testing techniques. We introduce concept of p-hard and determine the complexity of the extra hardware required for built-in self-testing on our hardness scale. A novel approach using microcoded ROM for implementation of built-in testing is also proposed and its complexity is determined.

In this correspondence we consider the problem of test pattern generation for random-access memory to detect pattern-sensitive faults. A test algorithm is presented which contains a near-optimal WRITE sequence and is an improvement over existing algorithms. The algorithm is well suited for built-in testing applications.

In this paper, the problem of fault detection for multiple faults in programmable logic arrays (PLA's) is discussed. An easily testable design of PLA's has been proposed which has the following properties: 1) for a PLA with n inputs, m product terms, there exists a test set such that the test patterns do not depend on the function realized by the PLA; 2) the number of tests to detect multiple stuck type and cross point faults is m(2n + 1) + 4n + 4; 3) the number of additional pins for the testable design is 3; 4) the design philosophy is compatible with the built-in-testing approaches.

In this paper the problem of fault detection in easily testable programmable logic arrays (PLA's) is discussed. The easily testable PLA's will be designed by adding extra logic. These augmented PLA's have the following features: 1) for a PLA with n inputs and m columns (product terms), there exists a "universal" test set such that the test patterns and responses do not depend on the function of the PLA, but depend only on the size of the PLA (the values n and m); 2) the number of tests is of order n + m. For the augmented PLA's, universal test sets to detect faults in PLA's are presented. The types of faults considered here are single and multiple stuck faults and crosspoint faults in PLA's. Fault location and repair of PLA's are also considered.

A conservative logic element (CLE) is a multiple-output logic element whose weight of an input vector is equal to that of the corresponding output vector, and fan-out of each output terminal is restricted to one. A CLE is a generalized model of magnetic bubble logic elements, etc. In order to realize an arbitrary function, it is necessary to use constant-supplying elements (CSE's). In this correspondence, we consider the universality of CLE's in relation to the number of CSE's.

In this correspondence, the number of functions and the number of equivalence classes of functions realized by fanout-free networks and cascades of AND'S, OR'S, and inverters are presented. For fanout-free functions, recursive formulas for TND(n) and φND(n), the number of n-p-n-equivalence classes of n-variable functions and p-equivalence classes of n-variable functions, respectively, are derived. For unate cascade functions, a recursive formula for ψND(n), the number of n-variable functions, and formulas for UND(n) and ψND(n), the number of n-p -equivalence classes and p-equivalence classes, respectively, are derived. Some asymptotic properties of ψND(n), UND(n), and ψND(n) are also examined and it is shown that ψND)/ψ(n)→ 1/√2, UND(n)/U(n)→ 1/2, and ψND(n)/ψ(n)→ 1/√2 as n →∞, where ψ(n) is the number of distinct unate cascade functions of up to n variables, and U(n) and ψ(n) are the number of distinct n-p-n-and p-equivalence classes of unate cascade functions of up to n variables, respectively.

In this paper we analyze the computational complexity of system diagnosis. We show that several problems for instantaneous and sequential fault diagnosis of systems are polynomially complete and that for single-loop systems these problems are solvable in polynomial time.

This correspondence is concerned with probabilistic fault diagnosis for digital systems. A graph-theoretic model of a diagnosable system introduced by Preparata et al.[3] is considered in which a system is made up of a number of units with the probability of failure. The necessary and sufficient conditions are obtained for the existence of testing links (a connection) to form probabilistically t-diagnosable systems with and without repair. Methods for connection assignments are given for probabilistic fault diagnosis procedures with and without repair. Maheshwari and Hakimi [10] gave the necessary and sufficient condition for a system to be probabilistically t-diagnosable Without repair. In this correspondence, we show the necessary and sufficient condition for a system to be probabilistically t-diagnosable with repair.

This correspondence is concerned with probabilistic fault diagnosis for digital systems. The model considered in this correspondence is the diagnostic model introduced by Maheshwari and Hakimi where each unit has a probability of failure. For this model under both fault assumptions by Maheshwari-Hakimi and by Barsi-Grandoni-Maestrini, some existence theorems are obtained for probabilistically diagnosable systems. 1) Necessary and sufficient conditions for the existence of testing links to form probabilistically t-diagnosable systems with and without repair. 2) Necessary and sufficient conditions for the existence of probabilities of failure of all units to form probabilistically t-diagnosable systems with and without repair which have no hardcore.

This correspondence is concerned with the realization of logical functions by using two-input three-output conservative logic elements (CLE's) called IB.

A conservative logic element (CLE) is a multiple-output logic element whose weight of an input vector is equal to that of the corresponding output vector, and is a generalized model of magnetic bubble logic elements, fluid logic elements, and so on. This paper considers the problem of realizing arbitrary 3-input 3-output conservative logic elements (3-3 CLC's) by cascade connections of 3-input 3-output CLE's called "primitives." It is shown that the necessary and sufficient number of different primitives to realize an arbitrary 3-3 CLC is three in the case when the crossovers of lines are permitted, and four in the case when the crossovers of lines are not permitted.

This paper is concerned with the realization of logic functions by using two-input magnetic bubble logic elements. A magnetic bubble logic element is the multiple-output logic element whose number of ``1'' 's of the output is equal to that of corresponding input, and fanout of each output terminal of the element is restricted to one. In order to realize some functions, it is necessary to use the generators which correspond to constant-supplying elements. First, the number of generators which are necessary and sufficient to realize an arbitrary functions is obtained for a given set of elements. In particular, it is shown that an arbitrary function can be realized by using IBelements and at most two generators. Since the IBelement is a universal element in the above sense and is considered to be rather easily realized by magnetic bubble interactions, the IBlogic circuits are mainly discussed. The IBminimum circuit defined here is a circuit which consists of minimum number of generators and minimum number of IBelements. In the last half of this paper, it is shown that the minimum circuits of most functions have the characteristic circuit structure called ``1-4 form.''

In this paper, an easily testable machine is defined as one which possesses: 1) a distinguishing sequence of length [log2 n] which forces the machine into a specific state S1, and 2) transfer sequences of length at most [1og2 n] to carry the machine from state S1 to state Si for all i. A design procedure is presented in which an arbitrary machine is augmented to an easily testable machine by adding two special input symbols to the original machine. An efficient procedure is also described for designing checking experiments for the easily testable machines. For an n-state, m-input symbol machine, this procedure gives a bound on the length of the checking experiment that is approximately mn[log2,n]. Furthermore, the total checking experiments are preset.

This paper is concerned with the problem of designing easily testable sequential machines, output-observable machines, for which there exist very short checking experiments. A sequential machine for which any initial state can be uniquely determined only by the output response is said to be output-observable. An algorithm is developed to modify a given machine to an output-observable one by adding a minimum number of extra outputs. This method is based on the fact that the output-observable realization of a given machine M exists if and only if M is semi-FSR realizable (a special type of feedback shift register realization).

By a checking sequence for a sequential machine, we mean an input-output sequence with a special property such that, when the input sequence is applied to the machine, the decision whether or not the machine operates correctly can be made by comparing the output sequence with the output of the machine.