Finding tests for hard-to-detect (HTD) faults in complex designs is challenging. Researchers use testability measures to guide automatic test pattern generation (ATPG) programs to improve fault detection efficiency. However, each measure favors the detection of specific faults in the same circuit. Principal component analysis (PCA), an unsupervised learning technique, has been used to combine several algorithmic testability measures. Guidance from the PCA measure was found to uniformly improve the ATPG efficiency with fewer backtracks, lower ATPG CPU time, detection of many HTD faults, fewer aborted faults, and increased fault coverage. The present work shows that these benefits continue further when we also included topological factors like fan-in and fanout cone base widths, fanout reconvergence data, and even-odd inversions on reconverging paths in a new-PCA measure. This work opens the venue for ongoing improvements.

This paper advances the recent results on testing skyrmion logic circuits, which recently gained popularity as an emerging technology. A skyrmion circuit differs significantly from the existing CMOS circuit in physical structure and operation mechanisms. The previous work identified 19 defect types and modeled them as either a stuck-at fault, no-fault causing no error, or a technology-specific defect requiring special consideration. The previous work was limited to those defects that map onto single stuck-at faults. The present work addresses the class of technology-specific defects that were not discussed before. Our defect mapping onto an analyzable fault model uses extensions of fault equivalence and fault dominance principles. We model the defects as transition faults whose test generation is supported in the logic-level EDA systems. All such defects require two-pattern tests, except one defect, missing annihilation notch of OR gate, that needs three patterns. These require test generation for constrained stuck-at fault, generally available in EDA systems. The reported results show that majority of the defects of skyrmionbased circuits can be detected using the proposed test generation approach; few exceptions are defects that map through dominance onto faults rendered redundant due to the circuit structure.

The exponential complexity of automatic test pattern generation (ATPG) necessitates the use of heuristics in making choices during test generation. However, in practice no single heuristic fits all situations. Unsupervised learning can combine any number of known heuristics, such as input-output distance (logic depths), gate type, fanout information, and testability measures like Controllability and Observability Program (COP) and Sandia Controllability/Observability Analysis Program (SCOAP) through principal component (PC) analysis, and then the major PC can guide ATPG choices. This study combines three heuristics, distance, COP, and SCOAP. Some heuristic data are complemented and two major PC are obtained. These PC guide backtrace directions in a PODEM ATPG program. For most circuits, the number of backtracks either matches the best of the three heuristics or is lower than all.

Integrated circuit (IC) testing presents complex problems that, when ICs become large, are exceptionally difficult to solve by traditional computing techniques. To deal with unmanageable time complexity, engineers often rely on human “hunches” and “heuristics” learned through experience. Training machines to adopt these human skills is called machine learning (ML). This survey examines applications of ML to testing analog, digital, memory, radio frequency (RF), and other application based ICs. This survey then highlights significant challenges and potential research directions.

Magnetic skyrmion is an emerging digital technology that provides ultra-high integration density and requires ultralow energy. Skyrmion is a magnetic pattern behaving like a stable pseudoparticle, created by a transverse current injection in ferromagnetic thin film. The state of a logic signal is represented by the presence (logic-1) or absence (logic-0) of a single skyrmion. Patterns on ferromagnetic and metal films form interconnects, called nanotracks, through which electric currents move skyrmions. Because skyrmion-based logic gates (e.g., AND, OR, inverter, and fanout) operate through skyrmion-to-skyrmion interaction, their logic circuit implementation and manufacturing defects differ from those of CMOS circuits. We examine breaks and bridges in nanotrack interconnects, and 19 technology-specific defects in skyrmion gate structures. Simulator MuMax3is used to exhaustively simulate all circuit elements. The results help map each defect onto a fault, modeled in an equivalent logic circuit. A break in a nanotrack interconnect maps onto a single stuck-at fault. Experiments on benchmark circuits demonstrate that tests for all nanotrack breaks can be found using the available ATPG and simulation tools. Others are classified as technology-specific defects. For example, a bridge between two nanotracks results in simultaneous AND and OR functions on respective nanotracks. A variety of technology-dependent faults are identified for future research.

This study examines machine intelligence's (MI) ability to enhance automatic test pattern generation (ATPG) by reducing backtracks. In lieu of a conventional heuristic to decide backtracing directions, this study uses an artificial neural network (ANN) trained through PODEM on hard-to-detect faults. Training data contains topological data, testability measures, and backtracking history, and when trained on this data, the ANN guides backtracing in directions unlikely to backtrack. When trained with a single feature (e.g., COP), ATPG performance is comparable to conventional PODEM, and using multiple features further reduces backtracks and ATPG CPU time.

This article surveys test point (TP) architectures and test point insertion (TPI) methods for increasing pseudo-random and logic built-in self-test (LBIST) fault coverage. We present a history of TPI approaches, including TPI for increasing stuck-at fault coverage, compressing test patterns, detecting path delay faults, and reducing test power. We discuss some known weaknesses of TPs and explore research directions to overcome them.

This article presents methods of increasing logic built-in self-test (LBIST) delay fault coverage using artificial neural networks (ANNs) to selecting test point (TP) locations a method to train ANNs using randomly generated circuits. This method increases delay test quality both during and after manufacturing. This article also trains ANNs without relying on valuable third-party intellectual property (IP) circuits. Results show higher-quality TPs are selected in significantly reduced CPU time and third-party IP is not be required for ANN training.

This article presents a brief survey of digital delay fault testing, which lists 100+ references on fault models, simulators, ATPG, DFT, and tools. Continuing studies are needed in this maturing field for new technologies, signal integrity, process variations, faster than critical path operation, asynchronous circuits, counterfeit ICs, and hardware Trojans. This information is compiled to provide direction to students, practicing engineers, and researchers alike.

Due to globalization of semiconductor manufacturing, appearance of malicious circuitry known as hardware Trojan is now a recognized security threat. A Trojan may be added to the verified netlist without the knowledge of the designer or user causing unexpected malfunction or data theft when the device is in use. In this research we devise tests that would detect a Trojan in a manufactured chip. We recognize that a Trojan must escape manufacturing tests provided with the netlist by the designer. Based on the two parts of a Trojan, namely, a trigger derived as a Boolean function of any set of signals and a payload (typically, an XOR gate) inserted on a signal line, we develop a test generation model. A single-line trigger combined with a single payload line gives a set of 2K × (K - 1) Trojans in this model for a circuit with K signal lines. Tests for these are shown to be vectors that detect “conditional stuck-at” faults, for which we give a test generation algorithm using standard ATPG tools. The model allows us to define and measure a Trojan coverage metric for tests. Results show scalability of these tests, besides being more effective in detecting real Trojans than N-detect stuck-at test vectors or random vectors.

IEEE 1687-2014 Standard provides an effective method for accessing on-chip instruments for testing, debugging and board configuration. The standard, however, causes a safety problem because anyone can access the chip instruments, set inputs and obtain safety critical information. In recent work, a lock in the segment insertion bit (SIB) and a corresponding unlocking key application procedure have been proposed for securing the 1687. This paper provides a linear feedback shift register (LFSR) based key generation mechanism that enhances the security of 1687 very significantly. By reconfiguring m (a small number) scan flip-flops into an LFSR that generates the key to unlock the SIB, we show a substantial increase in the expected break-in time.

Based on a recent pre-bond TSV probing technique, this paper proposes an iterative greedy procedure to sort the order of test sessions for reducing pre-bond TSV test time. We then combine that session sorting procedure with two existing methods to develop a 3-Step test time Optimization Simulator named “SOS3”. SOS3 consists of an ILP (integer linear programming) model for session generation, the greedy procedure for session sorting, and a TSV identification algorithm for early test termination. Experiments are done for various TSV networks and two observations are made. First, session sorting plays an important role within SOS3 as it helps to further reduce pre-bond test time expectation and thus reduces pre-bond TSV test cost. Second, SOS3 as a framework greatly speeds up the pre-bond TSV test.

A method of testing for parametric faults in analog circuits based on a polynomial representation of fault-free function of the circuit is presented. The response of the circuit under test (CUT) is estimated as a polynomial in the root mean square (RMS) magnitude of the applied input voltage at a relevant frequency or DC. The test then classifies the CUT as fault-free or faulty based upon a comparison of the estimated polynomial coefficients with those of the fault-free circuit. The test application needs very little augmentation of the circuit to make it testable as only output parameters are used for classification. The method is validated on an active elliptic filter and is shown to uncover parametric faults causing deviations as small as 5% from nominal values. Fault diagnosis based upon sensitivity of polynomial coefficients at relevant frequencies is discussed. Another type of circuit signatures in the form of probability moments of the output when test input is random noise are also proposed. It is shown that the sensitivity of either signature can be enhanced by a newly proposed nonlinear V-transform. Finally, an adaptive test framework leveraging from these signatures and the transform technique is shown to improve defect level and yield loss.

A conventional wafer sort test on an automatic test equipment (ATE) uses a fixed synchronous clock period. Typical test cycles may produce high signal activity and to keep the power dissipation under control, a relatively slow test clock is used. This results in long test times, especially for large scan based circuits. Observing that each test clock cycle may consume different amount of power, we propose an asynchronous clock test methodology to reduce the test time. Smallest customized clock periods for test cycles or sets of cycles are computed based on power and critical path constraints. A theoretical analysis shows that the total energy consumed by the entire test is invariant and the test time depends on the rate it is dissipated during test. An asynchronous clock test dissipates this energy at the maximum allowable rate, while the conventional synchronous clock test dissipates it at a lower average rate. The asynchronous clock test method is first implemented in simulation using several ISCAS'89 benchmark circuits. These results show test time reductions up to 47%. To establish the test programming feasibility of the new methodology the Advantest T2000GS ATE at Auburn University Test Lab was used. Test time reduction of 38% is demonstrated for scan test of a circuit. The paper ends with an investigation showing that for a circuit under test, given its power budget and a test there exists a supply voltage that minimizes the test time. An analysis determines whether the shortest test must use a synchronous or an asynchronous clock.

Reducing test cost by minimizing the overall test time remains one of the main goals of System-on-Chip (SoC) testing. Power-aware strategies optimize the overall test time of a SoC for a global peak power budget. Test time and test power can be regulated by VDDand test clock frequency to optimize SoC test schedules for a given power budget. Dynamic voltage and frequency scaling (DVFS) techniques have been used in the past to optimize energy efficiency in SoCs. In this paper, we extend the concept of DVFS to optimize the test scheduling of SoC. We adopt a sessionless test scheduling strategy and provide a simple heuristic approach for its optimization. The proposed idea is implemented on several ITC02 benchmarks. Results show significant test time reduction over sessionless reference test schedules for which VDDand clock frequency are fixed at nominal values.

In a digital test, supply voltage (VDD), clock frequency (ftest), peak power (PMAX) and test time (TT) are related parameters. For a given limit PMAX= PMAX func, normally set by functional specification, we find the optimum VDD= VDDoptand ftest= foptto minimize TT. A solution is derived analytically from the technology-dependent characterization of semiconductor devices. It is shown that at VDDoptthe peak power any test cycle consumes just equals PMAX funcand ftestis fastest that the critical path at VDDoptwill allow. The paper demonstrates how test parameters can be obtained numerically from MATLAB, or experimentally by bench test equipment like National Instruments' ELVIS. This optimization can cut the test time of ISCAS'89 benchmarks in 180nm CMOS into half.

In recent years, a number of high level applications have been reported to be tolerant to errors resulting from a sizable fraction of all single stuck-at faults in hardware. Production testing of devices targeted towards such applications calls for a test vector set that is tailored to maximize the coverage of faults that lead to functionally malignant errors while minimizing the coverage of faults that produce functionally benign errors. Given a partitioning of the fault set as benign and malignant, and a complete test vector set that covers all faults, in this paper, we formulate an integer linear programming (ILP) problem to find an optimal test vector set that ensures 100% coverage of malignant faults and minimizes coverage of benign faults.We also propose a test strategy based on selectively masking appropriate outputs of the circuit to partition the circuits at production test into three bins - malignant, benign, and fault-free. As a case study, we demonstrate the proposed ILP based test optimization and functional binning on three adder circuits: 16-bit ripple carry adder, 16-bit carry lookahead adder, and 16-bit carry select adder. We find that the proposed ILP based optimization gives a reduction of about 90% in fault coverage of benign faults while ensuring 100% coverage of malignant faults. This typically translates to an (early manufacturing) yield improvement of over 20% over what would have been the yield if both malignant and benign faults are targeted without distinction by the test vectorset.

Manufacturing process variations (PV) of transistors in the deep-submicron regime present the single biggest design challenge for large die size VLSI circuits such as processor arrays, GPUs, and FPGAs. However, there are a few applications in signal processing, such as image processing, and speech processing, where errors in computation by the underlying hardware could be tolerated or corrected off-line with readily available image restoration algorithms. In this paper, we qualitatively and quantitatively evaluate the effect of process variation in the underlying hardware (for different technology nodes) on a high level application program such as image processing. We rely on gate level simulation, of the data-path of an image processor comprising of a dedicated multiply-accumulate (MAC) array of size 256 × 256, with individual gate delays of the processor sampled from a delay distribution as appropriate for each technology node. Our results show that processing images with PV degraded hardware in technologies beyond 65nm is discernible to the human eye; image quality degrades further at 45nm, and is of unacceptable quality at 32nm and beyond. We also use image restoration algorithms to restore the images corrupted due to processing on PV degraded hardware. Our results show that with standard restoration algorithms, even images processed with high levels of PV (as in 32nm) can be restored to almost the same quality as the image processed on fault-free hardware.

Computing with large die-size graphical processors (that need huge arrays of identical structures) in the late CMOS era is abounding with challenges due to spatial non-idealities arising from chip-to-chip and within-chip variation of MOSFET threshold voltage. In this paper, we propose a machine learning based software-framework for in-situ prediction and correction of computation corrupted due to threshold voltage variation of transistors. Based on semi-supervised training imparted to a fully connected cascade feed-forward neural network (FCCFF-NN), the NN makes an accurate prediction of the underlying hardware, creating a spatial map of faulty processing elements (PE). The faulty elements identified by the NN are avoided in future computing. Further, any transient faults occurring over and above these spatial faults are tracked, and corrected if the number of PEs involved in a particle strike is above a preset threshold. For the purposes of experimental validation, we consider a 256 × 256 array of PE. Each PE is comprised of a multiply-accumulate (MAC) block with three 8 bit registers (two for inputs and one for storing the computed result). One thousand instances of this processor array are created and PEs in each instance are randomly perturbed with threshold voltage variation. Common image processing operations such as low pass filtering and edge enhancement are performed on each of these 1000 instances. A fraction of these images (about 10%) is used to train the NN for spatial non-idealities. Based on this training, the NN is able to accurately predict the spatial extremities in 95% of all the remaining 90% of the cases. The proposed NN based error tolerance results in superior quality images whose degradation is no longer visually perceptible.

Given the test output from a defective digital circuit, we identify one or more faulty signal nets that may have caused the observed output results. Although we make no assumption about the actual defect, our diagnosis is based upon a dictionary pre-generated by simulating the test vectors for their detection of collapsed single stuck-at and transition faults at each primary output. First, novel three-stage candidate filtering system and candidate ranking system are proposed to reduce and rank candidate faults. A more balanced ranking method compared to previous works and a ranking strategy which combined both overall and per-test performance together are used in these two systems. Then, the ranked candidate list is expanded by uncollapsing faults. A rank for every candidate net is calculated based on the number of top-ranked suspected faults on it. Experiments were conducted by injecting multiple stuck-at or transition delay faults on either single or double nets in certain ISCAS85 circuit. When tests generated by targeting single stuck-at and transition faults were used, our diagnosis algorithm shows good diagnosability and resolution in identifying single and double faulty nets.

The function of a circuit under test (CUT) is represented as a transformation on the probability density function of its input excitation, which is a continuous random variable (RV) with Gaussian probability distribution. Probability moments of the output, now a transformed RV, are used as metrics for testing catastrophic and parametric faults in circuit components. The proposed use of probability moments as test metrics with white noise excitation as input addresses three important problems of analog circuit test, namely, it 1) reduces complexity of input signal design, 2) increases resolution of fault detection, and 3) reduces production test cost as it has no area overhead and may even marginally reduce the test time. We also propose a method to diagnose circuit elements with catastrophic faults based on unique relationships between specific moments of the output and circuit elements. We present a theoretical framework, test and diagnosis procedures and SPICE simulation results for a benchmark elliptic filter and a low noise amplifier. We are able to detect all catastrophic faults and single components that deviate from their nominal values by just over 10%. We diagnose all catastrophic faults in the example circuits.

To distinguish between a pair of transition faults, we need to find a test vector pair (LOC or LOS type)that produces different output responses for the two faults. By adding a few logic gates and one modeling flip-flop to the circuit under test (CUT), we create a diagnostic ATPG model usable by a conventional single stuck-at fault test pattern generator. Given a transition fault pair, this ATPG model either finds a distinguishing test or proves the faults to be equivalent. An efficient diagnostic fault simulator is devised to find undistinguishable fault pairs from a fault list by a test vector set. The number of fault pairs that needs to be targeted by the ATPG is greatly reduced after diagnostic fault simulation. We use a previously proposed diagnostic coverage (DC) metric to determine the distinguishability (diagnosability) of a test vector set. Experimental results show improved DC for benchmark circuits after applying the proposed diagnostic ATPG algorithms.

ATPG tool generated patterns are a major component of test data for large SOCs. With increasing sizes of chips, higher integration involving IP cores and the need for patterns targeting multiple fault models for better defect coverage in newer technologies, the issues of adequate coverage and reasonable test data volume and application time dominate the economics of test. We address the problem of generating compact set of test patterns across multiple fault models. Traditional approaches use separate ATPG for each fault models and minimize patterns either during pattern generation through static or dynamic compaction, or after pattern generation by simulating all patterns over all fault models for static compaction. We propose a novel ATPG technique where all fault models of interest are concurrently targeted in a single ATPG run. Patterns are generated in small intervals, each consisting of 16, 32 or 64 patterns. In each interval fault model specific ATPG setups generate separate pattern sets for their respective fault model. An effectiveness criterion then selects exactly one of those pattern sets. The selected set covers untargeted faults that would have required the most additional patterns. Pattern generation intervals are repeated until required coverage for faults of all models of interest is achieved. The sum total of all selected interval pattern sets is the overall test set for the DUT. Experiments on industrial circuits show pattern count reductions of 21% to 68%. The technique is independent of any special ATPG tool or scan compression technique and requires no change or additional support in an existing ATPG system.

We dynamically monitor per cycle scan activity to speed up the scan clock for low activity cycles without exceeding the specified peak power budget. The activity monitor is implemented either as on-chip hardware or through pre-simulated and stored test data. In either case a handshake protocol controls the rate of test data flow between the automatic test equipment (ATE) and device under test (DUT). The test time reduction accomplished depends upon an average activity factor α. For low α, about 50% test time reduction is analytically shown. With moderate activity, α = 0.5, simulated test data gives about 25% test time reduction for ITC02 benchmarks. For full scan s38584, the dynamic scan clock control reduced the test time by 19% when fully specified ATPG vectors were used and by 43% for vectors with don't cares. BIST with dynamic clock showed about 19% test time reduction for the largest ISCAS89 circuits in which the hardware activity monitor and scan clock control required about 2-3% hardware overhead.

Parametric fault testing of non-linear analog circuits based on a new mathematical transform is presented. The V-Transform acts on the polynomial expansion of the circuit's function. Its main properties are: 1) to make the polynomial coefficients monotonic, 2) to reduce masking of parametric faults due to process variation, and 3) to increase the sensitivity of polynomial coefficients to the circuit parameter variation, thus enhancing diagnostic resolution. We show that the sensitivity of V-Transform Coefficients (VTC) with respect to circuit parameter variation is up to 3 to 5 times greater than the sensitivity of polynomial coefficients. Fault diagnosis of parametric faults under process variation using VTC is then presented. We also propose a scheme to distinguish between circuit specifications failures due to process variation versus manufacturing defects which manifest as parametric faults. To validate our approach, we apply the test and diagnosis procedures to a benchmark fifth order elliptic filter. We use SPICE program for fault injection, with about 50,000 Monte Carlo simulation runs to demonstrate fault detection-diagnosis under process variation. The test scheme uncovers 95% of all injected single parametric faults whose sizes deviate 5% from the nominal values of circuit components corrected for process variation, while the procedure successfully diagnosed all component faults under ±3σ process variation with 88% confidence level.

A diagnostic automatic test pattern generation (DATPG) system is constructed by adding new algorithmic capabilities to conventional ATPG and fault simulation programs. The system generates tests to distinguish between fault pairs through different output responses. Given a fault pair, by modifying circuit netlist a new single fault is modeled and targeted for detection by a conventional ATPG. The test distinguishes the given fault pair. In the fault simulator faults are partitioned into different groups according to their output responses. Thus, fault pairs that a simulated vector can distinguish between are split among separate groups. Faults that form single-fault groups are dropped from further simulation. Using a proposed diagnostic coverage (DC) metric, we observe improved DC in most benchmark circuits. Cases of low DC have helped identify new open problems.

A diagnostic automatic test pattern generation (DATPG) system is constructed by adding new algorithmic capabilities to conventional ATPG and fault simulation programs. The DATPG aim to generate tests to distinguish fault pairs, i.e., two faults must have different output responses. Given a fault pair, by modifying circuit netlist a new single fault is modeled. Then we use a conventional ATPG to target that fault. If a test is generated it distinguishes the given fault pair. A fast diagnostic fault simulation algorithm is implemented to find undistinguished fault pairs from a fault list for a given test vector set. We use a proposed diagnostic coverage (DC) metric, defined as the ratio of the number of fault groups to the number of total faults. The diagnostic ATPG system starts by first generating conventional fault coverage vectors. Those vectors are then simulated to determine the DC, followed by repeated applications of diagnostic test generation and simulation. We observe improved DC in all benchmark circuits.

Circuit dependent vectors like functional verification vectors, RTL test vectors, or gate-level ATPG vectors contain circuit specific information in the form of spatial correlations (among bits of a vector) and temporal correlations (among bits of the bit stream at an input pin). Some specified bits have don't care behavior because they can be changed without affecting the relevant (testing or functional) properties of the signal. In this paper, we develop a functional analysis framework for digital signals which extracts this information content from the vectors under consideration. Our proposed method is based on spectral analysis of binary bit-streams using Hadamard transform. A bit-stream corresponding to an input pin is transformed to Hadamard spectral components. The information content is distinguished from the noise in the signal using spectral analysis of random binary bit-streams. The magnitude of the spectral components represent temporal correlations while the phases of spectral components of separate bit streams represent the spatial correlations. Applications to ATPG, test compression and BIST (combinational and sequential), as described in recent publications, will benefit from this analysis, because the previous works have used ad-hoc methods for extracting spectral components from samples of test signals. We illustrate the analysis with an application to test generation for sequential benchmark circuits.

A method of testing for parametric faults of analog circuits based on a polynomial representation of fault-free function of the circuit is presented. The response of the circuit under test (CUT) is estimated as a polynomial in the applied input voltage at relevant frequencies in addition to DC. Classification of CUT is based on a comparison of the estimated polynomial coefficients with those of the fault free circuit. This testing method requires no design for test hardware as might be added to the circuit by some other methods. The proposed method is illustrated for a benchmark elliptic filter. It is shown to uncover several parametric faults causing deviations as small as 5% from the nominal values.

We optimize the full-response diagnostic fault dictionary from a given test set. The smallest set of vectors is selected without loss of diagnostic resolution of the given test set. We give an integer linear program (ILP) formulation using a fault diagnostic table. The complexity of the ILP is made manageable by two innovations. First, we define generalized fault independence. This property identifies many fault pairs that are guaranteed to be distinguished, significantly reducing the number of ILP constraints. Second, we propose a two-phase ILP approach. An initial phase, which uses existing procedures, selects a minimal detection test set. In a final phase, additional tests are then selected for the undiagnosed faults using a new diagnostic ILP. The overall minimized test set may be only slightly longer than that obtained from a one-step ILP optimization, but has advantages of significantly reduced computation complexity and reduced test time. Benchmark results show potential for very small diagnostic test sets.

Scan circuit generally causes excessive switching activity compared to normal circuit operation. The higher switching activity in turn causes higher peak power supply current which results into supply voltage droop and eventually yield loss. This paper proposes an efficient methodology for test vector re-ordering to achieve minimum peak power supported by the given test vector set. The proposed methodology also minimizes average power under the minimum peak power constraint. A methodology to further reduce the peak power, below the minimum supported peak power, by inclusion of minimum additional vectors is also discussed. The paper defines the lower bound on peak power for a given test set. The results on several benchmarks shows that it can reduce peak power by up to 27%.

DC testing of parametric faults in non-linear analog circuits based on polynomial approximation of the functionality of fault free circuit is presented. Classification of circuit under test (CUT) is based on comparison of estimates of polynomial coefficients with those of the fault free circuit. The method needs very little augmentation of circuit to make it testable as only output parameters are used for classification. Possible fault diagnosis using the proposed method in conjunction with sensitivity of polynomial coefficients is also presented.

Nanoscale system-on-chip (SoC) devices offer potential for higher performance and reduced power consumption at lower cost. However yield and reliability of mixed-signal components in such devices become serious issues due to process variability. In this paper, we discuss a novel variation-tolerant technique for non-linearity errors in self-correctable mixed-signal components. We propose a completely digital method of test and correction of digital-to-analog and analog-to-digital converters (DAC/ADC) using a digital signal processor (DSP) assumed to be available on the SoC. The added hardware includes a first-order sigma-delta ADC for measurement and a low-resolution dithering DAC for correction of output. The DSP handles test pattern generation (TPG) and output response analysis (ORA) and a third-order polynomial fitting algorithm is employed to characterize the nonlinearity error. Simulation results demonstrate a reduction in nonlinearity errors of converters from plusmn1.5LSB down to plusmn0.5LSB. Our technique can also be applied to other mixed-signal devices with digital control.

Scan based timing comparison tests offer a potential solution to the problem of small delay detection in aggressive nanometer technologies. However, such tests require that circuit delays be unambiguously captured in the scan chains using multiple fast clocks. To ensure this, only those signals that are known to be hazard free at capture are analysed for timing information from the scan-out data. In this paper we present the first systematic ATPG driven approach for generating high coverage output hazard free TDF tests for scan delay testing. Results indicate that acceptable coverage can be achieved, no worse than about 10% below the unconstrained TDF coverage for both LOS and LOC tests, even in the presence of significant process variations.

We propose a new complementary metal-oxide semiconductor (CMOS) gate design that has different delays along various input to output paths within the gate. The delays are accomplished by inserting selectively sized ldquopermanently onrdquo series transistors at the inputs of a logic gate. We demonstrate the use of the variable input delay CMOS gates for a totally glitch-free minimum dynamic power implementations of digital circuits. Applying a linear programming method to the c7552 benchmark circuit and using the gates described in this paper, we obtained a power saving of 58% over an unoptimized design. This power consumption was 18% lower than that for an alternative low power design using conventional CMOS gates. The optimized circuits had the same critical path delays as their original unoptimized versions. Since the overall delay was not allowed to increase, the glitch elimination with conventional gates required insertion of delay buffers on noncritical paths. The use of the variable input delay gates drastically reduced the required number of delay buffers.

ATPG patterns of a digital sequential circuit contain temporally and spatially ordered bits as well as random (or donpsilat care) bits. We synthesize BIST hardware that mimics these characteristics by controlled mixing of spectral components and noise. A Hadamard digital wave generator circuit produces all required spectral sequences and a weighted pseudorandom bit generator provides random bits. While these two blocks serve the entire circuit under test, specific to each primary input are two small blocks, one that combines the required Hadamard sequences in proper proportions and the other a randomizer that adds the required amount of noise if necessary. As an example, the FlexTest ATPG produced 55110 patterns for s38417, detecting 15472 of 31180 stuck-at faults. Sixty four-thousand of our BIST patterns detected 17020 faults as compared to 4244 detected by a previously reported spectral BIST method utilizing similar hardware overhead.

Both average power and peak power specifications of a circuit pose serious problems for the prevalent test methods like scan and built-in self-test. This tutorial discusses the problems and solutions for minimizing power dissipation in these test procedures. Hardware approaches and test vector optimization methods are outlined. Power-constrained testing of core-based systems is discussed. Finally, an open problem of finding an efficient test for verifying the power specification of a system is formulated.

Linearity measurements are significant for assessing the performance of a modern mixed-signal system-on-chip. In this paper a new built-in self-test (BIST) scheme is presented for testing and calibration of on-chip high-resolution digital-to-analog converters (DACs) and analog-to-digital converters (ADCs) for better linearity using sigma-delta modulator and low-resolution dithering DAC. Ramp signals are used as testing stimuli and responses of DAC-under-test (DUT) are measured by a first-order 1-bit sigma-delta modulator with high oversampling rate (OSR) and a low-pass digital filter for noise cancellation. A polynomial fit algorithm is used to characterize DAC and to obtain calibrating coefficients that determine whether the DUT passes or fails the test. DUT output error is compensated for by a dithering DAC with dynamic element matching (DEM) technique, which is controlled by the calibrating coefficients, to reduce the integral non-linearity (INL) error. Simulation results show that a sigma-delta modulator with effective number of bits (ENOB) equivalent to 17-bit ADC and a 6-bit low-cost dithering DAC are sufficient to calibrate a 14-bit high-resolution on-chip DAC such that the maximum INL error is reduced from 3 LSB to approximate 0.25 LSB. Testing and calibration of on-chip ADC using the same scheme is also discussed.

This paper presents a new fault node for implication graph that represents the Boolean detectability status of a fault in the circuit. An implication graph with fault nodes is termed functional fault graph (FFG) because such a graph stores both the functional information and the fault information of the circuit. By computing the transitive closure and graph condensation of the FFG of a circuit, we show that we can collapse faults, and identify untestable faults and independent fault pairs in the circuit. Compared to prior fault independent-based approaches for fault collapsing, our technique gives the best result by reducing the fault-set size by 66%. Additional advantages of our technique compared to previous techniques are: a) It can also identify independent fault pairs in the circuit, and b) It can be extended for other fault models and has a variety of applications. Our experiment with c7552 also found more than 268 K independent fault pairs. This work also introduces the first fault-independent polynomial-time approach for identifying untestable transition delay faults.

Stuck fault coverage estimation for sequential circuits relies on a time expansion model, where combinational techniques are employed for each time-frame. Faults that are hard to detect and require a particular sequence of states are often incorrectly estimated to be detected. This problem is more evident for designs that exhibit low coverage either due to low testability or insufficient vectors that fail to exercise the required sequence of states. This paper illustrates how a simple state traversal analysis can mitigate this problem. For circuits with large number of sequential elements, we propose an entropy based technique that collapses the state graph to be analyzed. Experimental results for larger ISCAS benchmarks show that this technique reduces the coverage estimation error by as much as 50%.

Previously reported work on path and gate delay tests fail to analyze path reconvergences when a bounded gate delay model is used. While robust path delay tests are of the highest quality, most path faults are only testable nonrobustly. Many non-robust tests are usually found but, in practice, are easily invalidated by hazards. The invalidation of non-robust tests occurs primarily due to non-zero delays of off-path circuit elements that may reconverge. Thus, non-robust tests are of limited value when process variations cause gate delays to vary. For gate delay faults, failure to recognize the correlations among the ambiguity waveforms at inputs of reconvergent gates cause fault coverages to be optimistic. This paper enhances a recently published ambiguity simulation algorithm [5] to accurately measure both non-robust path and gate delay coverages for the bounded delay model. Experimental results for the ISCAS circuits show accurate results are often 20-30% less than the optimistic ones that fail to analyze signal reconvergences.

We propose a new partial-scan algorithm, the first to use toggling rates of the flip-flops (analyzed using DSP methods) and Shannon entropy measures of flip-flops to select flip-flops for scan. This improves the testability of the circuit-under-test (CUT). Entropy is maximized throughout the circuit to maximize the information flow (the principle of maximum entropy), which improves testability. We propose using partial-scan for testing, to maximize fault coverage (FC), reduce test volume (TV), reduce test application time (TAT), and reduce test power (TP) but we allow for full-scan during silicon debug. Full-scan is commonly used for testing, to reduce sequential automatic test-pattern generation (ATPG) to the complexity of combinational ATPG, but comes with serious TV, TAT, and TP overheads. Partial-scan significantly reduces circuit delay, when compared to full-scan, because critical flip-flops in the circuit data path do not have the extra hardware for full-scan, and therefore are roughly 5% faster, and use 10% less area. This is particularly critical for microprocessors. The HITEC ATPG program generated results for this new partial-scan algorithm.

Conventionally, path delay tests are derived in a delay-independent manner, which causes most faults to be robustly untestable. Many non-robust tests are invalidated by hazards caused primarily due to non-zero delays of off-path circuit elements. Thus, non-robust tests are of limited value when process variations change gate delays. The authors propose a bounded gate delay model for test quality evaluation and give a novel simulation algorithm that is less pessimistic than previous approaches. The key idea is that certain time-correlations among the multiple transitions at the inputs of a gate cannot cause hazard at its output. The authors maintain "ambiguity lists" for gates. These are propagated with events, similar to fault lists in a traditional concurrent fault simulation. They are used to suppress erroneous unknown states. Experimental results for ISCAS benchmarks with gate delay variation of plusmn14% show a miscorrelation of critical path delay as much as 20%.

We propose a new IDDQtesting signature, the graphical IDDQsignature. We discovered that noise, in the entire set of current measurements for a chip, is a vastly superior feature for classifying chips as good or bad, compared to present methods. The measured IDDQcurrent as a function of vectors is defined here as the signature. We examine the shape of the waveform defined by the total set of the IDDQmeasurements, to extract the number of bands that all of the current measurements cluster into, the width and separation of the bands and current glitches or noise among all IDDQmeasurements. We examined the IDDQsignatures of all SEMATECH experiment chips that were classified as good or bad by a combination of functional, delay, and scan voltage tests. A single IDDQthreshold, whether absolute or differential, cannot separate good/bad chips reliably. Good chip signatures contain discrete levels (or bands) of varying widths and separations. A faulty chip almost always displays noise and glitches in the band structure. The graphical IDDQclassifier shows very high accuracy for SEMATECH test data with a test escape rate of 5.97%, compared with 7.5% for the single threshold method, 7.6% for current differences and 7.5% for the DeltaIDDQmethod. The graphical IDDQmethod had a 1.2% test overkill, compared with 2.3% for the single threshold method, 6.1% for current differences and 7.0% for DeltaIDDQ.

We model RTL faults as stuck-at faults on primary inputs, primary outputs, and flip-flops. Tests for these faults are analyzed using Hadamard matrices for Walsh functions and random noise level at each primary input. This information then helps generate vector sequences. At the gate-level, a fault simulator and an integer linear program (ILP) compact the test sequences. We give results for four ITC'99 and four ISC AS'89 benchmark circuits, and an experimental processor. The RTL spectral vectors performed equally well on multiple gate-level implementations. Compared to a gate-level ATPG, RTL vectors produced similar or higher coverage in shorter CPU times

Literature proposes linear programming (LP) methods for glitch-less design of digital circuits. Considering the worst-case these methods ensure absence of glitches for any arbitrary state of primary input as well as internal signals. In this paper, we examine an unexplored aspect, i.e., glitch-free design with respect to a specific set of vectors (patterns). Introducing the logic-level concepts of glitch-generation patterns and glitch-generation probability, which are analyzable through logic simulation, we remove glitch filtering requirements from gates on which the given set of input vectors cannot produce glitches. We relax constraints of any existing LP either selectively or probabilistically. Such input-specific design from an LP model without process variation and another with process variation reduced the number of delay buffer overhead by up to 80% and 63%, respectively, while maintaining the power reduction and overall delay.

Statistical stuck-at fault coverage estimation assumes that signals at primary inputs and at other internal gates of the circuit are statistically independent. While valid for random and pseudo-random inputs, this causes substantial errors in coverage estimation for input sequences that are functional and not random, as shown by experimental data presented in this paper. At internal gates, signal correlation due to fanout reconvergence, even for random input sequences, contributes to errors. A significantly improved coverage estimation algorithm is presented in this paper. First, during logic simulation we identify faults that are guaranteed to stay undetected by the applied vectors. Then, after logic simulation, we estimate the detection probabilities of the remaining faults. Compared to Stafan, the statistics gathered during logic simulation are modified in order to eliminate the non-random biasing of the input sequence. Besides the improved detection probabilities, a newly defined effective length (Neff) of the vector sequence corrects for the temporally correlated signals. Experimental results for ISCAS combinational benchmarks demonstrate validity of this approach

A new algorithm for identifying stuck faults in combinational circuits that cannot be detected by a given input sequence is presented. Other than pre and post-processing steps, certain signal conditions are monitored during logic simulation. These signal conditions are specified by an analysis of dominators and signal reconvergences in the circuit graph. After simulation, a post-processing step identifies faults that cannot be detected by the sequence. For combinational IS GAS benchmarks, the runtime overhead for the algorithm is found to be around 30-40% over that of a logic simulator. Experimental data show a substantial reduction of error in statistical estimates obtained by a stuck-fault coverage estimator when corrected for faults found by this algorithm as guaranteed to be undetected by the given sequence. An effective application of this technique is demonstrated for scan-based test point selection in an industrial scenario where circuit size and vector length prohibit the use of fault simulation

We define a new type of test, called "concurrent test," for a combinational circuit. Given a set of target faults, a concurrent-test is an input vector that detects all (or most) faults in the set. When concurrent tests are generated for fault sets obtained from independence fault collapsing, minimal or near-minimal tests can be expected. This paper gives new simulation-based methods for independence fault collapsing and for deriving concurrent tests using single-fault ATPG.

We discuss fault equivalence and dominance relations for multiple output combinational circuits. The conventional definition for equivalence says that "two faults are equivalent if and only if the corresponding faulty circuits have identical output functions". This definition, which is based on indistinguishability of the faults, is extended for multiple output circuits as "two faults of a Boolean circuit are equivalent if and only if the pair of the output functions is identical at each output of the circuit". This is termed as diagnostic equivalence in this paper. "If all tests that detect a fault also detect another fault, not necessarily on the same output, then the two faults are called detection equivalent". Two detection equivalent faults need not be indistinguishable. The definitions for fault dominance follow on similar lines. A novel algorithm based on redundancy identification has been proposed to find the equivalence and dominance collapsed sets based on diagnostic and detection collapsing. Applying the algorithm to a 4-bit ALU would collapse the total fault set of 502 faults to 253 and 155, respectively, according to diagnostic equivalence and dominance. The collapsed sets have 234 and 92 faults, respectively, for detection equivalence and dominance. In comparison, the traditional structural equivalence and dominance collapsing results in 301 and 248 faults, respectively. Finally, we use library-based functional collapsing in a hierarchical system and find that smaller fault sets are obtained with an order of magnitude reduction in CPU time for very large circuits.

Existing gate-level probabilistic approaches to power estimation fail to accurately model the glitch filtering by inertial delays. This effect has an impact on the power dissipation of a circuit and should not be neglected, especially for dynamic power estimation of circuits with dynamic power optimization. We propose a new glitch filtering analysis using the dual-transition probability that captures the states of a node at two different time instances. Experiments show that probabilistic simulation and the tagged probability simulation (TPS) techniques, when enhanced by the dual-transition analysis, provide more consistent power estimation. For circuits with a large component of glitch power, up to 29 % improvement in the estimation accuracy is obtained.

Consideration of pairs of transition in probabilistic simulation allows power estimation for digital circuits in which inertial delays can filter glitches (Hu and Agrawal, 2005). However, the merit of the method is not fully realized because of the way probabilistic simulation approximates spatial correlations of signals in the presence of delays. In this paper, we use supergate partitions (enclosing reconvergent fanouts) and timed Boolean functions (TBF) to obtain the dual-transition probabilities that correctly deal with glitches and filtering as they affect power estimation. Experimental results on ISCAS'85 benchmarks show significant improvements in estimation accuracy as the average estimation error on total power consumption remains under 5%.

In this paper we propose architecture for random access scan (RAS) that minimizes the signals to the RAS flip-flops (FF), and provide an estimate of the area overhead. Two global signals, scan-in and mode control, have been eliminated compared to previous RAS designs presented in the literature. For 'n' flip-flops, instead of routing 'n' address wires, one to each FF, we use /spl radic/n wires in an 'x-y' matrix layout. A unique toggle mechanism is introduced in the RAS FF that eliminates the scan-in signal wire and reduces the vector set up time to 60% compared to traditional serial scan (SS). Serial scan induces unnecessary circuit activity during scan that causes the circuit under test (CUT) to dissipate a significant amount of power. Our design reduces this power dissipation by 99%. The problem of delay testing is highly constrained in SS and the scan-cell is often modified to assist delay testing. Any single input change delay test can be directly applied in our design. Hence all testable paths in the circuit can be effectively tested without constraints. We also propose a multistage scan-out system to observe the addressed FF avoiding a slow output bus.

It is known that the complexity of automatic test pattern generation (ATPG) for acyclic sequential circuits is similar to that of combinational ATPG. The general problem, however, requires time-frame expansion and multiple-fault detection and hence does not allow the use of available combinational ATPG programs. The first contribution of this work is a combinational single-fault ATPG method for the most general class of acyclic sequential circuits. Without inserting any real hardware, we create a functionally equivalent "balanced" ATPG model of the circuit in which all reconverging paths have the same sequential depth. Some primary inputs and gates are duplicated in this model, which is converted into a combinational circuit by shorting all flip-flops. A test vector obtained by a combinational ATPG program for a fault in this combinational circuit is transformed into a test sequence to detect a corresponding fault in the original sequential circuit. A combinational ATPG program finds tests for all but a small set of faults that must be explicitly detected as multiple-faults. Those are modeled for ATPG using the second contribution of this work, which is a generalized method to model any given multiple stuck-at fault as a single stuck-at fault. The procedure requires insertion of at most n+3 modeling gates for a fault of multiplicity n. We show that the modeled circuit is functionally equivalent to the original circuit and the targeted multiple fault is equivalent to the modeled single stuck-at fault. Benchmark results show at least an order of magnitude saving in the ATPG CPU time by the new combinational method over sequential ATPG.

A selfish gene (SG) algorithm differs from the genetic algorithm (GA) because it evolves genes (characteristics) that provide higher fitness rather than evolving individuals with higher fitness. We enhance the spectral method of sequential circuit test generation by using a SG algorithm. The objects of evolution are the Hadamard spectral matrix, non-linear digital signal processing (DSP) filtering cutoff values, vector holding time, and relative input phase shifts, which are all modeled as genes. These characteristics, extracted from compacted test vectors, are used to create new vector sequences to be further compacted with higher fault coverage. Alternatively, new vectors were generated by holding randomly selected vectors and then randomly perturbing some bits in 8-bit chunks of bit streams. Both the SG algorithm and holding with bit-perturbation can outperform the previously-published spectral method in either fault coverage, or shorter vector length, or both. The SG algorithm is often superior to random bit-perturbation but it requires more CPU time.

A fault fj is said to dominate another fault fi if all tests for fi detect fj. When two faults dominate each other, they are called equivalent. Dominance and equivalence relations among faults around a Boolean gate are called \structural and are used for fault collapsing in large circuits. Some fault equivalences, that cannot be determined by the structural analysis, can be found by equivalence relations. This paper gives a \functional relation, which has not been described in the literature. Since the functional analysis is computationally expensive, it can only be applied to small circuits such as standard cells. A graph-theoretic hierarchical fault collapsing method from the recent literature can then collapse faults in any large cell-based circuit. It is found that the size of the dominance collapsed set for an exclusive-OR cell reduces to just four faults when functional dominance is considered. With the traditional method of structural collapsing this set contains 13 faults. When the exclusive-OR cell is used to build an 8-bit adder circuit, the size of the dominance collapsed set reduces to 112 faults from a total of 466 faults. Traditional structural dominance collapsing would have given a set of 226 faults. Smaller fault set can lead to more compact tests. Collapsing for the cell-based design of benchmark circuit, c499, reduces a set of 2,710 faults to just 586 faults.

Stratified fault sampling is used in register transfer level (RTL) fault simulation to estimate the gate-level fault coverage of given test patterns. RTL fault modeling and fault-injection algorithms are developed such that the RTL fault list of a module can be treated as a representative fault sample of the collapsed gate-level stuck-at fault set of the module. The RTL coverage for the module is experimentally found to track the gate-level coverage within the statistical error bounds. For a very large scale integration system, consisting of several modules, the level of description may differ from module to module. Therefore, the stratified fault sampling technique is used to determine the overall coverage as a weighted sum of RTL module coverages. Several techniques are proposed to determine these weights, known as stratum weights. For a system timing controller application specific integrated circuit, the stratified RTL coverage of verification test-benches is estimated to be within 0.6% of the actual gate-level coverage of the synthesized circuit. This ASIC consists of 40 modules (consisting of 9000 lines of Verilog hardware description language) that are synthesized into 17,126 equivalent logic gates by a commercial synthesis tool. Similar results on two other systems are reported.

Nodes in a dominance graph represent faults of a circuit. A directed edge from node f/sub i/ to node f/sub j/ means that fault f/sub j/ dominates f/sub i/. The equivalence of faults f/sub i/ and f/sub j/ is indicated by the presence of simultaneous edges f/sub i/ /spl rarr/ f/sub j/ and f/sub j/ /spl rarr/ f/sub i/. When local dominance and equivalence relations are included in this graph, its transitive closure provides the collapsed fault sets. Pre-collapsed fault sets of standard cells and other logic blocks can be stored in a graph library for hierarchical fault collapsing. Examples show how more compact fault sets are obtained by using functional equivalences that can be found by analysis of small cells. Benchmark circuits c432 and c499 are used to illustrate the use of functional fault collapsing within their exclusive-OR cells.

Proposes a new analog coupling delay fault model and analog macromodeling technique to generate tests for these faults. To our knowledge, this is the first time that analog macromodeling, along with multiple-delay sequential digital fault simulation, using differing rise and fall times for digital logic gates, effectively detected coupling timing faults. We propose a new crosstalk candidate reduction (CCR) algorithm, which looks at the entire set of possible signal line couplings and eliminates impossible and uninteresting couplings from the final list. On various circuits, CCR reduced the coupling candidates by 98.1%, on average. The analog macromodels eliminate errors and uncertainty about whether signals actually couple, and also avoid complete analog simulation during fault simulation, as all analog macromodels are precomputed. The analog macromodel is independent of the circuit-under-test, because it models generalized interconnect. The method efficiently handles large circuits with more than 10,000 coupling faults, while obtaining coupling fault coverages in the range of 4 to 10% on sequential circuits, and up to 33% on combinational circuits. These are the first coupling fault results for sequential circuits.

We present a new test generation procedure for sequential circuits using spectral techniques. Iterative processes of filtering via compaction and spectral analysis of the filtered test set are performed for each primary input, extracting inherent spectral information embedded within the test sequence. This information, when viewed in the frequency domain, reveals the characteristics of the input spectrum. The filtered and analyzed set of vectors is then used to predict and generate future vectors. We also developed a fault-dropping technique to speed up the process. We show that very high fault coverages and small vector sets are consistently obtained in short execution times for sequential benchmark circuits.

It is known that a class of acyclic sequential circuits called balanced circuits can be tested by combinational ATPG. The first contribution of this paper is a modified and efficient combinational single fault ATPG method for any general (not necessarily balanced) acyclic circuit. Without inserting real hardware, we create a "balanced" ATPG model of the circuit in which all reconverging paths have the same sequential depth. Some primary inputs are duplicated and each combinational A TPG vector for this model circuit is transformed into a test sequence. Although no time-frame expansion is used, a small set of faults still map onto multiple faults. Those are identified and dealt with again by the single fault combinational A TPG. The results show nearly an order of magnitude or greater saving in the A TPG CPU time over sequential ATPG. The second contribution consists of new partial-scan algorithms to obtain three subclasses of acyclic circuits, namely, internally balanced, balanced, and strongly balanced, which have been described in the literature. Results on ISCAS '89 circuits show that such structures require extra scan overhead, sometimes almost approaching that of full-scan, and their advantages in ATPG are marginal considering the present contribution.

This new method of built-in self-test (BIST) for sequential cores on a system-on-a-chip (SOC) generates test patterns using a real-time program that runs on an embedded processor. Alternatively, the same program can be run on an external low-cost tester. This program generates patterns using circuit-specific spectral information in the form of one or more Hadamard coefficients. The coefficients are extracted from high fault-coverage compacted pattern sets. When an embedded processor is available on SOC, the overhead is negligible. Also, sequential cores are tested in the functional mode, avoiding activation of nonfunctional timing paths. We present experimental results to show that for hard to test circuits, with any given test time, spectral patterns provide significantly higher fault coverage than weighted-random patterns.

In this paper, we propose a new testability metric for path delay faults.The metric is computed efficiently using a non-enumerative algorithm.It has been validated through extensive experiments and the results indicate a strong correlation between the proposed metric and the path delay fault testability of the circuit.We further apply this metric to derive a path delay fault test application scheme for scan-based BIST.The selection of the test scheme is guided by the proposed metric.The experimental results illustrate that the derived test application scheme can achieve a higher path delay fault coverage in scan-based BIST.Because of the effectiveness and efficient computation of this metric, it can be used to derive other design-for-testability techniques for path delay faults.

Presents a new test generation procedure for sequential circuits using newly-traversed state information and newly-detected fault information obtained between successive iterations of vector compaction. Two types of technique are considered. One is based on which new states a sequential circuit is driven into, and the other is based on the new faults that are detected in the circuit between consecutive iterations of vector compaction. These data modify an otherwise random selection of vectors to bias vector sequences that cause the circuit to reach new states and cause previously undetected faults to be detected. The biased vectors, when used to extend the compacted test set, provide an intelligent selection of vectors. The extended test set is then compacted. Repeated applications of state and fault analysis, vector generation and compaction produce significantly high fault coverage using relatively small computing resources. We obtained improvements in terms of higher fault coverage, fewer vectors for the same coverage, or smaller numbers of iterations and time required, consistently for several benchmark circuits.

Accounting for the clustering effect is fundamental to increasing the accuracy of defect level (DL) modeling. This result has long been known in yield modeling but, as far as known, only one DL model directly accounts for it. In this paper we improve this model, reducing its number of parameters from three to two by noticing that multiple faults caused by a single defect can also be modeled as additional clustering. Our result is supported by test data from a real production line.

Stratified fault sampling is used in RTL fault simulation to estimate the gate-level fault coverage of given test patterns. RTL fault modeling and fault injection algorithm are developed such that the RTL fault list of a module can be treated as a representative fault sample of the collapsed stuck-at fault set of the module. The RTL coverage for the module is experimentally found to track the gate-level coverage within the statistical error bounds. For a VLSI system, consisting of several modules, the overall coverage is a weighted sum of RTL module coverages. Several techniques are proposed to determine these weights, known as stratum weights. For a system timing controller ASIC, the stratified RTL coverage of verification test-benches was estimated within 0.6% of the actual gate-level coverage. This ASIC consists of 40 modules (9,000 lines of Verilog HDL) that are synthesized into 17,126 equivalent logic gates by a commercial synthesis tool. Similar results on two other VLSI systems are reported.

A differential algorithm for concurrent simulation of path delay faults in sequential circuits is presented. The simulator analyzes all three conditions, namely, initialization, signal transition propagation through the path, and fault effect observation at a primary output for vector pairs and considers the hazard states occurring between vectors. The main contribution is in methods of propagating signals between time frames. An optimistic method assumes that all nondestination flip-flops are not affected by delays. The pessimistic method converts all nondestination flip-flops with nonsteady values to the unknown state before these values are propagated beyond the time frame in which a path is activated. A 13-valued algebra is shown to improve the efficiency of fault simulation.

We analyze the causes of low path delay fault coverage in synchronous sequential circuits and propose a method to improve testability. The three main reasons for low path delay fault coverage are found to be: (A) combinationally false (nonactivatable) paths; (B) sequentially nonactivatable paths; and (C) unobservable fault effects. Accordingly, we classify undetected faults in Groups A, B, and C. Combinationally false paths ran be made testable by modifying the circuit or resynthesizing the combinational logic as discussed by other researchers. A majority of the untestable faults are, however found in Group B, where a signal transition cannot be functionally propagated through a combinational path. A test requires two successive states necessary to create a signal transition and propagate it through the target path embedded in the sequential circuit. We study a partial scan technique in which flip-flops are scanned to break cycles and shun that a substantial increase in the coverage of path delay faults is possible.

We propose a method of partitioning the set of all flip-flops in a circuit for multiple clock testing. In the multiple clock testing, flip-flops are partitioned into different groups and each group of flip-flops has an independent clock control. In our method, we use a test generator assuming an independent clock control for each flip-flop. We than determine correlation between clock activity for all pairs of flip-flops. This information is then used to an optimal or near optimal partition of flip-flops in the circuit. Through experiments, we demonstrate that our partitioning method increases fault coverage and reduces test length with almost no hardware overhead or performance penalty.

Current code coverage metrics used in high level VLSI design methodology are based on statement, branch, toggle and condition coverages of the HDL code obtained by simulating validation vectors. These measures allow the designer to find sections of the HDL code not executed during validation. Feedback from the code coverage analysis helps generate additional vectors to exercise previously unexercised functionality. In this paper, we explore the relationship between results of RTL code coverage and the gate level fault coverage. Based on the observations of this empirical study we propose a new and improved code coverage metric "Validation Vector Grade (VVG)". The VVG-approach modifies code coverage metrics by adding the concepts of observability and arithmetic fault library. VVG is an improved validation metric, which can also be used for early testability analysis at the RT level. Results of the VVG-approach at RT level are shown to be good indicators of the structural fault coverage. Experiments on actual telecommunication VLSI chip designs show that the VVG reported at the RT level can predict the post-synthesis gate level fault coverage with an error margin less than 4%. Also, the improvements in VVG at the RT level due to high-level design changes or added vectors track improvements in gate level fault coverage.

Some false paths are caused by redundant stuck-at faults. Removal of those stuck-at faults automatically eliminates such false paths from the circuit. However, there are other false paths that are not associated with any redundant stuck-at fault. All links of such a false path are shared with other testable paths. We focus on the elimination of this type of false paths. We use a nonenumerative path delay fault simulator, which duplicates selected gates to separate the detected and undetected path delay faults. The expanded circuit may contain new redundant stuck-at faults, corresponding to those undetected paths that are false. This happens because in the expanded circuit some new links have only false paths passing through them. Such links become the sites for redundant stuck-at faults. Removal of these redundant faults eliminates false paths. The quality of the result may depend on the coverage of testable paths by the vectors that are simulated. Since a non-enumerative path delay simulation and an implication-based redundancy removal technique are used, the present procedure of false-path elimination can be applied to very large circuits.

Signal probability calculation in circuits where signals are not independent is generally expensive. We show that some correlated signals may be mutually disjoint. In such cases, the probability calculation can be as simple as it is for independent signals. For example, two signals that cannot be simultaneously true are defined as OR-disjoint. If these signals feed an OR gate, the probability of the output being true is simply the sum of the probabilities of inputs being true. We give an implication-based algorithm for identifying disjoint signals. Examples of large adders illustrate how the identification of disjoint signals simplifies the probability calculation.

We extend the path status graph (PSG) method of delay fault simulation to sequential circuits. By devising a layered PSG and restricting the number of time-frames over which a fault must be detected, we preserve the non-enumerative nature of the simulation algorithm. The program is capable of simulating a wide variety of circuits (synchronous, asynchronous, multiple-clock and tri-state logic.) Both rated and variable clock modes, as well as robust, non-robust or functional sensitization detection options, are available. The simulation can be stopped and restarted through a check pointing facility. The program can target any given list of paths. This path list can also be generated by the program based on user-selectable criteria (all paths, longest paths, paths between certain I/O pairs, etc.) User reports include a histogram of path coverage versus path length. Detected and undetected path data remain implicit in the PSG and can be retrieved through post-processing commands. Due to its non-enumerative stature, the program can process most production level digital logic circuits.

We explore non-robust untestability of paths based on redundant stuck-at faults. Such untestability classification is necessary for a path to be ignored in timing verification and delay testing. A recent result states that redundant stuck-at-0 (s-a-0) and stuck-at-1 (s-a-1) faults of a line imply untestability of rising and falling delay faults, respectively, for all paths through that line. We find that this result only establishes robust untestability of paths. Starting with known examples, where a non-robust test can exist for some paths that pass through the site of a redundant stuck-at fault, we examine various classes of stuck-at fault redundancies. We prove that: (1) an unexcitable or undrivable redundant s-a-0 (s-a-1) fault will make all paths through the fault site non-robustly delay-untestable for rising (falling) transition, and (2) an unobservable fault site (causing both s-a-0 and s-a-1 faults to be redundant) can only classify the passing paths as robustly delay-untestable, Finally, we show that two singly-untestable paths, passing through the sites of separate redundant single stuck-at faults, may form a multiply-testable pair of paths provided the two redundant single stuck-at faults have a multi-fault test.

We present an algorithm to derive logic systems for various classes of path delay test problems. In these logic systems, the value of a signal represents the relevant conditions that occur during a set of consecutively applied vectors. Starting from a set of basic values for valid signals at primary inputs, a state transition graph is constructed to enumerate all possible signal states relevant to path activation that are reachable by Boolean operations. These states include all incompletely specified states, composed as combinations of basic values. A distinguishability analysis then finds all state-pairs that need to be distinguished during test generation. The final step minimizes the number of states. For forward and backward implications of test generation in combinational or sequential circuits, the procedure provides optimal logic systems. We define optimality as the smallest set of logic states that provides the least possible ambiguity in implications. Thus, an optimal set of logic states will minimize the number of backtracks in test generation. A 10-valued logic described in the literature is found to be optimal for generating tests for single path delay faults. Other problems addressed in this paper include compact test generation through activation of many single path delay faults, test generation for rated-clock test application, and test generation for multiple path delay faults. The limitations and capabilities of various logic systems are illustrated by examples.

We present an efficient path-delay fault (PDF) simulator that does not involve the enumeration of paths. Our method calculates the exact fault coverage, and identifies all tested faults in any circuit with a large number of paths. We present a new data structure, called the path-status graph (PSG), to efficiently hold the status of each PDF in the circuit, i.e., whether or not the PDF is tested. The keg to this efficiency is in breaking the information into pieces and distributing it over the data structure, and in retaining all or part of the reconverging fan-out structure of the circuit in the PSG. Thus, an exponential number of PDF's can share the same piece of information. Using 1000 random tests, we simulated all of the approximately 10/sup 20/ PDF's in the circuit c6288, and determined that 4.4 billion faults were detected. This number is larger by over three orders of magnitude compared to what was possible with previously reported methods.

A new simulation-based method uses single-input change (SIC) vectors to derive tests efficiently for singly testable (ST) path-delay faults (PDFs). A PDF is ST if there exists a delay test that guarantees its detection when it is the only PDF in the circuit. It is known that an ST PDF must have a single-input change test. We utilize this result and present a fault simulator that is specifically tuned to simulate single-input change vectors efficiently. We assign random values to all inputs, and then propagate rising and falling transitions from each input while all other inputs are held steady. We present a 16-valued algebra with which rising and falling PDF's from all inputs are concurrently simulated. Using a suitable encoding for signal values, gates are evaluated directly through Boolean operations, and all computation stages use machine word parallelism. Results on the ISCAS'85 and '89 benchmarks show that the approach is superior to another published method in terms of both fault coverage and execution time.

Current test generation algorithms for path delay faults assume a variable-clock methodology for test application. Two-vector test sequences assume that the combinational logic reaches a steady state following the first vector before the second vector is applied. While such tests may be acceptable for combinational circuits, their use for nonscan sequential circuit testing is impractical. A rated-clock path delay simulator shows a large drop in coverage for vectors obtained from existing test generators that assume a variable clock. A new test generation algorithm provides valid tests for uniform rated-clock test application. In this algorithm, signals are represented for three-vector sequences. The test generation procedure activates a target path from input to output using the three-vector algebra. For an effective backward justification, we derive an optimal 41-valued algebra. This is the first time, rated-clock tests for large circuits are obtained. Results for ISCAS-89 benchmarks show that rated-clock tests cover some longest, or close to longest, paths.

The authors propose a novel algorithm to rapidly identify untestable delay faults using pre-computed static logic implications. The fault-independent analysis identifies large sets of untestable faults, if any, without enumerating them. The cardinalities of these sets are obtained by using a counting algorithm that has quadratic complexity in the number of lines. Since the method is based on an incomplete set of logic implications, it gives only a lower bound on the number of untestable faults. A post-processing step can list the untestable faults, if desired. Targeting untestable delay faults for test generation by an automatic test pattern generation (ATPG) tool can be avoided. The method works for the segment delay fault model and its special case, the path delay fault model, and identifies robustly untestable, non-robustly untestable, and functionally unsensitizable delay faults. Results on benchmark circuits show that many delay faults are identified as untestable in a very short time. For the benchmark circuit c6288, the algorithm identified 1.978/spl times/10/sup 20/ functionally unsensitizable path faults in 3 CPU seconds.

Delay test problems are well understood for gate level circuits. For certain logic families, delays depend on the charge stored at internal nodes. For such circuits, gate level models do not surface, A switch level simulator can be used for logic verification and stuck-at fault simulation. Toward making the delay fault simulation possible, this paper contributes three innovations to the switch-level technique: (1) Signals that remain steady over two consecutive vectors are identified using additional strength designations for charge and discharge paths; (2) Delay faults are propagated through MOS gates using articulation analyse's of the graph; and (3) A modified relaxation procedure determines the steady or non-steady status of signals at the same time it evaluates nodes. Experimental results demonstrate the validity of algorithms.

This paper outlines several problems related to the delay fault testing of sequential circuits. For timing test of a circuit and for layout optimization, critical path data are needed. When critical paths are identified by a static timing analyzer many of the selected paths cannot be activated functionally. Such paths are sequential false paths. However, many of these paths can be activated and tested in the full or partial scan mode due to the increased controllability and observability. Therefore, it is possible that detection of a timing error on a sequential false path, when scan mode is used, can lead to the rejection of a functionally good circuit. We propose that these paths should not be targeted during delay test if scan mode is used. Similarly, sequential false paths should not be used for layout optimization or for selection of maximum clock rate. We present a novel algorithm to identify these paths. This algorithm is based on functional analysis of each target path for single and multiple path activation. If a path cannot be activated either way, it is sequentially false.

We propose a delay test methodology for general sequential circuits. To test a combinational path between two flip-flops, the source flip-flop is initialized to the appropriate value, followed by creation of a transition, which is propagated through the path. An incorrect logic value is captured in the destination flip-flop if the path delay exceeds the clock period. The state of the destination flip-flop is observed at a primary output through path sensitization. Only one vector that propagates the transition through the path is applied with the rated clock period. All other vectors use a slow speed clock to ensure fault-free initialization and fault effect observation. The test generation method uses a 13-value algebra that represents the relevant transition and hazard states of signals. Since several path delay faults can be activated by the vector applied at the rated clock, only the flip-flops with hazard-free steady values are assumed to have deterministic states. This allows us to generate sequentially robust tests. We present the results of the test generation method on ISCAS benchmark circuits.

Production VLSI circuits typically consist of primitives like tristate buffers, bidirectional buffers, and bus configurations that assume non-Boolean values like the high-impedance state. We describe a systematic methodology for extending test generation algorithms that work on combinational circuits with only Boolean primitives to full-scan production circuits. Key features of the methodology are illustrated using the energy minimization based test generation algorithm for combinational circuits. The main features of our methodology that make the test generation algorithm practical for large production circuits are: (1) only one Boolean variable is used to represent the value on a signal and all signals assume only Boolean values during the test generation procedure; (2) the function of non-Boolean primitives is separated into Boolean and non-Boolean components with energy functions required only for the Boolean component; and (3) non-Boolean components are implicitly considered in the energy minimization procedure. In this process, no new energy functions other than the normal Boolean gate energy functions are needed. We give a method for identifying and removing redundancies in production circuits using energy minimization. The formulation is also applicable to Boolean satisfactorily and BDD methods. We first use the test generation algorithm for identifying undetectable faults and then relax specific constraints in the original test generation problem by ignoring the non-Boolean components. We show that undetectability in the relaxed formulation implies redundancy. We report redundancy removal results for production VLSI circuits, ISCAS 85, and full-scan versions of the ISCAS 89 benchmark circuits.

A recently proposed method obtains path delay fault coverages by estimating the count of the number of tested faults instead of actually enumerating them. The estimate becomes pessimistic when several paths share a set of lines. In this communication, we present a continuum of improved approximations for the counting method, approaching exact fault simulation, to allow tradeoffs between accuracy and complexity. Higher accuracy is obtained at the expense of CPU time. We propose the use of flags corresponding to fixed-length path segments. A flag indicates whether or not the segment has been included in a previously detected path fault. A path fault, detected by a pair of vectors, is counted as a new detection only if it includes at least one segment not included in any previously tested path fault. The results show that as the length of segments is increased, the accuracy becomes close to that of the exact fault simulation, even with small segment lengths.

This paper considers the problem of testing VLSI integrated circuits in minimum time without exceeding their power ratings during test. We use a resource graph formulation for the test problem. The solution requires finding a power-constrained schedule of tests. Two formulations of this problem are given as follows: (1) scheduling equal length tests with power constraints and (2) scheduling unequal length tests with power constraints. Optimum solutions are obtained for both formulations. Algorithms consist of four basic steps. First, a test compatibility graph is constructed from the resource graph. Second, the test compatibility graph is used to identify a complete set of time compatible tests with power dissipation information associated with each test. Third, from the set of compatible tests, lists of power compatible tests are extracted. Finally, a minimum cover table approach is used to find an optimum schedule of power compatible tests.

We analyze all signals of a combinational circuit simultaneously for redundancy. The state of a signal is represented by two binary variables. The first variable is the logic value of the signal. The second variable is the observability status of the signal with respect to all primary outputs. Boolean equations specify local relationships of these variables in a manner similar to the neural network or Boolean satisfiability method. All pairwise terms appearing in these Boolean equations are used to construct an implication graph, for which the transitive closure graph is obtained. Any signal assignments or relations found from the transitive closure are substituted into higher-order terms of the Boolean equations, some of which reduce to pairwise terms. Such cases are iteratively included in the transitive closure until no more reductions are possible. In the final transitive closure, all signals are examined for the following conditions of redundancy: (1) If a signal and its complement imply each other (contradiction) then both stuck-at faults on that signal are redundant; (2) If one value implies the other value (fixation) then one of the stuck-at faults on that signal is redundant; (3) If the true observability status of a signal implies its own false observability status, then both stuck-at faults of that signal are redundant; (4) If a certain value of a signal implies the false observability status, then the corresponding stuck-at fault is redundant. We give ISCAS '85 benchmark results. For c6288, we could identify 31 out of 33 redundancies. The percentage of identified redundancies was not always that high, but the algorithm has polynomial complexity and we discuss its limitations.

The testability of a sequential circuit can be improved by controlling the clock of individual storage elements during testing. We propose several clock control strategies derived from an analysis of the circuit, its S-graph structure, and its function. Through examples we show how the number of clocks affects the circuit's testability. It is shown that if certain flip-flops (FFs) are scanned (or otherwise initialized), the remaining FFs can be controlled and initialized to any arbitrary state using the clock control. We derive a controllability graph and use it to assign clocks to FFs and to schedule the clocks to set the FFs to an arbitrary state during test. Our analysis of sequential benchmark circuits indicates that this could be an attractive scheme for combining partial scan with clock control.

We propose an efficient combinational circuit simulation technique for the recently proposed segment delay fault model. After simulation of a vector pair, activated segments are traced using a depth-first search. A segment numbering scheme finds the number of faults to be simulated. A labeling technique generates edge labels to compute a unique label for each segment fault. The use of labels avoids explicit storing of fault lists and allows efficient access to previously detected segment faults. Experimental results demonstrate several advantages of the segment delay fault model. First, the total number of faults remains manageable for small segment lengths. Second, many segments, not included in any robustly testable path fault, may have robust segment delay fault tests. Generating tests for such segments may increase the delay defect coverage.

Current approaches to self test consist of adding hardware to the already synthesized circuits to transform them into autonomous finite state machines. If the circuit's own function is used for test generation and or data compression, then the fault coverage and aliasing properties have to be obtained by simulation. In this paper, we give a function-level specification for the self-test problem. In the self-test mode, all primary inputs and outputs are latched. The circuit behaves as an autonomous finite-state machine, which executes an Euler walk of all states. Thus, each state is visited exactly once, with all states forming a closed path in the state transition graph of the test machine. This function is embedded in the high-level description of the given finite state machine. The self-test hardware thus undergoes the same optimization process as the machine hardware, with a chance of better area/timing optimization. Up to 100% fault coverage against all single/multiple faults can be achieved if the appropriate synthesis/optimization tools are used. On completion of self-test the signature, consisting of the states of all flip-flops, is shown to have an aliasing probability 2/sup -m/ when the circuit has m flip-flops and the fault corrupts a single state-transition.

The present an efficient path-delay fault (PDF) simulator that does not involve enumeration of paths. Our method calculates the exact fault coverage, and identifies all tested faults in any circuit with a large number of paths. We present a new data structure, called the Path-Status Graph (PSG), to efficiently hold the status of each PDP in the circuit, i.e., whether or not the PDF is tested. The key to this efficiency is in breaking the information into pieces and distributing it over the data structure and in retaining all or part of the reconverging fanout structure of the circuit in the PSG. Thus, an exponential number of PDFs can share the same piece of information. Using one thousand random tests, we simulated all of the approximately 10/sup 20/ PDFs in the circuit c6288 and determined that 4.4 billion faults were detected. This number is larger by over three orders of magnitude compared to what was possible with previously reported methods.

We propose a segment delay fault model to represent any general delay defect ranging from a spot defect to a distributed defect. The segment length, L, is a parameter that can be chosen based on available statistics about the types of manufacturing defects. Once L is chosen, the fault list contains all segments of length L and paths whose entire lengths are less than L. Both rising and falling transitions at the origin of segments are considered. Choosing segments of a small length can prevent an explosion of the number of faults considered. At the same time, a defect over a segment may be large enough to affect any path passing through it. We present an efficient algorithm to compute the number of segments of any possible length in a circuit. We define various classes of segment delay fault tests-robust, transition, and non-robust-that offer a trade-off between fault coverage and quality.

We present a novel, highly efficient functional test generation methodology for synchronous sequential circuits. We generate test vectors for the growth (G) and disappearance (D) faults using a cube description of the finite state machine (FSM). Theoretical results establish that these tests guarantee a complete coverage of stuck faults in combinational and sequential circuits, synthesized through algebraic transformations. The truth table of the combinational logic of the circuit is modeled in the form known as personality matrix (PM) and vectors are obtained using highly efficient cube-based test generation method of programmable logic arrays (PLA). Sequential circuits are modeled as arrays of time-frames and new algorithms for state justification and fault propagation through faulty PLAs are derived. We also give a fault simulation procedure for G and D faults. Experiments show that test generation can be orders of magnitude faster and achieves a coverage of gate-level stuck faults that is higher than a gate-level sequential-circuit test generator. Results on a broad class of small to large synthesis benchmark PSM's from MCNC support our claim that functional test generation based on G and D faults is a viable and economical alternative to gate level ATPG, especially in a logic synthesis environment. The generated test sequences are implementation-independent and can be obtained even when details of specific implementation are unavailable. For the ISCAS'89 benchmarks, available only in multilevel netlist form, we extract the PM and generate functional tests. Experimental results show that a proper resynthesis improves the stuck fault coverage of these tests.

Many test generation algorithms for path delay faults assume a special methodology for application of the test sequence. The two-vector test sequences are valid under the assumption that the combinational logic reaches a steady state following the first vector before the second vector is applied. While such vectors may be acceptable for combinational circuits, their use for testing a non-scan sequential circuit is virtually impossible where it is difficult to run the clock at a constant rate. Most multi-valued algebras for combinational circuits are rendered invalid when vectors are applied at the rated speed. We present a new multi-valued algebra and a test generation algorithm to derive tests for a uniform rated speed test application methodology. The main ideas in the paper include an algebra that derives three-vector test sequences combinational logic and (2) a value propagation rule for latches, resulting in more realistic fault coverages in sequential circuits when all vectors are applied at the rated speed. The test generator uses Boolean functions to reason about state transitions in sequential machines. These Boolean functions are stored and manipulated as Binary Decision Diagrams (BDDs). Experimental data on moderate size ISCAS89 benchmarks are included.

We present a novel test generation technique for path delay faults, based on the growth (G) and disappearance (D) faults of programmable logic arrays (PLA). The circuit is modeled as a PLA that is prime and irredundant with respect to every output. Certain tests for G faults, generated by using known efficient methods are transformed into tests for path delay faults. Our algorithm generates tests for all robustly detectable path delay faults in the two-level circuit and its multilevel implementation synthesized using algebraic transformations. Experimental results confirm that the generated vectors, beside robustly covering all path delay faults, also cover most stuck faults in the algebraically factored multilevel circuit. We present some of the best known timings and robust path delay fault coverages for the scan/hold versions of several ISCAS89 circuits, for which the PLA description could be obtained.

We propose a method of testing high-speed digital devices whose clock frequency exceeds the capability of the test equipment. The circuit is designed such that a controllable delay is introduced in the timing paths during test. With the added delay, the maximum operating frequency is lowered to a rate which is within the capability of the ATE. The delay circuit is so designed that its function is also testable. In an illustrative design with single clock, the controllable delay is incorporated within a master-slave flip-flop. The control of delay is then achieved by manipulation of the duty-cycle of the clock waveform. In a two-clock system, no modification of the flip-flop is required and the delay is varied by skewing one clock signal with respect to the other.

In this paper, we classify path-delay faults into three categories: singly-testable (ST), multiply-testable (MT), and singly-testable dependent (ST-dependent). All ST faults are guaranteed detection in the case of a single fault, and some may be guaranteed detection through robust and validatable non-robust tests even in the case of multiple faults. An ST-dependent fault can affect the circuit speed only if certain ST faults are present. Thus, if the ST faults are tested, the ST-dependent faults need not be tested. MT faults cannot be guaranteed detection, but affect the speed only if delay faults simultaneously exist on a set of paths none of which is ST. We classify all path-delay faults into the three categories by a procedure using any unaltered single stuck fault test generation tool. We use only two runs of this tool on a network derived from the original network. As a by-product of this process, we generate single and multiple input change delay tests for all testable faults. With these tests, we expect that most defective circuits are identified. Examples and results on ISCAS'89 benchmarks are presented.

We examine the detectability of stuck-at faults when test vectors are applied at the rated speed. In the presence of path delays that are comparable to the clock interval, delayed signal transitions or timing hazards influence the detection of faults. It is, therefore, possible that a stuck-at fault that is detected by a test applied at slow speed, may not be detected with high speed test application. We present a fault simulation method that takes timing effects into account without specific delay modeling. Delay-hazard robust (dh-robust) coverage of a test sequence is defined as the coverage of single stuck-at faults that are guaranteed to be detected irrespective of delays or hazards. For tests generated for slow-speed testing, the dh-robust coverage can be quite low. However, special timing considerations in test generation provide better quality tests, especially for high performance circuits.

A new test generation technique for path delay faults in circuits employing scan/hold type flip-flops is presented. Reduced ordered binary decision diagrams (ROBDDs) are used to represent Boolean functions realized by all signals in the circuit, as well as to represent the constraints to be satisfied by the delay fault test. Two faults are considered for each path in the circuit. For each fault, a pair of constraint functions, corresponding to the two time frames that constitute a transition, is evaluated. If the constraint function in the second time frame is non-null, robust-hazard-free-test generation for the delay fault is attempted. A robust test thus generated belongs either to the class of fully transitional path (FTP) tests or to the class of single input transition (SIT) tests. If a robust test cannot be found, the existence of a non-robust test is checked. Boolean algebraic manipulation of the constraint functions guarantees that if neither robust nor non-robust tests exist, the fault is undetectable. In its present form the method is applicable to all circuits that are amenable to analysis using ROBDDs. An implementation of this technique is used to analyze delay fault testability of ISCAS '89 benchmark circuits. These results show that the algebraic technique is one to two orders of magnitude faster than previously reported methods based on branch-and-bound algorithms.>

We give two theorems for identifying untestable faults in sequential circuits. The first, the single-fault theorem, states that if a single fault in a combinational array is untestable then that fault is untestable in the sequential circuit. The array replicates the combinational logic and can have any finite length. We assume that the present state inputs of the left-most block are completely controllable. The next state outputs of the right-most block are considered observable. A combinational test pattern generator determines the detectability of single faults in the right-most block. The second theorem, called the multifault theorem, uses the array model with a multifault consisting of a single fault in every block. The theorem states that an untestable multifault in the array corresponds to an untestable single fault in the sequential circuit. For the array with a single block both theorems identify combinational redundancies. Experiments on ISCAS benchmarks show that using a small array size (typically, two to four blocks) we can identify a large number of sequentially untestable faults.>

We present a new formulation of the delay testing problem as an energy minimization problem. Two important applications have motivated this work. First, it can be used to efficiently generate robust and nonrobust tests for path delay faults in scan and hold type of sequential circuits. Second, It allows the design of a special class of delay fault testable circuits, called (k,K)-circuits, that have polynomial-time test generation complexity. For the new formulation, the relationship between input and output signal states of a logic gate for an arbitrary pair of input vectors is expressed through an energy function. The minimum-energy states of this function correspond to signal values that are consistent with the gate's logic function. The function also implicitly includes the information about the potential hazards due to arbitrary delay distributions in the circuit. The energy function for the circuit is the summation of the individual gate energy functions. To derive tests for a given delay fault, this function is suitably modified such that any minimum-energy state is guaranteed to be a test. The specific modifications to the energy function depend on the type (robust or nonrobust, with or without hazards) of delay test desired. For (k, K)-circuits, we show that the energy function can be minimized in polynomial-time. For general circuits, where the problem still has an exponential complexity, the recently proposed transitive closure based test generation technique is very effective in generating tests. This approach efficiently determines a delay test or establishes that no test is possible for the given delay fault. We report experimental results on various sequential benchmark circuits (full-scan versions) showing the feasibility and practicality of the new methods.>

We have developed a new statistical technique for estimating delay fault coverage in combinational circuits. True value simulation is performed for a sample of vector pairs chosen randomly from the test set. Transition probabilities and observabilities are estimated from the simulation data. These allow us to estimate fault detection probabilities per vector pair. Fault models considered are the transition faults, path delay faults, and the longest path delay faults. We analyze the vector sampling error and find a high-confidence lower bound for the detection probability that is used to compute the fault coverage for the entire vector set. Experimental results show that vector sampling can provide a close approximation to other methods. It requires reduced computing resources compared to other statistical methods. The savings over fault simulation is even greater.>

We present new algorithms for embedding test functions into the state diagram of a finite state machine. We first identify the cases where test functions can be embedded into the state diagram of the given object machine without using an extra input line. When such embedding is possible, our method finds it. In other cases, an extra input line must be added to the object machine to make the embedding possible. For the extra input case, we use partition theory and state variable dependencies in the object machine to obtain a mapping of the test machine states onto the object machine states. This mapping introduces a minimum number of extra state variable dependencies in the augmented machine as compared to the dependencies in the object machine. Experimental results on several MCNC benchmarks show that our method yields augmented machine implementations that have lower area than corresponding full scan designs. The test generation complexity for the augmented machine implementation is the same as that for a full scan design. We further consider the embedding of test functions into machines specified as an interconnection of finite state machines. We incorporate test functions into each component finite state machine such that the augmented interconnected machine has the same testability properties as the product machine with test function.>

We present a new area-efficient procedure for embedding test function into the gate-level implementation of a sequential circuit. First, we develop a test machine embedding technique for a given gate-level implementation of a finite state machine. The test machine states are mapped onto the states of the given circuit such that a minimum number of new state variable dependencies are introduced. The composite function is optimized. Experimental results show that our method yields testable machine implementations that have lower area than the corresponding full scan designs. The test generation complexity for our machine implementation is the same as that for a full scan design. To apply the method to large gate-level designs, we partition the circuit into interconnected finite-state machines. Each component state machine can be specified either as its gate-level implementation or as the extracted state diagram. We incorporate test functions into each component finite state machine such that the entire interconnection of the augmented components has the same testability properties as the product machine with a single test function. ISCAS '89 benchmark circuits are partitioned into component finite state machines using a new testability-directed partitioning algorithm. Again, our embedding procedure results in testable circuits that have lower area than the corresponding full scan designs.>

We develop an exact algorithm for selecting flip-flops in partial scan designs to break all feedback cycles.The main ideas that allow us to solve this hard problem exactly for large, practical instances are -graph transformations, a partitioning scheme used in the branch and bound procedure, and pruning techniques based on an integer linear programming formulation of the minimum feedback vertex set (MFVS) problem.We have obtained optimum solutions for the ISCAS '89 benchmark circuits and several production VLSI circuits within reasonable computation time.For example, the optimal number of scan flip-flops required to eliminate all cycles except self-loops in the circuit s38417 is 374.This optimal solution was obtained in 32 CPU seconds on a SUN Sparc 2 workstation.

Abstract|W e propose a linear complexity method to estimate robust path dela y fault coverage in digital circuits.W e adopt a path counting scheme for a true-value simulator that uses ags for each signal line.These ags determine the new path delay faults detected by the simulated vector pair.Experimental results are presented to show the eectiveness of the method in estimating path delay fault coverage.

We show that a given initialization sequence for a synchronous sequential circuit is not guaranteed to work correctly when arbitrary path delays are present in the circuit. In this paper, we present a novel robust-initialization procedure for sequential circuits. This procedure guarantees the correct initialization of state elements of a sequential circuit regardless of delays in the circuit. Every pattern of the normal initialization sequence is repeatedly clocked in flip-flops, so that excessive delays on combinational paths feeding flip-flops do not prevent the proper initialization. This method guarantees the correct initialization of pipeline circuits. For a general sequential circuit which may have feedbacks, we give a simulation procedure to determine the initial state of the circuit that is guaranteed to be correct for arbitrarily large but bounded delays.>

We propose a new statistical technique for estimating fault coverage in combinational circuits. Our method requires fault-free simulation of a random sample of vectors from the test vector set. Fault coverage is computed from controlabilities and observabilities both defined as probabilities and the method is applicable to any fault model like stuck-at-faults or delay faults. Experimental results are presented for path and transition delay faults.>

A sequential circuit teat generation program ts paratleltzed to run on a network of Spare 2 workstations con.

We experimentally study the reasons for low coverage of path delay faults in several sequential benchmark circuits. Causes for undetected faults are classified into three categories: (A) Combinationally nonactivated paths, (B) Sequentially nonactivated paths, and (C) Unobservable fault effect. The type A faults can only be made detectable by modifying or resynthesizing the combinational logic as has been discussed by others. We find that almost 80% of sequentially untested faults are in category B. Most are not activated because the two successive states necessary to create a transition and to propagate it through the path cannot be produced in the sequential circuit. We study the partial scan technique in which flipflops are scanned to break cycles and show that a substantial increase in the coverage of path delay faults is possible.

For a given set of vectors, the guaranteed failure frequency of a synchronous sequential circuit is defined. This frequency is obtained from multiple delay logic simulation by selectively suppressing timing hazards. Any path delay fault testable by the vectors, if present, is guaranteed to be detected if the tests were run at this frequency.>

An implementation of a design for testability model for sequential circuits is presented. The flip-flops in a sequential circuit are partitioned to reduce the number of cycles and the path lengths in each partition, thereby reducing the complexity of test generation. The implementation includes a Podem-based test generator. Preliminary results using the Contest sequential test generator are presented.>

A sequential circuit test generation program is parallelized to run on a network of Sparc 2 workstations connected through ethernet. The program attempts to compute tests to detect all faults in a given list. The fault list is equally divided among the processors. The entire process consists of a series of parallel computing passes with synchronization occurring between passes. During a pass, each processor independently generates test sequencies for the assigned faults through vector generation and fault simulation. A fixed per-fault CPU time limit is used within a pass. Faults requiring more time are abandoned for later passes. Each processor simulates the entire fault list with its vectors and communicates the list of undetected faults to all other processors. Processors then combine these fault lists to create a list of faults that were not detected by all processors. This list is again equally divided and the next pass begins with a larger per-fault time limit for test generation. The process stops after either the required fault coverage is achieved or the pass with given maximum per-fault time limit is completed. Some benchmark results are given to show the advantage of distributed system for large circuits. Finally, the authors study a speedup model that considers duplicated computation and interprocessor communication.>

We use a 23-value logic system to generate robust path delay tests. Each test is successively augmented to detect as many path faults as possible. Other features of the test generator are a podem-like branch and bound search for test, an efficient path designation based on ordering of paths, and an algorithmic selection of secondary target faults for augmenting the tests to cover multiple faults. Results for ISCAS '89 benchmarks are given.>

We present a new area-efficient procedure for embedding test function into the gate-level implementation of a sequential circuit. We use partition theory and a state variable dependency minimization criterion to map the test function states onto the states of the given circuit. The test generation complexity for our implementation is the same as that for a full scan design. To apply the method to large gate-level designs, we partition the circuit into interconnected finite-state machines. We incorporate test functions into each component machine such that the augmented interconnected machine has the same testability properties as the product machine with test function. Several ISCAS 89 benchmark circuits are partitioned into component finite state machines using a testability-directed partitioned into component finite state machines using a testability-directed partitioning algorithm. Our embedding procedure results in testable circuits that have smaller area than the corresponding full scan designs.>

Gives methods of test generation for partial scan circuits in which a single system clock controls all flip-flops in both functional and scan modes. Scan flip-flops are selected to break cycles. In comparison to circuits with separate scan clock, the single clock tests can cover most detectable faults with shorter test sequence. However, test generation time is increased.>

A transitive-closure-based test generation algorithm is presented. A test is obtained by determining signal values that satisfy a Boolean equation derived from the neural network model of the circuit incorporating necessary conditions for fault activation and path sensitization. The algorithm is a sequence of two main steps that are repeatedly executed: transitive closure computation and decision-making. A key feature of the algorithm is that dependences derived from the transitive closure are used to reduce ternary relations to binary relations that in turn dynamically update the transitive closure. The signals are either determined from the transitive closure or are enumerated until the Boolean equation is satisfied. Experimental results on the ISCAS 1985 and the combinational parts of ISCAS 1989 benchmark circuits are presented to demonstrate efficient test generation and redundancy identification. Results on four state-of-the-art production VLSI circuits are also presented.>

To analyze path delay faults in synchronous sequential circuits, stimuli are simulated in a dual-vector mode. The signal states represent the logic and transition conditions for two consecutive vectors. After the simulation of each vector, only the activated paths are traced and the corresponding fault effect, if propagated to a flip-flop, is added to its fault list. A path numbering scheme avoids storage of path data which can be generated, if needed, from the path number. The simulation is independent of the specific delays of the combinational elements, and either robust or nonrobust detection can be simulated as options to the user. For robust simulation, an update rule for state variables is proposed whereby a flip-flop is updated with its correct value, provided it is a destination of at least one robustly activated path. This rule gives a higher and more realistic coverage of robustly detected faults. Experimental results verify the effectiveness of the simulator.>

It is shown that the known methods of field reject ratio prediction are not accurate since they fail to realistically model the process of testing. The authors model the detection of a fault by an input test vector as a random event. However, the detection of a fault may be delayed for various reasons: the fault may be detectable only by application of a sequence of vectors or it may not have been targeted until later. In the statistical model, a fault is characterized by two parameters: a per-vector detection probability and an integer-valued latency. Irrespective of the detection probability, the fault cannot be detected by a vector sequence shorter than its latency. The circuit is characterized by the joint distribution of latency and detection probability over all faults. This distribution, obtained by applying the Bayes' rule to the actual test data, allows computations the field reject ratio. The sensitivity of this approach to variations in the measured parameters is also investigated.>

It is shown that a finite-state machine, whose state encoding is obtained only to reduce the amount of logic in the final implementation, may not be initializable by a logic simulator or a test generator even when the circuit is functionally initializable (i.e. has synchronizing sequences). A fault simulator or a sequential circuit test generator that assumes all memory elements initially to be in the unknown state will be totally ineffective for such a design. Proper consideration for initializability during state assignment and logic optimization can guarantee the success for gate-level analysis tools. The conditions for initializability of finite-state machines are derived, and an automatic state assignment algorithm for logic minimality and initializability is given. Experimental results show that, in most cases, this method does not require more hardware than the other methods that may produce an uninitializable design. A partial reset technique, recommended for machines without a synchronizing sequence, is also discussed.>

A statistical model of parallel processing and a performance evaluation technique are introduced. A task is characterized by the number of atoms and by activity. An atom is the smallest part of computation that cannot be distributed to multiple processors and all atoms of a task are assumed to be equal in computational effort. Furthermore, atoms of the task became active with a fixed probability a called the activity. The task is equally divided among processors and the computation is synchronized at periodic instances when the results can be shared. The amount of computational activity of a processor within the period between synchronizations is assumed to be a binomial random variable. The performance of the multiprocessor system is derived from the maximum order-statistic of these random variables. The theoretical performance predicted by the analysis agrees well with the reported experimental performance of logic simulation of production VLSI chips, and several observed phenomena are explainable.>

We present a transitive closure (TC) based test generation algorithm.A test k obtained by determining signal values that sattsfy a Boolean expression constructed from the ctrcuit netltst and the fault.The atgorithm is a sequenceof two main stepsthat are repeatedly executed: TC computation and dectsion- maldng.To compute the TC of the ctrcuit, we construct an hnpltcation graph whose vertices are labeled as the true and fatse states of alt signals.A directed edge (z, y) tn this graph represents the controlling htfluence of the true state of signal z on the true state of signal y that are connected through a wire or a gate.Since the implication graph only includes pairwtse (or btnary) relations, it is a partial representation of the netlist.The TC of the bnplication graph contatns pairwise logical relationships among all signats.When signal relationships describing fault activation and path sensittzatton are included, TC determines signal fixations and logical contradictions that dtrectly identify many redundancies.Sensitization of physical and logical dominators, unique path sensitization, static and dynamic learntng and other techniques that are useful in determiatng necessary stgnal assignments are implicit tn the preeess.If signals thus determined satisfy the Boolean formula, we have a test.Otherwtse, we use the decision-making step, fix an unasstf+ned signal, and update the TC to find further logical consequences.

Summary form only given. The automation of the design and test of VLSI circuits is discussed. Principles that the author believes will guide the design and test methodology of the future are stated. They are: the principle of hierarchy, the principle of orthogonality, the principle of standardization, and computing resource sharing. The principles apply equally to design and test, strengthening the view that design and test are two sides of the same coin.>

Novel models and algorithms for MOS transmission gates, buses and functional memories for use in statistical fault analysis (Stafan) are described. A bus is modeled as a multiple input multiplexer with feedback to account for its memory state. A CMOS transmission gate, modeled as a unidirectional device, always feeds into a bus that processes the high impedance state. Novel algorithms are devised to compute input observabilities of functional memory blocks. A novel implementation of Stafan algorithms is described for the MARS hardware accelerator environment. MARs is run in the true-value simulation mode and sends signal changes for all lines through a Unix pipe to the Stafan process running on a SUN workstation. The Stafan process computes controllabilities, observabilities, detection probabilities, and fault coverage. MARS and Stafan thus run as a pipeline. Results on several CMOS circuits are obtained and compared with those obtained from a concurrent fault simulator.>

Abstract: Detection of a fault in a sequential circuit requires a sequence of test vectors. This se-quence activates the fault and propagates the effect of the fault to a primary output. To accomplish this, the test sequence must set flip-flops through a series of states. Unlike a combinational circuit, many faults in a sequential circuit cannot be detected by a sin-, gle vector. We propose a statistical model in which. a fault is characterized by two parameters: a per-vector detection probability and an integer-valued la-. tency. Irrespective of its detection probability, the fault cannot be detected by a vector sequence shorter than the latency. A joint distribution of the latency and detection probability over all the failed chips is thus obtained. Using the new model, an analysis o:f chip failure data to predict actual yield and reject ra-tio is given. For a large-volume CMOS chip, tested by vectors having 99.7 % fault coverage, this analysis gives a reject ratio of 43 parts per million that is be-lieved to be in close agreement with the field data. 1

We present a new synthesis for testability method in which a test function is incorporated into the state diagram of the finite state machine (FSM). The test function is specified as a FSM with the same number of state variables as the given object machine. The state graph of the test machine is so defined that each state is uniquely set and observed by an input sequence no longer than ⌈logkn⌉, where n is the number of states and the integer k is a design parameter. The state transition graph of the test machine is superimposed on the state graph of the object function such that a minimal number of new transitions are added. State assignment, logic minimization and technology mapping are then carried out for the combined graph. By design, the embedded test machine is fully testable. Also, since the test machine can control all memory elements, the circuit is effectively tested by a combinational circuit test generator. Scan register is shown to be a special case in this methodology.

We recently proposed an unconventional digital circuit modeling technique and formulated test generation as an energy minimization problem [7]. Although energy minimization is as hard as test generation, the new approach has two advantages. Since the circuit function is mathematically expressed, operations research techniques like linear and non-linear programming can be applied to test generation. The non-causal form of the model makes parallel processing possible. The energy function E, a quadratic 0-1 function, is split into two sub-functions, a homogeneous posiform and an inhomogeneous posiform. The minimum of E is the sum of the minima of the two sub-functions, each having a minimum value of 0. We obtain a minimizing point of the homogeneous posiform, in time complexity that is linear in the number of sub-function terms, and check if the other sub-function becomes 0. When both become 0, we have a test vector. We discuss several easily parallelizable speedup techniques using the transitive closure and other graph properties. Preliminary results on combinational circuits confirm the feasibility of this technique.

The complexity of a Boolean function can be expressed in terms of computational work. We present experimental data in support of the entropy definition of computational work based upon the input-output description of a Boolean function. Our data show a linear relationship between the computational work and the average number of literals in a multi-level implementation. The investigation includes single-output and multi-output function with and without don't care states. The experiments, conducted on a large number of randomly generated functions, showed that the effect of don't cares is to reduce the computational work. For several finite state machine benchmarks, the computational work gave a good estimate of the size of the circuit. Finally, circuit delay is shown to have a non-linear relationship to the computational work.

A statistical model is presented of parallel processing based on circuit activity defined as the average number of gates evaluated at a time step. The number of active gates in a processor is assumed to be a random variable with a binomial probability density function. The performance of the multiprocessor system is derived from the maximum order-statistic of these random variables. When the gates can be equally divided among the p processors, the lower bound on speedup is found to be a*p, where a is the average circuit activity. For unequal division of gates, the lower bound on speedup is less than a*p. Interestingly, for very low activity, speedups significantly higher than the lower bounds are possible.>

The authors report on an experiment to verify the accuracy of reject ratio predictions by the available approaches. The data collection effort includes instrumenting the wafer probe test to obtain chip failures as a function of applied vectors and running a fault simulator to obtain the cumulative fault coverage of these vectors. The accuracy of reject ratio predictions is judged by assuming earlier stopping points for the wafer probe, thereby gaining a measure of confidence in the final predicted value. The results of five different analyses are reported for over 70000 tested dies of a CMOS VLSI device. The five methods discussed predicted values for the reject ratio that vary by an order of magnitude at high values of fault coverage. It is shown that, with only an incremental effort during wafer probe, data collection that can be used to compare the relative accuracy of different models over a range of fault coverage is possible.>

A statistical model for analyzing the performance of synchronized iterative algorithms on a multiprocessor system is presented. Key ideas are illustrated using logic simulation as an example problem. The authors introduce activity as a relevant parameter and analyze the behavior of the parallel processing system using an analytical method. The statistical performance results agree with and satisfactorily explain empirical observations on production VLSI circuits obtained by other researchers. It is shown that as the number of processors is increased, the speedup rapidly changes from p to a*p, where a is the activity and p is the number of processors. Low activity reduces speedup. A lower bound on the speedup of the parallel processing system is presented. For high activity, this lower bound is quite close to the actual speedup.>

A method of partial scan design is presented in which the selection of scan flip-flops is aimed at breaking up the cyclic structure of the circuit. Experimental data are given to show that the test generation complexity may grow exponentially with the length of the cycles in the circuit. This complexity grows only linearly with the sequential depth. Graph-theoretic algorithms are presented to select a minimal set of flip-flops for eliminating cycles and reducing the sequential depth. Tests for the resulting circuit are generated by a sequential logic test generator. An independent control of the scan clock allows insertion of scan sequences within the vector sequence produced by the test generator. An independent control of the scan clock allows insertion of scan sequences within the vector sequences produced by the test generator. 98% fault coverage is obtained for a 5000-gate circuit by scanning just 5% of the flip-flops.>

In a recent work of the authors (1987), a simulation-based directed search approach for generating test vectors for combinational circuits was proposed. In this method, the search for a test vector is guided by a cost function computed by the simulator. Event-driven simulation deals with circuit delays in a very natural manner. Signal controllability information required for the cost function is incorporated in a new form of logic model called the threshold-value model. These concepts are extended to meet the needs of sequential circuit test generation. Such extensions include handling of unknown values, analysis of feedback loops, and analysis of race conditions in the threshold-value model. A threshold-value sequential test generation program, TVSET, is implemented. It automatically initializes the circuit and generates race-free tests for synchronous and asynchronous circuits.>

A relation between the average fault coverage and circuit testability is developed. The statistical formulation allows computation of coverage for deterministic and random vectors. The following applications of this analysis are discussed: determination of circuit testability from fault simulation, coverage prediction from testability analysis, prediction of test length, and test generation by fault sampling.>

A new automatic test pattern generation (ATPG) methodology that has the potential to exploit fine-grain parallel computing and relaxation techniques is described. This approach is radically different from the conventional methods used to generate tests for circuits from their gate level description. The digital circuit is represented as a bidirectional network of neurons. The circuit function is coded in the firing thresholds of neurons and the weights of interconnection links. This neural network is suitably reconfigured for solving the ATPG problem. A fault is injected into the neural network and an energy function is constructed with global minima at test vectors. The authors simulated the neural network on a serial computer, and determined the global minima of the energy function using a directed search technique augmented by probabilistic relaxation. Preliminary results on combinational circuits confirm the feasibility of this technique.>

Proper consideration of initializability during state assignment can guarantee success for gate level analysis tools. The necessary and sufficient conditions for initializability are derived. The new state assignment algorithm uses additional constraints for initialization by a preselected input sequence. Experimental results show that, in most cases, this method does not require more hardware than the other methods that may produce an uninitializable design. A partial reset technique is suggested for machines without a synchronizing sequence.>

The authors propose design for testability at the logic synthesis level. Their state assignment is aimed at producing a reduced feedback or pipeline like structure which is easily analyzed by a sequential circuit test generator. State variables are assigned one at a time such that a state variable depends only on primary inputs and the previously assigned state variables. This results in a purely pipeline structure for finite-memory or definite machines. For other machines, the number of cycles in the implemented structure is minimized. The authors give several examples to compare their reduced feedback synthesis with another method that is aimed at reducing the amount of logic in a multilevel implementation. Results show a marked improvement in test generation time and fault coverage; in terms of logic their method did just as well as the other method.>

The authors describe fault simulation algorithms for the MARS hardware accelerator. Two algorithms are considered. The first, serial fault simulation, has a performance that is linear in the number of faults. Its performance is easily predictable and it takes full advantage of the true-value simulation speed of the accelerator; it is also easy to implement. The second algorithm, concurrent fault simulation, is found to have a performance that is nonlinear in the number of faults. It also requires either a large amount of memory or a dynamic memory management, both of which are difficult to implement in an accelerator. Yet the concurrent method has the advantage of more efficient event processing and less duplicated effort. Combining the features of both algorithms, a fixed-memory, multipass, concurrent algorithm is developed for MARS.>

A description is given of the application of a concurrent fault simulator to automatic test vector generation. As faults are simulated in the fault simulator a cost function is simultaneously computed. A simple cost function is the distance (in terms of the number of gates and flip-flops) of a fault effect from a primary output. The input vector is then modified to reduce the cost function until a test is found. Experimental results are presented showing the effectiveness of this method in generating tests for combinational and sequential circuits. By defining suitable cost functions, it has been possible to generate: (1) initialization sequences; (2) tests for a group of faults; and (3) a test for a given fault. Even asynchronous sequential circuits can be handled by this approach.>

An automatic test pattern generation (ATPG) methodology that has the potential to exploit fine-grain parallel computing and relaxation techniques is described. The approach is radically different from the conventional methods used to generate tests for circuits from their gate-level descriptions. A digital circuit is represented as a bidirectional network of neurons. The circuit function is coded in the firing thresholds of neurons and the weights of interconnection links. This neural network is suitably reconfigured for solving the ATPG problem. A fault is injected into the neural network and an energy function is constructed with global minima at test vectors. Global minima are determined by a probabilistic relaxation technique augmented by a directed search. Preliminary results on combinational circuits confirm the feasibility of the technique.>

The authors present a novel technique of generating tests from a random sample of faults. The entire fault population of the circuit is randomly divided into two groups. Only one group, usually the smaller one, is used for test generation by the test-generator and fault-simulator programs. This group is known as the sample and its coverage is deterministic. The coverage of faults in the remaining group is similar to that of random vectors and is estimated from the distribution of fault detection probabilities in the circuit. As the sample size increases, the fraction of unsampled faults reduces. At the same time, a larger sample yields more test vectors to increase the random coverage. For a circuit with high testability, a sample of just 5% faults, will provide tests for a 95% coverage. On the other hand, for a circuit with a relatively poor testability, one may have to sample 33% faults for the same coverage. For most practical cases, the sampling approach will mean significant saving in the computation and storage needs of fault simulation.>

This paper describes two logic minimization algorithms. CAMP (Computer Aided Minimization Procedure) minimizes single functions. The minterms are covered either by essential prime implicants or by selective prime implicants. The two types of prime implicants are determined one at a time thus completely avoiding the computationally expensive covering problem. The adjacency of a minterm, that depends upon the proximity of this minterm with respect to other minterms on the Karnaugh map, guides the determination of prime implicants. This procedure is nonheuristic and has proved to be very efficient for large number of input variables. The multiple output minimization (MOM) algorithm generates the product terms with maximum sharing between the output functions. In addition to using adjacency, this procedure is also guided by the frequency with which a minterm is used by the functions. Examples show the performance of this algorithm to be equal or better than many other minimization procedures.

An application of the D-algorithm in generating tests for MOS circuit faults is described. The MOS circuits considered are combinational and acyclic but may contain transmission gates and buses. Tests are generated for both the stuck type faults and the transistor faults (open and short). A logic model is derived for the MOS circuits. In addition to the conventional logic gates, a new type of modeling block is used to represent the "memory" state caused by the "open" transistors. Every fault, whether a stuck type fault or a transistor fault, is represented in the model as a stuck fault at a certain gate input. For generating tests, however, the D-algorithm needs modification. The singular cover and the D-cubes for the new gate include some memory states. To handle the memory state, an initialization procedure has been added to the consistency part of the D-algorithm. The procedure of modeling and test generation is finally extended to transmission gates and buses.

The results of production test on LSI wafers are analyzed to determine the parameters of the yield equation. Recognizing that a physical defect on a chip can produce several logical faults, the number of faults per defect is assumed to be a random variable with Poisson distribution. The analysis provides a relationship between the yield of the tested fraction of the chip area and the cumulative fault coverage of test patterns. The parameters of the yield equation are estimated by fitting this relation to the measured yield versus fault coverage data.

For verifying the timing performance of synchronous MOS circuits a path analysis facility has been developed in the MOTIS (MOS Timing Simulator) system. This path analysis traces the clock signals to the latches in the circuit, computes the clock skews and then performs a path search analysis between all latches. For the paths between clocked latches, the timing constraints are determined using the clock skews and the operating frequency. The paths that do not satisfy these constraints are identified as problem paths. Such an analysis does not require a prior generation of circuit stimuli that are necessary for simulation. In terms of complexity also, it is simpler than simulation.

The concepts of information theory are applied to the problem of testing digital circuits. By analyzing the information throughput of the circuit an expression for the probability of detecting a hardware fault is derived. Examples are given to illustrate an application of the present study in designing efficient pattern generators for testing.

To provide flexibility and efficiency in logic and timing verification of MOS VLSI circuits, it is desirable that various portions of a circuit can be described and simulated at appropriate levels of detail. Such a capability is provided by the Mixed-Mode Simulator described here. This simulator allows different elements of a circuit to be modeled and simulated at different levels of detail. The modeling levels are MOS transistor level, logic gate level and functional level. The simulation levels are timing, multiple delay and unit delay. The simulator is being used on production LSI chips and its performance is discussed.

The above paper1describes machines constructed on faulty logic arrays. These machines use some or all of the good cells that form a connective cluster. It is pointed out here that when the faulty cells are randomly distributed over the array, the propagation of a freely expanding signal, which must avoid the faulty cells, is a percolation process. The percolation process determines the limit to the size of a machine embedded in a faulty array. Some useful characteristics of this process are discussed.

P. B. Schneck is right in pointing out that maximum fan-in will lead to a more conservative estimate of the number of random patterns needed for complete testing. It is, however, useful to compare these estimates with practical cases. We will consider two examples.

A probabilistic method for deciding whether a combinational circuit should be tested by random inputs, is given. This decision is based upon certain easily observable circuit parameters, such as, the number of primary inputs, the number of levels, and the average fan in.

It is shown that by a proper selection of the probabilities of 0 and 1 at the inputs, the efficiency of random test generation can be improved. This correspondence includes some results describing the testing of actual logic networks used in a computer.

In this paper the random test generation method for large logic circuits is analyzed. Formulas for the detection probability and the number of random input patterns required to complete the test generation with a high probability are obtained for an irredundant fan-out-free combinational network tree consisting of identical n-input NAND gates. The quantitative estimates for the number of random input patterns required for test generation appear to depend upon the number of levels in the circuit and the fan-ins of the gates. Experimental results for actual computer logic circuits are given and show the validity of the approach.

A test generation system, developed for the logic boards of the Illiac IV computer, is described. The system combines the test generation by random patterns and the D-algorithm. Some results are given to illustrate the effectiveness of this approach.