The problem of balancing the computational load between fault simulation and conventional ATPG (automatic test program generation) is treated. A rule for switching from probabilistic to deterministic test pattern computation is derived. The criterion is based on a model of monitoring of the simulation process and on an online estimation of the fault detection probabilities. Using these probabilities and the operation characteristics of the ATPG program, one can decide whether it is more efficient to continue fault simulation or to proceed with algorithmic test pattern computation. A prototype of the hybrid ATPG system was implemented on an Apollo DN3000. Compared to a conventional ATPG system, better coverage and shorter generation times were obtained.>

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.>

Contest (cone-oriented test pattern generator), an ATPG (automatic test pattern generation) tool for very large combinational digital circuits, is presented. Contest is based on four major ideas. Cone-oriented circuit partitioning reduces the circuit complexity and increases the number of dominators. The propagation graph is a dynamic data structure that keeps track of all paths from the fault location to a primary output. The multiple backtrace procedure reduces contradictory node assignments by examination of fanout nodes and dynamic implications. The pattern parallel fault dropping technique is based on Hamming distance variations of generated test patterns. Experimental results for benchmark circuits containing up to 40000 nodes illustrate the superiority of the ATPG system. For these circuits a 100% fault coverage for all detectable stuck-at faults and a 100% redundancy identification are achieved.>

Aliasing errors in linear feedback shift registers (LFSRs) used as signature analysis registers in self-testing networks are considered. A bound on aliasing is established by a straightforward algebraic analysis of LFSRs. It is calculated as a function of p, the probability of an error occurring at an output of the network under test. This bound is robust but is only good for p close to 1/2. To investigate the question of what happens to aliasing errors in general, the function of LFSRs is modeled by a Markov process and a solution is obtained by the z-transform. It is shown that for p>1/2 the aliasing probability for primitive polynomials converges much faster to the final steady-state value than for nonprimitive polynomials. For values of p>

The calculation of test patterns for PLAs is an expensive and time consuming task if a general purpose test pattern generation program is used. A unified treatment of faults in PLAs and a test pattern generation algorithm based on the calculation of Boolean differences is given in this paper. Calculating the difference between the Boolean functions of the faulty and the fault free circuit guarantees that a test for a given fault is found if it exists. By tailoring the algorithm to the specific structure of programmable logic arrays a powerful tool for the test pattern calculation for PLAs is obtained. An important feature of the method is the ease of incorporating different fault assumptions.

A hardware technique for testing large programmable arrays is presented. The method is based on an appropriate circuit partitioning and on using nonlinear feedback shift registers for test pattern generation. It allows the testing of a PLA within a number of cycles that is a linear function of the number of inputs and product terms. A 8 X 16 X 8 PLA is completely tested within 52 cycles; a 16 X 48 X 8 PLA requires 132 cycles. The test patterns do not depend on the individual personalization of any PLA. So there is no more need of an extensive fault simulation or test pattern computation. The result is a fast efficient built-in test for PLA-macros, the most promising building blocks of VLSI circuits.