A probabilistic diagnosis algorithm is presented for constant degree structures. The performance of the algorithm is analyzed under a negative binomial failure distribution to account for fault clustering. It is shown that the algorithm can correctly identify almost all units even when the yield is low (much lower than 50%) and when faults are clustered. A wafer test structure is proposed, which utilizes the test access port of each die to perform comparison tests on its neighbors and incorporates a localized version of the diagnosis algorithm to determine the status of each die. Both the test time and the diagnosis time are invariant with respect to the number of dies on the wafer. The saving of test costs could be significant as compared with probe testing, because with probe testing dies are probed one at a time while they are tested in parallel with this scheme. The scheme is unique in that it is shown to work well when faults are clustered and when the yield is low.

This paper addresses the issue of testing MCMs on large-area substrates. The cost of testing each MCM may be as high as 40% of the total manufacturing cost. It is critical that the test process be parallelized in order that multiple MCMs may be tested for the cost of testing one MCM. With this objective in mind, we propose a distributed probabilistic diagnosis algorithm for MCMs on large-area substrates. Our algorithm performs better than the existing diagnosis algorithms and can correctly identify almost all MCMs even when the yield is very low (35%). Further it provides upto an order of magnitude reduction in test application time as opposed to serial MCM probe test.

Signature computation for linear compactors in a BIST environment is a computationally intensive process. In this paper, a fast compaction simulation algorithm is presented which uses superposition and look-up tables. While keeping memory requirements reasonable, this algorithm has a speedup advantage of at least one order of magnitude over traditional algorithms, and offers a threefold speedup over recently published "fast" algorithms. Our algorithm is also applicable to any linear compactor - while existing algorithms are restricted to only one type of compactor. Simulation results comparing the speed and memory requirements of the proposed compaction algorithm to that of existing compaction algorithms are given.>

A simple diagnosis algorithm is presented for constant degree systems such as rectangular grids connected as tori. The algorithm determines the status of a unit according to the size of its faction, a cluster of units that call each other fault-free but outsiders faulty. Almost all units are correctly identified with this algorithm under a binomial failure distribution even when the probability of failure is rather high. The complexity of the algorithm is O(n), where n is the number of units in a constant degree system. The application of the algorithm to production testing of VLSI chips is also considered. With a test board that houses a large number of chips to be tested, all the chips can be tested in parallel in a way that they test each other and the test outcomes, not necessarily correct, are reported to a host system for analysis. The actual status of each chip is determined by using this new diagnosis algorithm. The above chip screening process can be repeated for higher accuracy. It is shown that no more than two steps are needed in most real situations. Compared with testing by test equipment that usually tests only one chip at a time, the saving of test time and the test equipment cost could be significant with our approach.>

VAMP (Variation Analysis with Matching Program) considers the impact on system-level performance caused by device-level parameter variations and mismatch effects using hierarchical behavioral modelling and statistical circuit simulation. It targets cases for which complete transistor simulation is not feasible. Hierarchy is used to decrease model dimensionality and reduce the intensive simulation requirements. Approximation of distributions at an intermediate level is the key to making the link between the detailed device level and the abstract system level tractable, both in terms of clarity and of computing load.>

A classic PMC (Preparata, Metze, and Chien) multiprocessor system [F. P Preparata, G. Metze, and R. T. Chien, IEEE Trans. Electr. Comput., EC-16 (1967), pp. 848–854] composed of n units is said to be ${t / {(t + 1)}}$ diagnosable [A. D. Friedman, A new measure of digital system diagnosis, in Dig. 1975 Int. Symp. Fault-Tolerant Comput., 1975, pp. 167–170] if, given a syndrome (complete collection of test results), the set of faulty units can be isolated to within a set of at most $t + 1$ units, assuming that at most t units in the system are faulty. This paper presents a methodology for determining when a unit $\upsilon $ can belong to an allowable fault set of cardinality at most t. Based on this methodology, for a given syndrome in a ${t / {(t + 1)}}$-diagnosable system, the authors establish a necessary and sufficient condition for a vertex v to belong to an allowable fault set of cardinality at most t and certain properties of ${t / {(t + 1)}}$-diagnosable systems. This condition leads to an ${{O(n^{3.5} )t} / {(t + 1)}}$-diagnosis algorithm. This ${t / {(t + 1)}}$-diagnosis algorithm complements the ${t / {(t + 1)}}$-diagnosability algorithm of Sullivan [The complexity of system-level fault diagnosis and diagnosability, Ph.D. thesis, Yale University, New Haven, CT, 1986].

We demonstrate a structure for mutual test among N processing elements. We indicate how this structure might be used to identify the good dice on a semiconductor wafer at a cost below that of current techniques. Under either a digraph or a comparison model, our proposed test structure has the following properties: 1) It is nearly regular. 2) It can be laid out in area O(/spl ominus/(n). 3) In time /spl ominus/(N) and with high probability, all but at most an arbitrarily small fraction of the good elements can be identified. 4) The number of tests or comparisons per element is bounded by a constant. We approximate this constant analytically. The result is a substantial savings over the /spl ominus/(log N) tests per element in regular structures whose purpose is to identify, with high probability, every good element. In contrast with the majority of previous work, our results apply even when less than half of the elements are good.>

This paper shows how to: (1) convert single-bit march tests into multi-bit March tests; and then (2) how to transform the new multi-bit March tests, using a "serial shifting notation" which represents "serial access" in embedded RAMs, into serial-access word-oriented March tests. The standard March test notation is extended to compactly include Galloping read actions, and other algorithms with two levels of FOR-loops, since such algorithms are indispensible for locating coupling faults in cell arrays, and stuck-open faults in address decoders. The main body of the paper uses the new notations to describe seven categories of fault location algorithms, with each algorithm displayed in both the "hybrid serial/parallel" and the "modular" data accessing formats.>

Architectural level design and synthesis requires a versatile library support system. Such a system must have provisions for organizing abstract models in a hierarchical manner as well as retrieval and storage of components in an object-oriented manner. Common relations between models can then be captured and different library models substituted and reused within the environment. An example of the capabilities of the library system for DASE is also provided.>

The authors study the fault diagnosis of multiprocessor systems when fault constraints in the local domain of each processor are specified. They use the comparison-based model. A multiprocessor system S is t-in-L diagnosable if, given a syndrome, all faulty processors can be uniquely identified provided there are at most t faulty processors in the local domain L(u/sub i/) union (u/sub i/) of every processor, u/sub i/ in S, where L (u/sub i/) denotes the set of processors adjacent to u/sub i/. Certain basic results that lead to efficient conditions for unique diagnosis of a system when certain fault constraints are satisfied in the local domain of each processor in the system are presented. The t-in-L diagnosability of certain regular interconnected systems is examined under the assumption that less than half of the processors in the system are faulty. Diagnosis algorithms for these systems are presented.>

A framework for system level synthesis is presented, and a suitable language, DSL, for capturing design specifications and generating control graphs amiable to synthesis is proposed. The three stages in the synthesis process-design specification, intermediate representation, and synthesis-are examined in detail. A rough version of the language is used to model a simple system.>

A distributed diagnosis algorithm to locate faulty processing elements in large-scale regular interconnected structures based on the concepts of system-level diagnosis is developed. This algorithm can either operate in a systolic manner or may be executed on a supervisory processor to locate the faulty processors. The computational complexity of the algorithm is linear when run on a supervisory processor and constant when run in parallel systolic manner. The implementation complexity and diagnosis capability of the algorithm are also analyzed without restricting the fault set size. The probability of correct diagnosis is shown to be very high even in the presence of large fault sets.>

The issues of printed circuit board (PCB) interconnect testing are addressed in the context of boundary-scan architecture. Boundary-scan architecture is treated here as the framework for a PCB level built-in self-test (BIST). A novel BIST method is developed which utilizes various features of the architecture. Boundary-scan architecture is shown to have the capability to generate time-efficient test vector sets. Response compaction within the boundary-scan chain is introduced to reduce shift out time as well as to simplify detection and diagnosis. However, the proposed BIST schemes require some extensions of the standard boundary-scan cells, and the schemes can work only if every boundary-scan cell of every IC on the PCB has the proposed extensions.>

Recent predictions about the aliasing behavior of linear feedback shift registers used in signature analysis with pseudorandom testing are validated experimentally. It is shown that the independent error model accurately predicts aliasing in these signature registers when test sets are selected at random. In practice, however, a circuit's test set is fixed, and it is shown that adopting a more general asymmetric error model, of which the independent is a special case, yields more accurate aliasing information, especially in the dynamic or non-steady-state region of the aliasing profile. The only additional information needed to apply the asymmetric model to signature analysis is the fault-free sequence. Since this sequence is needed in any case to compute the fault-free signature, the model can reflect test set ordering at no extra cost.>

The authors present a general technique for computing P/sub e/ for all possible shortened versions of cyclic codes generated by any given polynomial. The technique is recursive, i.e. computes P/sub e/ for a given code block length n from that of the code block length n-1. The proposed computation technique for determining P/sub e/ does not require knowledge of the code weight distributions. For a generator polynomial of degree r, and mod g mod nonzero coefficients, the technique yields P/sub e/ for all code block lengths up to length n in time complexity O(n mod g mod 2/sup r+ mod g mod /). Channels with variable bit error probabilities can be analyzed with the same complexity. This enables the performance of the code generator polynomials to be analyzed for burst errors.>

An algorithm, ALG-MK, for computing exact aliasing probabilities in signature analysis is derived from a Markov process model of signature analysis. A previous algorithm, ALG-BL, which was derived from a Boolean expressions formulation of the problem, is reformulated so that it can also be reviewed as being based on a Markov process. Both algorithms compute exact aliasing probabilities in signature analysis. The computational complexities of the two models are compared. It is shown that the time complexity of the iterative algorithm ALG-MK is O(L2/sup k/), disregarding slight possible start-up and termination improvements, while that of ALG-BL is O(Lf2/sup k+f/), where k is the size of the signature register, f is the number of feedback taps, and L is the test sequence length. ALG-BL requires more shift and add operations, but requires half the number of floating-point multiplications that ALG-MK requires. The space complexity of ALG-MK is O(2/sup k/), while that of ALG-BL is O(2/sup k+f/). It is also shown that ALG-MK and ALG-BL are formally related through a linear transformation of their state vectors. Both algorithms may be used to study aliasing under generalized error models.>

It is proposed that a pseudorandom sequence and a single weighted random sequence be used to implement built-in self-test (BIST) efficiently in a large integrated scan circuit which would otherwise need an excessive pseudorandom test length. A method of determining the weight set and the approximate pseudorandom and weighted random test lengths, based on fast fault simulation tools, is suggested. By modifying specific scan cells, the BIST hardware conditionally generates the weighted stream locally, at specific input sites. A weighted control signal is used to regulate the proportion of weighted and pseudorandom inputs. Apart from determining that, in the cases examined, one weight set was sufficient for a notable decrease in test time, it was also noticed that a very coarse weight set (i.e. restricting biases to 0, 0.25, 0.5, 0.75, and 1) provides acceptable results. Using finer resolution within the weight set usually results in a slightly higher coverage, but at the expense of a much higher area overhead.>

A diagnosis method is proposed which may be used to locate faults in circuits tested with random or pseudorandom test vectors. No intermediate signatures are involved, and the external hardware required is not complex. This proposed diagnosis scheme, called DAPPER, is applicable to multioutput combinational circuits. DAPPER classifies faults initially by their detection probability for coarse resolution, and secondly using their first failing pattern and a conventional signature for fine resolution. This method uses offline posttest simulation to isolate a single fault with only a fraction of the simulation that would ordinarily be required. Additionally, any failures within the test hardware itself may be diagnosed using the method.>

The authors propose test schemes for glue logic (non-boundary-scan components) interconnects. Testing these interconnects is difficult owing to reduced accessibility and glue-logic function-dependent outputs. The proposed schemes address these testability issues and provide efficient boundary-scan based techniques. The tests are applied under the B-Scan DFT (design-for-testability) environment as scan tests. Thus, issues such as ease of test vector generation, test vector loading time, and test application time are very important for the proposed schemes. The application of the test schemes is described.>

An effort is made to validate experimentally predictions on aliasing in signature analysis registers under the independent error model. From the experimental results it appears that the independent error model accurately predicts the probability of aliasing in signature registers. The authors also provide justification for the adoption of a more general asymmetric error model of which the former is a special case; the latter can be used at no extra cost. Among the potential benefits in using the asymmetric error model is the subdivision of faults into classes based on pD and pDbar, the conditional probability, respectively, of the fault-free bit being 1 and the faulty bit being 0 and vice versa, whereby faults in a given class have the same probability of aliasing. Under the independent error model fault classification is based on a single parameter p. Use of an asymmetric model hence provides a better resolution in terms of the classification of faults based on aliasing probability. Experimental results also indicate that considering the asymmetric nature of circuit outputs yields more useful information, especially in the dynamic region of the aliasing curve.>

The complexity of the single-fault (SF) set diagnosability and SF-diagnosis problems under the symmetric invalidation models is discussed. It is shown that the SF-diagnosis problem under both these models is co-NP-complete and the SF-diagnosability problem is also co-NP-complete under the asymmetric invalidation model. The SF-diagnosability problem is also studied under the symmetric-invalidation model and a polynomial time-complexity algorithm is presented. These results are in contrast with the corresponding t-diagnosability and t-diagnosis problems, which are known to have polynomial time-complexity algorithms.>

The authors present an analysis technique useful for studying the probabilistic behavior of signature analysis registers, which is in turn useful for studying the aliasing problem. The technique is applicable to all linear-feedback signature analysis registers, i.e. characterized by any linear-feedback polynomial, including multiple-input signature registers. The basis for the technique is the calculation of a sequence of probabilities where the ith element of the sequence corresponds to the probability that one particular stage of the linear-feedback signature register (LFSR) is in the state 0 or 1 after the ith bit has been shifted in the LFSR. The complexity for calculating such a single-stage state probability sequence is linear in time and space. The authors generalize such sequences to k-stage state probability sequences.>

A comprehensive design methodology which includes built-in self-test (BIST) cannot be achieved without performance measures of BIST techniques. Exact and asymptotic expressions are derived for the aliasing probability of randomized syndrome testing using the independent error model proposed by T.W. Williams et al. (IEEE Trans. Computer-Aided Design, vol.7, no.1, p.75-83, 1988). It is shown that randomized syndrome testing outperforms signature analysis for a substantial class of functions, and that existing methods can be used to transform the remaining functions during test mode.>

A comparative study is presented of different methods of calculating multiple fault coverage and aliasing probability measures. The objectives are to describe the ways that these ratios are defined to give them a physical interpretation, and to separate the discussion of how to define the measure from how the measure might be actually obtained or calculated. The interpretation, accuracy, and applicability of the measures are discussed.>

A built-in self-test of interconnects based on boundary scan architecture is described. Detection and diagnosis schemes are proposed which provide minimal-size test vector sets. I/O scan chains order independent test vector sets and walking sequences. Properties like ease of test vector generation, structure-independent detection and diagnosis, and local response compaction have made the developed schemes suitable for built-in-self-test implementation. An example board-interconnect test session is described using one of the proposed schemes.>

A reconfiguration scheme is presented that is suitable for both yield and reliability enhancement of large-area VLSI implementations of binary tree architectures. The approach proposed makes use of partially global redundancy to allow clustered effects to be tolerated. The binary tree is cut a few levels above the leaves to form an upper subtree and many lower subtrees, with spare processors being grouped adjacent to the root of each lower subtree. Redundant links with programmable switches are used to permit reconfiguration. The cost of the scheme, in terms of redundant hardware, is comparable to that of other schemes. An O(N) H-tree layout is used. In comparison to existing schemes, the proposed scheme gives much better yield and better reliability.>

Two automatic test pattern generation (ATPG) algorithms, PODEM and FAN, use heuristics that rely on testability measures (TMs). The use of random-pattern (probabilistic) TMs in these heuristics has already been proposed and investigated. The types of TMs proposed for such use are static. Static TMs (STMs) become increasingly unjustifiable as the search for a test pattern progresses. Dynamic TMs (DTMs) are introduced as a method to overcome the deficiency in the quality of STMs while still observing linear time and storage constraints. Based on results from several experiments, test-set generation strategy is devised that utilizes the advantages of both STMs and DTMs. From the experiments performed on benchmark circuits, compared to the strategy wherein only STMs are used to attain a given fault coverage, the proposed strategy requires considerably less CPU time to obtain a test set which attains the same fault coverage.>

System-level diagnosis appears to be a viable alternative to circuit-level testing in complex multiprocessor systems. A completely new generalization of the characterization problem in the system-level diagnosis area is developed in this paper. This generalized characterization theorem provides necessary and sufficient conditions for any fault-pattern of any size to be uniquely diagnosable, under the symmetric, and asymmetric invalidation models with or without the intermittent faults. Moreover, it is also shown that the well known t-characterization theorems under these models can be derived as special cases. In addition to the generalization provided by these results, it is hoped that these results will also have a great impact on the diagnosis of faulty units in uniform structures based on the system-level diagnosis concepts and would be particularly useful in the diagnosis of WSI-oriented multiprocessor systems.

This correspondence presents a new built-in self-test design for PLA's, that has a lower area overhead and higher multiple fault coverage (of three types of faults: crosspoint, stuck, and bridging) than any existing design. This new design uses function independent test input patterns (which are generated on chip), compresses the output responses into a function independent string of parity bits (whose fault-free expected values are generated on-line with a simple circuit), and detects all siqgle faults and more than ( 1 −−2(m+2n) of all multiple faults where m and n represent the number of product terms and input variables, respectively.

Soft errors caused by ionizing radiation will be a limiting factor in the reliability of VLSI circuits with submicron-feature sizes. A new approach to the design of soft-error-tolerant digital integrated circuits'is presented. It is based on the filtering of transients at register inputs, and it incurs a lower area overhead than known techniques. The method, called soft-error filtering (SEF), is derived on the basis of the analogy between a noise-sensitive finite-state machine and a noisy communication channel. The necessary characteristics of the register are examined and a design is presented for the associated filter. It is shown that SEF can be used to reduce the associated error rate to insignificant levels.

A new modular, fault-tolerant scheme is proposed for the binary tree architecture. The approach uses redundant modular fault- tolerant building blocks to construct the complete binary tree. The restructuring operation is local to each faulty module. The proposed scheme is shown to be more reliable and easier to implement than the existing fault-tolerant schemes.

A new logic minimization algorithm is presented. It finds a minimal cover for a multiple-output boolean function expressed as a list of cubes. A directed graph is used to speed up the selection of a minimal cover. Covering cycles are partitioned and branched independently to reduce greatly the branching depth. The resulting minimized list of cubes is guaranteed to be minimal in the sense that no cover with less cubes can exist. The don't care at output is handled properly. This algorithm was implemented in C language under UNIX BSD4.2. An extensive comparison with ESPRESSO IIC shows that the new algorithm is particularly attractive for functions with less than 20 input and 20 output variables.

A new logic minimization algorithm is presented. It finds a minimal cover for a multiple-output Boolean function expressed as a list of cubes. A directed graph is used to speed up the selection of a minimal cover. Covering cycles are partitioned and branched independently to reduce greatly the branching depth. The resulting minimized list of cubes is guaranteed to be minimal in the sense that no cover with less cubes can exist. The dont care at output is handled properly. This algorithm was implemented in C under UNIX BSD4.2. An extensive comparison with ESPRESSO IIC shows that the new algorithm is particularly attractive for functions with less than 20 input and 20 output variables.

A systolic binary tree machine which can handle all the dictionary machine and priority queue operations such as Insert, Delete, Extract-Min, Extract-Max, Member, and Near is designed in this paper. The operations can be fed into the tree machine in a pipeline manner at a constant rate and the output is correspondingly generated in a pipeline manner. Each processor in the machine stores at most one data element, which consists of a key value and a record associated with the key. The machine has optimal performance since if the number of data elements present in the tree is n, then each operation takes O(log n) steps. Unlike some recent designs, this machine does not use any links other than the binary tree links, provides optimal performance without the need to store data elements in any sorted order by exploiting dynamic rebalancing, has higher throughput, and keeps the logical last level of the tree on one physical level of the tree.

The occurrence of a data flow anomaly is often an indication of the existence of a programming error. The detection of such anomalies can be used for detecting errors and to upgrade software quality. This paper introduces a new, efficient algorithm capable of detecting anomalous data flow patterns in a program represented by a graph. The algorithm based on static analysis scans the paths entering and leaving each node of the graph to reveal anomalous data action combinations. An algorithm implementing this type of approach was proposed by Fosdick and Osterweil [2]. Our approach presents a general framework which not only fillls a gap in the previous algorithm, but also provides time and space improvements.

A general theory is presented in this paper to quantitatively predict the multiple fault coverage capability of single fault detection test sets in combinational circuits. The theory is unique in that it provides greatest lower bounds on the coverage capability of all possible circuits of concern by a simple table-look-up process. All the results known so far in this area are seen to be special cases of the theory. The more important contribution of the theory, however, is seen in its predictions made for reconvergent internal fan-out circuits. Most unexpectedly, the multiple fault coverage of such circuits by single fault test sets is discovered to be extremely precarious. Such results clearly have alarming implications in LSI and VLSI testing.

The increasing recognition of PLA's as efficient and viable modules for such purposes as microprogramming and design of sequential controllers has led to a growing interest in the development of optimum fault detection test sets for these modules. It is now well known that a fault type which is unique to PLA's is the class of contact faults. A single contact fault is the spurious presence or absence of a contact between a row and a column of a PLA. We consider in this paper the problem of determining the capability of complete single contact fault test sets to cover multiple contact faults of PLA's. Our approach consists of developing a model of PLA's which allows one to represent a contact fault in a PLA as a stuck-at fault in the model of the PLA. Using this model, it is shown that more than 98 percent of all multiple contact faults of size 8 and less are inherently covered by every complete single contact fault test set in a PLA. Applications of this model to stuck-at fault diagnosis are also discussed.

Given any combinational, internal fan-out-free network and any complete single fault detection test set (SFDTS) for the network, we consider in this paper the problem of determining the minimal extent to which that SFDTS will cover multiple faults in the network. The basis of our approach is the development of a generic perspective to multiple faults which uses a representation of such faults called an L-expression. This perspective leads to a technique for obtaining the greatest lower bound on the multiple fault coverage capability of an SFDTS by means of a simple table look-up process. In addition to generalizing previously known results regarding multiple fault coverage, two particularly interesting results obtained from this approach are as follows: 1) On the average, every SFDTS for an internal fan-out-free network covers 92 percent of all multiple faults of sizes 8 and less. 2) On the average, every SFDTS for an internal fan-out-free network covers at least 46.1 percent of all multiple faults.

In the generation of test sets for the detection of stuck-type faults in combinational switching networks, it is an expedient and reasonably common assumption to consider explicitly faults only of specified sizes (for example, all single faults), and then to assume (or hope) that most or all faults of larger sizes will be covered (that is, detected) as well. This paper systematically addresses this aspect of multiple fault coverage in a quantitative manner for combinational networks, wherein only primary input fanout is allowed. A procedure is given to estimate (or project) the multiple fault coverage capability of a test set based on the known coverage capability of that test set for subsets of the multiple faults. This is accomplished by means of a recursive use of a detailed formula which exploits two fundamental interrelationships between test sets and faults. Based upon these results, it can be shown that the above-mentioned assumption must be made, in general, with discretion as its validity is highly network structure/test set dependent.

To efficiently perform the fault analysis of digital networks it is necessary that pertinent fault interrelationships be utilized. However, to determine these fault interrelationships can entail an analysis which is quite complex and thereby reduces the overall advantage of utilizing the gained insights in a fault analysis process. In this paper we suggest an approach to establishing the existence of a certain fault interrelationship relative to test set coverage in tree networks which is based only on the form of the output function. A procedure is given for generating a form expression (called an L-expression) corresponding to that function. A theorem is stated regarding the interpretation of these form expressions relative to test set coverage.

This correspondence considers fault resolution as a process of applying a sequence of input vectors, called tests, to a combinational logic network in order to resolve an existing fault situation from within a given master set of faults. A functional approach based upon an extension of the well-known Boolean difference concept to fault dependent situations is described. The test sets resulting from this extension, called fault dependent test sets, are fundamental to our considerations and are shown to be obtainable in a straightforward manner from standard test sets. Two fault interrelationships are defined which are particularly relevant to the resolution problem in that they algebraically describe the inherent limitations to the degree to which the existing fault situation can be resolved from within a given master set of faults using algebraic terminal experiments and fault dependent testing. Because these interrelationships are defined from a resolution-oriented point of view, they can be seen to be somewhat more intimate than other fault interrelationships which have been previously described in the literature. Some important ramifications of these interrelationships are discussed.