Discusses the current state of the journal, reports on current and future areas of exploration and research, and presents new editors.

A Failing Frequency Signature is a collection of the maximum operating frequencies of each pattern in a pattern set. Analyzing the failing frequency signature can successfully detect small-delay defects, because even a small-delay defect can cause an outlier to appear in a failing frequency signature. Moreover, the failing frequency signature will be consistent even in the presence of process variations. Failing frequency signature analysis can effectively detect very hard-to-find defects that occur in No-Trouble-Found (NTF) devices, without the necessity of thorough test patterns. The analysis can also be used for characterization tests. In this paper, experimental results using the failing frequency signature to detect small-delay defects are presented using test chips fabricated in a 0.18μm technology.

The two most popular transition tests are launch-on-shift (LOS) test and launch-on-capture (LOC) test. The LOS and LOC tests differ in their launch mechanisms, creating their own pros and cons. In this paper, new hybrids of LOS and LOC tests that launch transitions using both launch mechanisms are introduced. The new transition tests improved fault coverage without significant test length penalty. This paper presents the concepts and pattern generation methods of these new transition tests as well as experimental results that demonstrate the benefits of these tests.

Studies by previous researchers using production test data reported that not all the production test patterns applied detected defective chips. Researchers found that 70% to 90% of their production test patterns seemed useless because these patterns detected no defective chips and they could therefore be removed without impacting test quality. Previous researchers qualitatively explained this finding by a lack of correlation between test metrics and defect coverage. Notwithstanding the lack of correlation between test metrics and defect coverage, in this paper we develop a simple statistical model that relates the expected number of useless patterns to the production yield, the defect coverage characteristics, and the number of tested chips. This model demonstrates that for practical values of production yield, defect coverage and number of chips tested, a significant fraction of test patterns will be useless. We validated this statistical model by comparing its results with actual production testing data.

With increasing IC process variation and increased operating speed, it is more likely that even subtle defects will lead to the malfunctioning of a circuit. Various fault models, such as the transition fault model and the path-delay model, have been used to aid delay defect detection. However, these models are not efficient for small-delay defect coverage or for test pattern generation time. Error sequence analysis utilizes the order in which the errors occur during a frequency sweep of a transition test to identify small-delay defects that may escape the same test applied in the conventional way. Moreover, it can detect such defects even in the presence of inter-die process variations, such as lot-to-lot and wafer-to-wafer process variation. In addition, error sequence analysis is very effective in separating devices with delay defects from devices that have failed due to process variation.

Delay testing is a technique to determine if a chip will function correctly at a specified frequency. If a chip passes delay tests, it will presumably function at the specified frequency in the field. This paper presents experimental results that show how chips can pass very thorough delay tests and still fail in the field. It is shown that some chips sometimes pass and sometimes fail when the same delay test is applied multiple times under the same test conditions. These chips are called inconsistent fails. This paper shows how tester timing edge placement accuracy can cause inconsistent fails and suggests the minimum requirements for guardbands that avoid the inconsistent test results.

This paper presents a scan architecture-California scan-that achieves high quality and low power testing by modifying test patterns in the test application process. The architecture is feasible because most of the bits in the test patterns generated by ATPG tools are don’t-care bits. Scan shift-in patterns have their don’t-care bits assigned using the repeat-fill technique, reducing switching activity during the scan shift-in operation; the scan shift-in patterns are altered to toggle-fill patterns when they are applied to the combinational logic, improving defect.

When a test set size is larger than desired, some patterns must be dropped. This paper presents a systematic method to reduce test set size; the method reorders a test set using the gate exhaustive test metric and truncates the test set to the desired size. To determine the effectiveness of the method, test sets with 1,556 test patterns were applied to 140 defective Stanford ELF18 test cores. The original test set required 758 test patterns to detect all defective cores, while the test set reordered using the presented method required 286 test patterns. The method also reduces the test application time for defective cores.

This paper shows data related to choosing a pair of test sets for digital IC production test. This data demonstrates that the choice of the second set of the pair should take into account the test metric used for the first test set. An approach for making this choice by taking defect coverage and total test length into account is presented

Often times a particular research topic is the result of a group of individuals working together to better characterize or solve a current problem. It can be beneficial for the group of researchers to present their research and early-stage results to fellow engineers to obtain input that may help direct their research efforts. The Special Session "Elevator Talks" provides a forum for 15 researchers to each make a 4 minute presentation (plus a 1 minute question period) on an emerging research topic and key results of this research. The work described in the "Elevator Talks" is new research that has not been presented at any other confe

A gate exhaustive test set applies all possible input combinations to each gate in a combinational circuit, and observes the gate response at an observation point such as a primary output or a scan cell. In this paper, we analyze the effectiveness of the gate exhaustive test metric in detecting defective chips, and compare it with the single stuck-at fault, the N-detect, and the transition fault test metrics. Results from the Stanford CRC ELF35 and ELF18 test experiments show that gate exhaustive test sets are more efficient than single stuck-at and N-detect test sets in terms of the ability to detect defective chips and test length. It is also shown that test sets with higher values of the gate exhaustive coverage have better test quality.

TARO test patterns are transition fault test patterns that sensitize each transition fault to all of the outputs that can be reached from the fault location. We were not able to identify any ATPG tool that can generate TARO test patterns directly. This paper describes a technique to use an existing transition fault ATPG tool to efficiently generate TARO test patterns. This technique was used to generate TARO patterns for the ELF35 test chip. When these patterns were applied to the ELF35 chips, all of the defective chips were discovered (no test escapes).

Mixed-mode logic built-in self-test (BIST) applies both pseudorandom test patterns and deterministic test patterns [from an automatic test pattern generation (ATPG) tool] to the combinational portion of the circuit under test. Each scan-test cycle consists of: 1) shifting a test pattern into the scan chains; 2) capturing the response to that pattern; and 3) shifting the captured response out of the scan chains. The shifting of the test pattern out of the scan chains is overlapped with shifting in the next test pattern. The pattern shifted into the scan chains comes from the output of the pseudorandom pattern generator (PRPG); this pattern is determined by the initial state or seed of the PRPG (the contents of the PRPG at the beginning of the shifting operation). In a pseudorandom cycle, the initial state is the final state (last PRPG contents) from the previous cycle. The initial state of a deterministic cycle is shifted into the PRPG either from an a tester or from an on-chip BIST controller. This paper describes techniques to minimize the number of deterministic seeds that must be used: the number of seeds determines the required storage either on the ATE or the chip being tested. These techniques interleave pseudorandom and deterministic cycles rather than first applying all of the pseudorandom cycles and then the deterministic cycles. The decision of when to change from a pseudorandom cycle to a deterministic cycle is made by comparing the final state of the pseudorandom cycle with previously generated ATPG patterns or by carrying out fault simulation on the final state. Which deterministic pattern is chosen for the deterministic cycle critically influences the remainder of the test. A methodology for doing this is described. In addition to interleaving test cycles, it is possible to use partial cycles in which the PRPG operates for a few clocks without loading the scan chains. This allows a new seed to be present without loading the seed from the ATE or controller. As might be suspected, this reduces the number of stored seeds at the penalty of more complexity in the control sequence. These techniques were simulated and compared with conventional reseeding for some ISCAS'89 benchmarks. Improvements varied between 25% and 85% in the required seed storage.

A resistive-open defect is an imperfect circuit connection that can be modeled as a defect resistor between two circuit nodes that should be connected. A stuck-open (SOP) defect is a complete break (no current flow) between two circuit nodes that should be connected. Conventional single stuck-at fault diagnosis cannot precisely diagnose these two defects because the test results of defective chips depend on the sequence of test patterns. This paper presents precise diagnosis techniques for these two defects. The diagnosis techniques take the test-pattern sequence into account, and therefore, produce precise diagnosis results. Also, our diagnosis technique handles multiple faults of different fault models. The diagnosis techniques are validated by experimental results. Twelve SOP and one resistive-open chips are diagnosed out of a total of 459 defective chips.

Using complex (high-level) gates, such as multiplexers, full adders, etc., for automatic test pattern generation (ATPG) has several advantages. It makes ATPG faster and potentially reduces the size of the test set that needs to be applied. A variety of other techniques are used to reduce the size of test sets for digital chips. They typically rely on preserving the single-stuck-fault coverage of the test set. This article presents data obtained from applying a variety of test sets on the ELF35 test chip and recording the test escapes. The data presented show the test quality effect of using complex gates as fault sites. The article also shows the impact of test compaction and reduced fault coverage on the test quality.

Experimental data on 0.18 /spl mu/ test chips shows strong evidence of clustering of speeds of neighboring dies on a wafer. This clustering phenomenon is utilized to develop techniques for predicting the speed of a part from the speeds of three or more of its neighbors. On-chip processor monitors are used to further improve the prediction accuracy of these techniques. Experimental data demonstrates both the effectiveness of these prediction schemes and the possibility of applying of them to reduce the cost of speed binning.

LSI logic has designed and manufactured two test chips at CRC. These test chips were used to investigate the characteristics of actual production defects and the effectiveness of various test techniques in detecting their presence. This paper presents a characterization of the defects that shows that very few defective chips act as if they had a single-stuck fault present and that most of the defects cause sequence-dependent behavior. A variety of techniques are used to reduce the size of test sets for digital chips. They typically rely on preserving the single-stuck-fault coverage of the test set. This strategy doesn't guarantee that the defect coverage is retained. This paper presents data obtained from applying a variety of test sets on two chips (Murphy and ELF35) and recording the test escapes. The reductions in test size can thus be compared with the increases in test escapes. The data shows that, even when the fault coverage is preserved, there is a penalty in test quality. Also presented is the data showing the effect of reducing the fault coverage. Techniques studied include various single-stuck-fault models including inserting faults at the inputs of complex gates such as adders, multiplexers, etc. This technique is compatible with the use of structural RTL netlists. Other techniques presented include compaction techniques and don't care bit assignment strategies.

This paper presents delay test data collected from test chips fabricated in a 0.18 /spl mu/ technology. The experimental data shows that process monitor structures such as on-chip ring oscillators are effective in identifying slow parts while performing transition fault testing at frequencies slower than the rated frequency.

An application-dependent test strategy to be used by an FPGA user is presented which requires only 3 test configurations. In this specific strategy, the interconnect is first tested by modifying the logic block configuration and preserving the interconnect configuration. Then, the used logic blocks are fully tested by modifying the interconnect configuration. Results for some benchmark applications mapped into the Xilinx FPGAs are also provided.

Redundant systems are designed using multiple copies of the same resource (e.g., a logic network or a software module) in order to increase system dependability: Design diversity has long been used to protect redundant systems against common-mode failures. The conventional notion of diversity relies on "independent" generation of "different" implementations of the same logic function. In a recent paper, we presented a metric to quantify diversity among several designs. The problem of calculating the diversity metric is NP-complete (i.e., can be of exponential complexity). In this paper, we present efficient techniques to estimate the value of the design diversity metric. For datapath designs, we have formulated very fast techniques to calculate the value of the metric by taking advantage of the regularity in the datapath structures. For general combinational logic circuits, we present an adaptive Monte-Carlo simulation technique for estimating accurate bounds on the value of the metric.

Reseeding is used to improve fault coverage of pseudo-random testing. The seed corresponds to the initial state of the PRPG before filling the scan chain. In this paper, we present a technique for encoding a given seed by the number of clock cycles that the PRPG needs to run to reach it. This encoding requires many fewer bits than the bits of the seed itself. The cost is the time to reach the intended seed. We reduce this cost using the degrees of freedom (due to don't cares in test patterns) in solving the equations for the seeds. We show results for implementing our technique completely in on-chip hardware and for applying it from a tester. Simulations show that with low hardware overhead, the technique provides 100% single-stuck fault coverage. Also, when compared with conventional reseeding from an external tester or on-chip ROM, the technique reduces seed storage by up to 85%. We show how to apply the technique for both LFSRs and CA.

Reseeding is used to improve fault coverage in BIST pseudo-random testing. Most of the work done on reseeding is based on storing the seeds in an external tester. Besides its high cost, testing using automatic test equipment (ATE) makes it hard to test the circuit while in the system. In this paper, we present a technique for built-in reseeding. Our technique requires no storage for the seeds. The seeds are encoded in hardware. The seeds we use are deterministic so 100% fault coverage can be achieved. Our technique causes no performance overhead and does not change the original circuit under test. Also, the technique we present is applicable for transition faults as well as single-stuck-at faults. Built-in reseeding is based on expanding every seed to as many ATPG patterns as possible. This is different from many existing reseeding techniques that expand every seed into a single ATPG pattern. This paper presents the built-in reseeding algorithm together with a hardware synthesis algorithm and implementation.

Reseeding is used to improve the fault coverage of pseudo-random testing. The seed corresponds to the initial state of the LFSR before filling the scan chain. The number of deterministic seeds required is directly proportional to the tester storage or hardware overhead requirement. In this paper, we present an algorithm for seed ordering to minimize the number of seeds required to cover a set of deterministic test patterns. Our technique is applicable whether seeds are loaded from the tester or encoded on chip. Simulations show that, when compared to random ordering, the technique reduces seed storage or hardware overhead by up to 80%. The seeds we use are deterministic so 100% SSF fault coverage can be achieved. Also, the technique we present is fault-model independent.

Conventional fault simulation techniques for FPGAs are very complicated and time consuming. The other alternative, FPGA fault emulation technique, is incomplete, and can be used only after the FPGA chip is manufactured. In this paper, we present efficient algorithms for computing the fault coverage of a given FPGA test configuration. The faults considered are opens and shorts in FPGA interconnects. Compared to conventional methods, our technique is orders of magnitude faster, while is able to report all detectable and undetectable faults.

A technique capable of diagnosing single and multiple stuck-open and stuck-at faults is presented. Eleven sequence-dependent chips (test results depend on the order of test patterns) are diagnosed. Seven of them are diagnosed as having single stuck-open faults. Two of them are diagnosed as having multiple stuck-at and stuck-open faults.

The Test Access Port (TAP) controller is a very important circuit present in all IC chips that are compliant with the IEEE 1149.1 Boundary Scan standard. Although the main purpose of boundary scan is to facilitate board-level testing, it is also used for many other testing and non-testing purposes (e.g., memory and logic BIST wrappers to enable embedded core test, programming FPGAs, checkpointing and recovery of dependable systems, etc.). Hence, it is important to thoroughly test the TAP controller before using it for other purposes. In this paper, we present techniques for designing and testing the TAP controller. Our design techniques simplify the procedure to test the TAP controller by orders of magnitude compared to previously published results. Our TAP controller design technique does not require any extra I/O pins and can be easily automated and incorporated into test tools.

This paper presents slow-speed testing results for two test chip experiments at Stanford CRC: Murphy and ELF35. The test speed for slow-speed testing is 1/3 of the characterized speed, at which the circuit-under-test (CUT) can operate. At nominal supply voltage, 3 out the 116 defective Murphy CUTs escaped slow-speed testing. In the ELF35 experiment, I out of the 218 defective combinational CUTs escaped slow-speed testing. The experimental data also show that the number of test escapes depends more on the quality of the applied test sets, than on the test speed at which the test sets were applied We also evaluated the effectiveness of VLV testing at characterized speed. Our results show that it missed only one defective Murphy CUT. It detected all the defective ELF35 combinational CUTs. The one defective Murphy CUT that escaped VLV testing at characterized speed is a suspected resistive open. Schmoo characterization results show it can be detected by VLV testing at characterized speed if lot-to-lot re-characterization is done to determine the VLV testing speed.

Redundant systems are designed using multiple copies of the same resource (e.g., a logic network or a software module) in order to increase system dependability. Design diversity has long been used to protect redundant systems from common-mode failures. The conventional notion of diversity relies on "independent" generation of "different" implementations. This concept is qualitative and does not provide a basis for comparing the reliabilities of two diverse systems. In this paper, for the first time, we present a metric to quantify diversity among several designs and illustrate its effectiveness using several examples. Applications of this metric in analyzing reliability and availability of diverse redundant systems, and deriving simple relationships between diversity, system failure rate, and mission time are also demonstrated.

Errors in computing systems can cause abnormal behavior and degrade data integrity and system availability. Errors should be avoided especially in embedded systems for critical applications. However, as the trend in VLSI technologies has been toward smaller feature sizes, lower supply voltages and higher frequencies, there is a growing concern about temporary errors as well as permanent errors in embedded systems; thus, it is very essential to detect those errors. Software-implemented hardware fault tolerance (SIHFT) is a low-cost alternative to hardware fault-tolerance techniques for embedded processors: It does not require any hardware modification of commercial off-the-shelf (COTS) processors. ED/sup 4/I (error detection by data diversity and duplicated instructions) is a SIHFT technique that detects both permanent and temporary errors by executing two "different" programs (with the same functionality) and comparing their outputs. ED/sup 4/I maps each number, x, in the original program into a new number x', and then transforms the program so that it operates on the new numbers so that the results can be mapped backwards for comparison with the results of the original program. The mapping in the transformation of ED/sup 4/I is x' = k/spl middot/x for integer numbers, where k/sub f/ determines the fault detection probability and data integrity of the system. For floating-point numbers, we find a value of k/sub f/ for the fraction and k/sub e/ for the exponent separately, and use k = k/sub f//spl times/2/sup k/ for the value of k. We have demonstrated how to choose an optimal value of k for the transformation. This paper shows that, for integer programs, the transformation with k = -2 was the most desirable choice in six out of seven benchmark programs we simulated. It maximizes the fault detection probability under the condition that the data integrity is highest.

As commercial off-the-shelf (COTS) components are used in system-on-chip (SoC) design technique that is widely used from cellular phones to personal computers, it is difficult to modify hardware design to implement hardware fault-tolerant techniques and improve system reliability. Two major concerns of this paper are to: (a) improve system reliability by detecting transient errors in hardware, and (b) reduce energy consumption by minimizing error-detection overhead. The objective of this new technique, selective procedure call duplication (SPCD) is to keep the system fault-secured (preserve data integrity) in the presence of transient errors, with minimum additional energy consumption. The basic approach is to duplicate computations and then to compare their results to detect errors. There are 3 choices for duplicate computation: (1) duplicating every statement in the program and comparing results, (2) re-executing procedures through duplicated procedure calls, and comparing results, and (3) re-executing the whole program, and comparing the final results. SPDC combines choices (1) and(2). For a given program, SPCD analyzes procedure-call behavior of the program, and then determines which procedures can have duplicated statements [choice(1)] and which procedure calls can be duplicated [choice (2)] to minimize energy consumption with reasonable error-detection latency. Then, SPCD transforms the original program into a new program that can detect errors with minimum additional energy consumption by re-executing the statements or procedures. SPCD was simulated with benchmark programs; it requires less than 25% additional energy for error detection than previous techniques that do not consider energy consumption.

This paper proposes a pure software technique "error detection by duplicated instructions" (EDDI), for detecting errors during usual system operation. Compared to other error-detection techniques that use hardware redundancy, EDDI does not require any hardware modifications to add error detection capability to the original system. EDDI duplicates instructions during compilation and uses different registers and variables for the new instructions. Especially for the fault in the code segment of memory, formulas are derived to estimate the error-detection coverage of EDDI using probabilistic methods. These formulas use statistics of the program, which are collected during compilation. EDDI was applied to eight benchmark programs and the error-detection coverage was estimated. Then, the estimates were verified by simulation, in which a fault injector forced a bit-flip in the code segment of executable machine codes. The simulation results validated the estimated fault coverage and show that approximately 1.5% of injected faults produced incorrect results in eight benchmark programs with EDDI, while on average, 20% of injected faults produced undetected incorrect results in the programs without EDDI. Based on the theoretical estimates and actual fault-injection experiments, EDDI can provide over 98% fault-coverage without any extra hardware for error detection. This pure software technique is especially useful when designers cannot change the hardware, but they need dependability in the computer system. To reduce the performance overhead, EDDI schedules the instructions that are added for detecting errors such that "instruction-level parallelism" (ILP) is maximized. Performance overhead can be reduced by increasing ILP within a single super-scalar processor. The execution time overhead in a 4-way super-scalar processor is less than the execution time overhead in the processors that can issue two instructions in one cycle.

This paper presents a new signature monitoring technique, CFCSS (control flow checking by software signatures); CFCSS is a pure software method that checks the control flow of a program using assigned signatures. An algorithm assigns a unique signature to each node in the program graph and adds instructions for error detection. Signatures are embedded in the program during compilation time using the constant field of the instructions and compared with run-time signatures when the program is executed. Another algorithm reduces the code size and execution time overhead caused by checking instructions in CFCSS. A "branching fault injection experiment" was performed with benchmark programs. Without CFCSS, an average of 33.7 % of the injected branching faults produced undetected incorrect outputs; however, with CFCSS, only 3.1 % of branching faults produced undetected incorrect outputs. Thus it is possible to increase error detection coverage for control flow errors by an order of magnitude using CFCSS. The distinctive advantage of CFCSS over previous signature monitoring techniques is that CFCSS is a pure software method, i.e., it needs no dedicated hardware such as a watchdog processor for control flow checking. A watchdog task in multitasking environment also needs no extra hardware, but the advantage of CFCSS over a watchdog task is that CFCSS can be used even when the operating system does not support multitasking.

Design diversity has long been used to protect redundant systems against common-mode failures. The conventional notion of diversity relies on "independent" generation of "different" implementations of the same logic function. This concept is qualitative and does not provide a basis to compare the reliabilities of two diverse systems. In a recent paper, we presented a metric to quantify diversity among several designs. The problem of calculating the diversity metric is NP-complete and can be of exponential complexity. In this paper we present techniques to estimate the value of the design diversity metric. For datapath designs, we have formulated very fast techniques to calculate the value of the metric by exploiting the regularity in the datapath structures. For general combinational logic circuits, we present an adaptive Monte-Carlo simulation technique for estimating bounds on the value of the metric. The adaptive Monte-Carlo simulation technique provides accurate estimates of the design diversity metric; the number of simulations used to reach this estimate is polynomial (instead of exponential) in the number of circuit inputs. Moreover, the number of simulations can be tuned depending on the desired accuracy.

The partial reconfiguration feature of some of the current-generation Field Programmable Gate Arrays (FPGAs) can improve dependability by detecting and correcting errors in on-chip configuration data. Such an error recovery process can be executed online with minimal interference of user applications. However, because Look-up Tables (LUTs) in Configurable Logic Blocks (CLBs) of FPGAs can also implement memory modules for user applications, a memory coherence issue arises such that memory contents in user applications may be altered by the online configuration data recovery process. In this paper, we investigate this memory coherence problem and propose a memory coherence technique that does not impose extra constraints on the placement of memory-configured LUTs. Theoretical analyses and simulation results show that the proposed technique guarantees the memory coherence with a very small (on the order of 0.1%) execution time overhead in user applications.

This paper studies the behavior of stuck and resistive open defects. The effects on test results of three test conditions (supply voltage, speed, temperature) as well as test patterns applied are evaluated. Diagnosis schemes for stuck and resistive opens are also presented. Five Murphy chips are diagnosed as having stuck open defects and one chip is diagnosed as having a resistive open defect. Their experimental data match our expectations for stuck opens and resistive opens.

The test results of eight "challenge" Murphy chips that escaped either at least one of the 100% single stuck-at fault test sets or the 100% transition fault test set were analyzed. The results show that: (1) an input pattern sequence is needed to detect the defects in the eight chips; (2) the detection of a transition fault depends on the outputs at which it is observed; (3) a transition fault test set is more effective if each transition fault is detected more than once. A transition fault test set, TARO, in which each Transition fault is propagated to All the Reachable Outputs, is created and the experimental results are presented. The TARO test set detected all the eight "challenge" Murphy chips.

Triple Modular Redundancy (TMR) is known to improve reliability in real-time computing systems for short mission times. However, TMR-based systems are not effective for longer missions. For failures caused by transient faults, we have designed a new recovery scheme for TMR systems so that they can be used for long mission applications. The scheme can effectively recover computing systems from single transient faults without introducing any re-computation delay; hence, it is suitable for real-time applications. A robot controller is used as a case study. Theoretical analysis and implementation results show that, with very small hardware overhead for recovery logic, the proposed scheme can significantly improve system reliability and lengthen its lifetime. A new state restoration scheme for recovery is presented and shown to have lower overhead than a conventional restoration scheme.

This paper resolves two issues regarding diagnosis of tunneling opens: efficient screening and accurate localization. In the first part, a test pattern selection and sorting algorithm is presented. It is shown that the presented algorithm saves I/sub DDQ/(t) test time without impacting on its effectiveness. The second part of this paper presents a locating algorithm which combines both VLV and I/sub DDQ/(t) test results. This technique is shown to be able to accurately locate the tunneling opens with higher resolution than commercial single stuck-at fault diagnosis tool.

We present a technique using diverse duplication to implement concurrent error detection (CED) in sequential logic circuits. We examine three different approaches for this purpose: (1) identical state encoding of the two sequential logic implementations, duplication of flip-flops, diverse implementation of the combinational logic part (output logic and next-state logic) and comparators on flip-flop outputs and primary outputs; (2) diverse state encoding of the two implementations, duplication of flip-flops, diverse combinational logic implementation and comparators on primary outputs only; and (3) identical state encoding, parity prediction for the flip-flops, diverse combinational logic implementation, comparators on primary outputs and parity checkers on flip-flop outputs. Our results for the simulated sequential benchmark circuits demonstrate that the third approach is most efficient in protecting sequential logic circuits against multiple and common-mode failures. The computational complexity of the data integrity analysis of the third approach is of the same order as that of the first approach and is at least an order of magnitude less than that of the second approach.

Redundancy techniques like duplication and Triple Modular Redundancy (TMR) are widely used for designing dependable systems to ensure high reliability and data integrity. In this paper, for the first time, we develop fault models for common-mode failures (CMFs) in redundant systems and describe techniques to design redundant systems protected against the modeled CMFs. We first develop an input-register-CMF model that targets systems with register-files. This paper shows that, in the presence of input-register-CMFs, we can always design duplex or TMR systems that either produce correct outputs or indicate error situations when incorrect outputs are produced. This property ensures data integrity. Next, we extend the input-register-CMF model to consider systems where the storage elements of the registers are not organized in register-files; instead, the register flip-flops are placed using conventional CAD programs. For this case, we present a technique to synthesize redundant systems with guaranteed data integrity against the extended input-register-CMFs.

A weak chip is one that contains flaws-defects that do not interfere with correct circuit operation at normal conditions but may cause intermittent or early-life failures. MINVDD testing can detect weak CMOS chips. The minvdd of a chip is the minimum supply voltage value at which a chip can function correctly. It can be used to differentiate between good chips and weak chips. In the first part of this paper, we will study several types of flaws to demonstrate the effectiveness of MINVDD testing. Experimental results show that MINVDD testing is as effective as VLV testing for screening out burn-in rejects. In the second part of this paper, we propose test conditions for low voltage testing, including test voltage, test timing and test sets. Experimental results are presented to validate our proposal.

Research has shown that single stuck-at fault (SSF) N-detect test sets are effective for detecting defects not modeled by the SSF model. Experimental results showed N-detect coverage is a good metric for determining test quality. In this paper, we examine the test quality of pseudo-random Built-in-Self-Test (BIST) patterns by quantifying the relations between their N-detect coverage and test length. We theoretically derive bounds on the minimum test length of pseudo-random patterns required to achieve a given N-detect coverage. For faults with high detectability, the expected test length for N-detection is around N times the expected test length for single detection. However, for faults with low detectability, the expected test length for N-detection can be NlogN times the expected test length for detecting the fault only once; this increases the test length significantly. We also introduce the idea of effective detectability which is important for analyzing the effectiveness of BIST techniques for detecting real defects.

A low-overhead scheme for achieving complete (100%) fault coverage during built-in self test of circuits with scan is presented. It does not require modifying the function logic and does not degrade system performance (beyond using scan). Deterministic test cubes that detect the random-pattern-resistant (r.p.r.) faults are embedded in a pseudorandom sequence of bits generated by a linear feedback shift register (LFSR). This is accomplished by altering the pseudorandom sequence by adding logic at the LFSR's serial output to "fix" certain bits. A procedure for synthesizing the bit-fixing logic for embedding the test cubes is described. Experimental results indicate that complete fault coverage can be obtained with low hardware overhead. Further reduction in overhead is possible by using a special correlating automatic test pattern generation procedure that is described for finding test cubes for the r.p.r. faults in a way that maximizes bitwise correlation.

Data compression techniques based on the Lempel-Ziv (LZ) algorithm are widely used in a variety of applications, especially in communications and data storage. However, since the LZ algorithm involves a considerable amount of parallel comparisons, it may be difficult to achieve a very high throughput using software approaches on general-purpose processors. In addition, error propagation due to single-bit transient errors during LZ compression causes a data integrity problem. We present an implementation of LZ data compression on reconfigurable hardware with concurrent error detection for high performance and reliability. Our approach achieves 100 Mbps throughput using four Xilinx 4036XLA FPGA chips. We also present an inverse comparison technique for LZ compression to guarantee data integrity with less area overhead than traditional systems based on duplication. The resulting execution time overhead and compression ratio degradation due to concurrent error detection is also minimized.

This paper demonstrates that an adaptive computing system (ACS) is good platform for implementing robotic control algorithms. We show that an ACS can be used to provide both good performance and high dependability. An example of an FPGA-implemented dependable control algorithm is presented. The flexibility of ACS is exploited by choosing the best precision for our application. This reduces the amount of required hardware and improves performance. Results obtained from a WILDFORCE emulation platform showed that even using 0.35 /spl mu/m technology, an FPGA-implemented control algorithm has comparable performance with the software-implemented control algorithm in a 0.25 /spl mu/m microprocessor. Different voting schemes are used in conjunction with multi-threading and combinational redundancy to add fault tolerance to the robotic controller. Error-injection experiments demonstrate that robotic control algorithms with fault tolerance techniques are orders of magnitude less vulnerable to faults compared to algorithms without any fault tolerant features.

A tunneling-open failure mode is proposed and carefully studied. A circuit with a tunneling open could pass at-speed Boolean tests but fail VLV testing or I/sub DDQ/ testing. Theoretical calculations as well as Boolean and I/sub DDQ/ experiments confirm the existence of tunneling opens. The Murphy experimental data show that seven out of nine VLV-only failure circuits can be explained by this failure mode. All these seven circuits survived 366 hours temperature burn-in. Finally, a cost effective screening strategy is proposed.

This paper studies some manufacturing test data collected for an experimental digital IC. Test results for a large variety of single-stuck fault based test sets are shown and compared with a number of test sets based on other fault models. The defects present in the chips studied are characterized based on the chip tester responses. The data presented shows that N-detect test sets are particularly effective for both timing and hard failures. In these test sets each single-stuck fault is detected by at least N different test patterns. We also present data on the use of IDDq tests and VLV (very low voltage) tests for detecting defects whose presence doesn't interfere with normal operation during manufacturing test, but which cause early life failure.

We describe logic synthesis techniques for designing diverse implementations of combinational logic circuits in order to maximize the data integrity of diverse duplex systems in the presence of common-mode failures. Data integrity means that the system either produces correct outputs or indicates errors when incorrect outputs we produced. Design diversity has long been used to increase the data integrity of duplex systems against common-mode failures. The conventional notion of diversity is qualitative and relies on "independent" generation of "different" implementations. In a recent paper, we presented a metric to quantify, diversity among several designs. Our synthesis techniques described in this paper use the diversity metric as a cost function and maximize diversity while reducing the area overhead of the resulting diverse duplex system.

Concurrent error detection (CED) techniques (based on hardware duplication, parity codes, etc.) are widely used to enhance system dependability. All CED techniques introduce some form of redundancy. Redundant systems we subject to common-mode failures (CMFs). While most of the studies of CED techniques focus on area overhead, few analyze the CMF vulnerability of these techniques. In this paper, we present simulation results to quantitatively compare various CED schemes based on their area overhead and the protection (data integrity) they provide against multiple failures and CMFs. Our results indicate that, for the simulated combinational logic circuits, although diverse duplex systems (with two different implementations of the same logic function) sometimes have marginally higher area overhead, they provide significant protection against multiple failures and CMFs compared to other CED techniques like parity prediction.

This paper analyzes the data integrity of one of the most widely used lossless data compression techniques, Lempel-Ziv (LZ) compression. In this algorithm, because the data reconstruction from compressed codewords relies on previously decoded results, a transient error during compression may propagate to the decoder and cause a significant corruption in the reconstructed data. To recover the system from transient faults, we designed two rollback error recovery schemes for the LZ compression hardware, the "reload-retry" and "direct-retry" schemes. Statistical analyses show that the "reload-retry" scheme can recover the LZ compression process from transient faults in one dictionary reload cycle with a small amount of hardware redundancy. The "direct-retry" scheme can recover normal operations with a shorter latency but with a small degradation in the compression ratio.

Redundancy techniques are commonly used to design dependable systems to ensure high reliability, availability and data integrity. Triple Modular Redundancy (TMR) is a widely used redundancy technique that masks faults. In a TMR system, we have three implementations of the same logic function and their outputs are voted using a voter circuit. In this paper, we present a new voter design called the Word-Voter that has some distinct advantages over the bit-by-bit voting schemes used in conventional TMR systems. This paper demonstrates the usefulness of the word-voter design in increasing the data integrity (reducing the probability of corrupt outputs) of TMR systems. The area and delay overhead of the word-voter design is compared to that of the bit-by-bit voter. An efficient design of a TMR-Simplex system using the word-voter is also presented.

Hardware duplication techniques are widely used for concurrent error detection in dependable systems to ensure high availability and data integrity. These techniques are vulnerable to common-mode failures (CMFs). Use of duplex systems with diverse implementations of the two modules has been proposed in the past for protection against CMFs. In this paper, we define a category of faults, called non-self-testable faults that undermine the data integrity of dependable systems. These faults produce identical errors at the outputs of the two modules of a duplex system and can potentially be caused by CMFs. The main contributions of this paper are: (1) techniques that identify non-self-testable faults in duplex systems, and (2) design methods that reduce the number of non-self-testable faults by test point insertion. We show that our algorithm for identifying non-self-testable faults runs orders of magnitude faster than exact techniques with minimal loss of accuracy. Also, there is a significant reduction in the number of test points required for duplex systems with diverse implementations compared to duplex systems with identical implementations. Thus, we can detect common-mode failures in diverse duplex systems using very few test points. These results are especially useful for systems with user-programmable logic elements that enhance the practicality of using diverse designs in duplex systems.

Delay defects can escape detection during the normal production test flow; particularly if they do not affect any of the long paths included in the test flow. Some delay defects can have their delay increased, making them easier to detect, by carrying out the test with a very low supply voltage (VLV testing). However, VLV testing is not effective for delay defects caused by high resistance interconnects. This paper presents a screening technique for such defects. This technique, cold testing, relies on carrying out the test at low temperature. One particular type of defect, silicide open, is analyzed and experimental data are presented to demonstrate the effectiveness of cold testing.

This paper presents a survey of CMF (common-mode failures) in redundant systems with emphasis on VLSI (very large scale integration) systems. The paper discusses CMF in redundant systems, their possible causes, and techniques to analyze reliability of redundant systems in the presence of CMF. Current practice and results on the use of design diversity techniques for CMF are reviewed. By revisiting the CMF problem in the context of VLSI systems, this paper augments earlier surveys on CMF in nuclear and power-supply systems. The need for quantifiable metrics and effective models for CMF in VLSI systems is re-emphasized. These metrics and models are extremely useful in designing reliable systems. For example, using these metrics and models, system designers and synthesis tools can incorporate diversity in redundant systems to maximize protection against CMF.

In many computer systems, the contents of memory are protected by an error detection and correction (EDAC) code. Bit-flips caused by single event upsets (SEU) are a well-known problem in memory chips; EDAC codes have been an effective solution to this problem. These codes are usually implemented in hardware using extra memory bits and encoding/decoding circuitry. In systems where EDAC hardware is not available, the reliability of the system can be improved by providing protection through software. Codes and techniques that can be used for software implementation of EDAC are discussed and compared. The implementation requirements and issues are discussed, and some solutions are presented. The paper discusses in detail how system-level and chip-level structures relate to multiple error correction. A simple solution is presented to make the EDAC scheme independent of these structures. The technique in this paper was implemented and used effectively in an actual space experiment. We have observed that SEU corrupt the operating system or programs of a computer system that does not have any EDAC for memory, forcing the system to be reset frequently. Protecting the entire memory (code and data) might not be practical in software. However this paper demonstrates that software-implemented EDAC is a low-cost solution that provides protection for code segments and can appreciably enhance the system availability in a low-radiation space environment.

Design diversity has long been used to protect redundant systems against common-mode failures. The conventional notion of diversity relies on "independent" generation of "different" implementations. This concept is qualitative and does not provide a basis to compare the reliabilities of two diverse systems. In this paper, for the first time, we present a metric to quantify diversity among several designs. Based on this metric, we derive analytical reliability models that show a simple relationship between design diversity, system failure rate, and mission time. In addition, we present simulation results to demonstrate the effectiveness of design diversity in Duplex and Triple Modular Redundant (TMR) systems. For independent multiple-module failures, we show that, mere use of different implementations does not always guarantee higher reliability compared to redundant systems with identical implementations-it is important to analyze the reliability of redundant systems using our metric. For common-mode failures and design faults, there is a significant gain in using different implementations-however, as our analysis shows, the gain diminishes as the mission time increases. Our simulation results also demonstrate the usefulness of diversity for enhancing the self-testing properties of redundant systems.

A new synthesis technique for designing finite state machines with on-line parity checking is presented. The output logic and the next-state logic of the finite state machines are checked independently. By checking parity on the present state instead of the next state, this technique allows detection of errors in bistable elements (that were hitherto not detected by many previous techniques) while requiring no changes in the original machine specifications. This paper also examines design choices with respect to parity prediction circuits. Two such examined choices are the multi-parity-group and the single-parity-group techniques. A new state encoding technique based on the JEDI program is developed for the synthesis of the next-state logic with an additional parity output. Synthesis results produced by our proposed procedure for the MCNC'89 FSM benchmark circuits show on average a 25% reduction in literal counts compared to previous techniques.

This paper presents a new fault-tolerance technique for cache memories. Current fault-tolerance techniques for caches are limited either by the number of faults that can be tolerated or by the rapid degradation of performance as the number of faults increases. In this paper, we present a new technique that overcomes these two problems. This technique uses a special Programmable Address Decoder (PAD) to disable faulty blocks and to re-map their references to healthy blocks. Simulation results show that the performance degradation of direct-mapped caches with PAD is smaller than the previous techniques. However, for set-associative caches, the overhead of PAD is primarily advantageous if a relatively large number of faults is to be tolerated. The area overhead was estimated at about 10% of the overall cache area for a hypothetical design and is expected to be less for actual designs. The access time overhead is negligible.

We present a new output-encoding problem as follows. We are given a specification table, such as a truth table or a finite state machine (FSM) state table, where some of the outputs are specified in terms of ones, zeroes, and don't cares, and others are specified symbolically. The number of bits for encoding the output symbols may also be specified. We have to determine a binary code for each symbol of the symbolically specified output column such that the total number of output functions to be implemented after encoding the symbolic outputs and compacting the output columns is minimum. In this paper, we develop an exact algorithm to solve the above problem, analyze the worst case time complexity of the algorithm, and present experimental data to validate the claim that our encoding strategy helps to reduce the area of a synthesized circuit. In addition, we have investigated the possibility of using simple logical combinations of the already specified output columns to facilitate further reduction in the number of output functions.

An automated logic synthesis procedure, called RP-SYN, is described for synthesizing random pattern testable circuits. RP-SYN takes as an input a two-level description of a circuit and a constraint on the minimum fault detection probability (threshold below which faults are considered random pattern-resistant), and generates a multilevel implementation which satisfies the constraint while minimizing the literal count. RP-SYN identifies random-pattern-resistant faults and eliminates them through testability-driven factoring combined with test point insertion. By moving the task of test point insertion from the back-end into the synthesis process, RP-SYN reduces design time and enables better optimization of the resulting implementation. Results are shown for benchmark circuits which indicate that RP-SYN can generally reduce the random pattern test length by at least an order of magnitude with only a small area overhead.

We investigate defects in CMOS domino gates and derive the test conditions for them. Very-Low-Voltage Testing can improve the defect coverage, which we define as the maximum detectable resistance, of intra-gate and inter-gate resistive shorts. We also propose a new keeper design for CMOS domino circuits. The new keeper design has low performance impact and is best for small CMOS domino gates. Keepers can eliminate the floating nodes in CMOS domino logic gates.

This paper presents the results for very detailed studies of pattern and timing-dependent failures from the 309 dies in the retest of an experimental test chip. 22 out of the 50 CUTs with pattern-dependent failures had test escapes if the test sets were reordered. Some timing-dependent failures became timing-independent combinational (TIC) defects at very low voltage. Multiple-detect single stuck fault test sets have high transition fault coverage. Most dies with TIC or non-TIC defects were close to gross failures or next to the wafer periphery.

Describes the ROAR (Reliability Obtained by Adaptive Reconfiguration) project. Adaptive computing system (ACS) environments provide opportunities for dependable computing solutions. We identify some of the issues in traditional dependable computing solutions. We show that adaptive and reconfigurable environments address these issues and also enable new innovative techniques that enhance the dependability of systems. Natural redundancy in applications and new synthesis algorithms are two other opportunities we use in enhancing the dependability.

An experimental test chip was designed and manufactured to evaluate different test techniques. Based on the results presented in the wafer probe, 309 out of 5491 dies that passed the Stage 1 tests were packaged for further investigation. This paper describes the experimental setup and the preliminary results for the final package test. We focus on the correlation among various defect classes, including IDDQ failures, Very-Low-Voltage (VLV) failures, timing-independent combinational (TIC) defects, and non-TIC defects. We used 2 supply voltages for VLV tests. Two test speeds were used at each supply voltage. 9 dies failed only the VLV Boolean tests, and 7 of these were confirmed to have had high IDDQ measurement results. We also investigated the defect classes of the test escapes for 100% single stuck fault (SSF), transition fault, and IDDQ test sets.

We present a new output encoding problem as follows: Given a specification table, such as a truth table or a finite state machine state table, where some of the outputs are specified in terms of 1s, 0s and don't cares, and others are specified symbolically, and assuming that the minimum number of bits are used to encode the symbolic outputs ([log/sub 2/] bits for n symbolic outputs), determine a binary code for each symbol of the symbolically specified output column such that the total number of output functions to be implemented after encoding the symbolic outputs and compacting the columns is minimum. There are several applications of this output encoding problem, one of which is to reduce the area overhead while implementing scan or pseudo-random BIST in a circuit with one-hot signals. We develop an exact algorithm to solve the above problem and present experimental data to validate the claim that our encoding strategy helps to reduce the area of a synthesized circuit.

While previous research has focused on deterministic testing of bridging faults, this paper studies pseudo-random testing of bridging faults and describes a means for achieving high fault coverage in a built-in self-test (BIST) environment. Bridging faults are generally more random pattern testable than stuck-at faults, but examples are shown to illustrate that some bridging faults can be much less random pattern testable than stuck-at faults. A fast method for identifying these random-pattern-resistant bridging faults is described. State-of-the-art test point insertion techniques, which are based on the stuck-at fault model, are inadequate. Data is presented which indicates that even after inserting test points that result in 100% single stuck-at fault coverage, many bridging faults are still not detected. A test point insertion procedure that targets both single stuck-at faults and non-feedback bridging faults is presented. It is shown that by considering bath types of faults when selecting the location for test points, higher fault coverage can be obtained with little or no increase in overhead. Thus, the test point insertion procedure described here is a low-cost way to improve the quality of built-in self-test.

Tri-state buses and pass transistor logic are used in many complex applications to achieve high performance and small area. Such circuits often contain logic requiring one-hot signals. In a scan-based design, one-hot values on these signals may not be maintained during the scan-in and scan-out operations. Also, the presence of faults, the existence of don't care conditions and the use of random patterns for testing the circuit in a scan or BIST environment may lead to non-one-hot values on these one hot signals, resulting in abnormal circuit behavior and possible circuit damage. In this paper, we present new techniques for synthesizing scan-based designs so that one-hot values are maintained on the one-hot signals during all modes of operation. One of our synthesis techniques often generates designs with no area overhead-the designs are smaller than those that do not ensure safe scan operation. In addition, we propose a scan path design that has no performance overhead during the normal mode of operation and ensures that only valid states appear on the bistables during test mode, thus guaranteeing safe scan operations.

A stress procedure for reliability screening, SHOrt Voltage Elevation (SHOVE) test, is analyzed here. During SHOVE, test vectors are run at higher-than-normal supply voltage for a short period. Functional tests and IDDQ tests are then performed at the normal voltage. This procedure is effective in screening oxide thinning, which occurs when the oxide thickness of a transistor is less than expected, as well as via defects. The stress voltage of SHOVE testing should be set such that the electric field across an oxide is approximately 6MV/cm. The stress time can be calculated by using the "effective oxide thinning" model. We will also discuss the requirements on input vectors for stressing complementary CMOS logic gates and CMOS domino logic gates efficiently.

A new approach for testing the bistable elements (latches and flip-flops) in scan chain circuits is presented. In this approach, we generate test patterns that apply a checking experiment to each bistable element in the circuit while checking their response. Such tests guarantee the detection of all detectable combinational defects inside the bistable elements. The algorithm is implemented by modifying an existing stuck-at combinational test pattern generator. The number of test patterns generated by the new program is comparable to the number of traditional stuck-at patterns. This shows that this approach is practical for large circuits.

Scan paths are commonly used in digital design to improve the testability of sequential circuits since a full scan path provides complete controllability and observability for every bistable element. A traditional scan path is implemented after the circuit has been designed, with little regard to the actual circuit function. High-level synthesis can exploit knowledge of the circuit function to synthesize a scannable circuit that has less area overhead than a circuit that has scan inserted after synthesis. In this paper, we discuss how synthesis algorithms that target orthogonal scan can result in final designs that are fully scanned and have as little as one-third the overhead of a traditional scan path.

This paper presents parallel signature design techniques that guarantee the aliasing probability to be less than 2/L, where L is the test length. Using y signature samples, a parallel signature analysis design is proposed that guarantees the aliasing probability to be less than (y/L)/sup y/2/. Inaccuracies and incompleteness in previously published bounds on the aliasing probability are discussed. Simple bounds on the aliasing probability are derived for parallel signature designs using primitive polynomials.

This paper presents a procedure for synthesizing multilevel circuits with concurrent error detection. All errors caused by single stuck-at faults are detected using a parity-check code. The synthesis procedure (implemented in Stanford CRCs TOPS synthesis system) fully automates the design process, and reduces the cost of concurrent error detection compared with previous methods. An algorithm for selecting a good parity-check code for encoding the circuit outputs is described. Once the code has been selected, a new procedure called structure-constrained logic optimization is used to minimize the area of the circuit as much as possible while still using a circuit structure that ensures that single stuck-at faults cannot produce undetected errors. It is proven that the resulting implementation is path fault secure, and when augmented by a checker, forms a self-checking circuit. The actual layout areas required for self-checking implementations of benchmark circuits generated with the techniques described in this paper are compared with implementations using Berger codes, single-bit parity, and duplicate-and-compare. Results indicate that the self-checking multilevel circuits generated with the procedure described here are significantly more economical.

The detectability of delay flaws can be improved by testing CMOS IC's with a very low supply voltage-between 2 and 2.5 times the threshold voltage V/sub t/ of the transistors. A delay flaw is a defect that causes a local timing failure but the failure is not severe enough to cause malfunctioning. Delay flaws caused by degraded signals and gates with lower drive capability than expected are considered. This paper investigates the voltage dependence of the effects of delay flaws and derives the test conditions for them.

A 25 k gate Test Chip was designed and manufactured to evaluate different test methods for scan-designed circuits. The design of the chip, the experiment, and preliminary experimental results were presented at ITC'95. This paper presents results for different clock speeds and clocking modes (at-speed and delay), and uses this data to characterize the behavior of the defective parts. It was found that timing-related defects are common, and the escape rate for different test techniques on these parts is discussed.

Orthogonal scan paths, which follow the path of the data flow, can be used in data path designs to reduce the test overhead-area, delay and test application time by sharing functional and test logic. Orthogonal scan paths are orthogonal to traditional scan paths. Judicious ordering of the registers in the orthogonal scan path can allow the scan path to be implemented entirely with existing interconnect, resulting in no additional wiring to connect the scan path and no performance degradation due to additional loading on the bistable outputs. Taking the orthogonal scan path into account during high-level synthesis operations such as register allocation allows for a better final solution, but orthogonal scan paths can also be used with non-synthesized data path. Orthogonal scan paths have roughly half the overhead of traditional scan paths and greatly reduce the test application time. TOPS, Stanford CRC's synthesis-for-test tool, has been modified to implement orthogonal scan paths for synthesized circuits.

This paper presents a low-overhead scheme for the built-in self-test (BIST) of circuits with scan. Complete (100%) fault coverage is obtained without modifying the function logic and without degrading system performance (beyond using scan). Deterministic test cubes that detect the random-pattern-resistant faults are embedded in a pseudo-random sequence of bits generated by a linear feedback shift register (LFSR). This is accomplished by altering the pseudo-random sequence by adding logic at the LFSR's serial output to "fix" certain bits. A procedure for synthesizing the bit-fixing logic for embedding the test cubes is described. Experimental results indicate that complete fault coverage can be obtained with low hardware overhead. Also, the proposed approach permits the use of small LFSRs for generating the pseudo-random bit sequence. The faults that are not detected because of linear dependencies in the LFSR can be detected by embedding deterministic cubes at the expense of additional bit-fixing logic. Data is presented showing how much additional logic is required for different size LFSRs.

Some weak static CMOS chips can be detected by testing them with a very low supply voltage-between 2 and 2.5 times the threshold voltage V/sub t/ of the transistors. A weak chip is one that contains a flaw-an imperfection that does not interfere with correct operation at rated conditions but which may cause intermittent or early-life failures. This paper considers several types of flaws and derives the test conditions for them. It also proposes two approaches for determining the appropriate test speed for very-low-voltage testing.

Designing a testable circuit is often a two step process. First, the circuit is designed to conform to the functional specifications. Then, the testability aspects are added. By taking the test strategy into account during the synthesis of the circuit, the overhead due to the test features can be reduced. We present a synthesis-for-scan procedure, called beneficial scan, that orders the scan chain(s) during logic synthesis to minimize the area and performance overhead due to the scan-path by sharing the functional and the test logic. The results show that circuits synthesized with beneficially-ordered scan chains consistently have smaller area and are easier to route than circuits with traditional MUXed flip-flop scan-paths.

This paper presents an innovative method for inserting test points in the circuit-under-test to obtain complete fault coverage for a specified set of test patterns. Rather than using probabilistic techniques for test point placement, a path tracing procedure is used to place both control and observation points. Rather than adding extra scan elements to drive the control points, a few of the existing primary inputs to the circuit are ANDed together to form signals that drive the control points. By selecting which patterns the control point is activated for, the effectiveness of each control point is maximized. A comparison is made with the best previously published results for other test point insertion methods, and it is shown that the proposed method requires fewer test points and less overhead to achieve the same or better fault coverage.

This paper proposes a new technique, called scan-mapping, for applying two-pattern tests in a standard scan design environment. Scan-mapping is performed by shifting the first pattern (V/sub 1/) into the scan path and then using combinational mapping logic to generate the second pattern (V/sub 2/) in the next clock cycle. The mapping logic is placed in the scan path and avoids the performance degradation of using more complex scan elements to apply two-pattern tests. A procedure is described for synthesizing the mapping logic required to apply a set of two-pattern tests. Scan-mapping can be used in deterministic testing to apply two-pattern tests that can't be applied using scan-shifting or functional justification, and it can be used in built-in self-testing (BlST) to improve the fault coverage for delay faults. Experimental results indicate that, for deterministic testing, scan-mapping can reduce area overhead and test time compared with using complex scan elements; and for pseudo-random testing, scan-mapping can significantly improve the fault coverage using only a small amount of mapping logic.

This paper develops a closed-form formula, f(k), to count the number of transition-tour sequences of length k for bistable machines. It is shown that the function f(k) is related to Fibonacci numbers. Some applications of the results in this paper are in the areas of testable sequential machine designs, random testing of register data paths, and qualification tests for random pattern generators.

This paper presents a simple technique for locating single gate-level faults in combinational circuits. This technique consists of three processes; first, finding possible error sources from the observed errors, second, deducing possible faults from them and finally eliminating faults incapable of being in the circuit under test. Computer simulation was done for ISCAS'85 benchmark circuits to evaluate its performance. The computation time is very short while a high diagnostic resolution may not always be guaranteed. Therefore this would be useful as a preprocess for analyzing the physical defect by various tools such as scanning electron microscopy, electron beam probing and light emission microscopy.

An experiment has been designed to evaluate multiple testing techniques for combinational circuits. To perform the experiment, a 25 k gate CMOS Test Chip has been designed, manufactured (5491 devices),and evaluated with over 300 tests. The chip contains five types of CUTs derived from functions in production ASICs.

This paper describes the testing of a chip especially designed to facilitate the evaluation of various test techniques for combinational circuitry. The different test sets and test conditions are described. Several tables show the results of voltage tests applied, either at rated speed or 2/3 speed, to each defective CUT. Data for CrossCheck, Very-Low-Voltage, IDDQ and delay tests are also given.

New digital designs often include scan chains; high quality economical test is the reason. While many techniques exist for testing combinational circuitry, little attention has been paid to testing the sequential elements (latches and flip-flops). This paper presents techniques for testing latches included in either shift registers or scan chains. We show that a test that applies all transitions to a latch-based shift register is an exhaustive functional test of all of the latches in the register. A more complex test is required for a scan chain. We present a procedure for deriving an exhaustive functional test of the latches in a scan chain. The shift register and scan chain tests presented do not depend on the latch implementation; they detect all detectable combinational defects (those that do not introduce additional states into a latch). We assume that only one latch is defective.

During built-in self-test (BIST), the set of patterns generated by a pseudo-random pattern generator may not provide a sufficiently high fault coverage. This paper presents a new technique for synthesizing combinational mapping logic to transform the set of patterns that are generated. The goal is to satisfy test length and fault coverage requirements while minimizing area overhead. For a given pseudo-random pattern generator and circuit under test, there are many possible mapping functions that will provide a desired fault coverage for a given test length. This paper formulates the problem of finding a mapping function that can be implemented with a small number of gates as a one of finding a minimum rectangle cover in a binate matrix. A procedure is described for selecting a mapping function and synthesizing mapping logic to implement it. Experimental results for the procedure are compared with published results for other methods. It is shown that by performing iterative global operations, the procedure described in this paper generates mapping logic that requires less hardware overhead to achieve the same fault coverage for the same test length.

Necessary and sufficient conditions for exhaustive functional tests (checking experiments) of 2-state latches are derived. These conditions are used to derive minimum-length checking experiments. The checking experiment for the D-latch is simulated using an HSpice implementation of the transmission gate latch. All detectable shorted interconnects, open interconnects, short-to-power, short-to-ground, stuck-open, and stuck-on faults are detected. A pin fault test set and a multiplexer-based test set are also simulated. These tests miss some faults detected by the checking experiment.

In this paper we propose a new apparatus for embedding deterministic patterns in pseudo-random sequences, with application to at-speed BIST. We employ an arbitrary length Shift Register driven by a LFSR (LFSR/SR) with the size of the LFSR dependent only on the number of care bits in any test vector. We provide an efficient method to compute positions of bit-patterns at arbitrarily chosen tap configurations in the LFSR/SR sequence. Hence, one can make an optimal choice of test segments (seeds) while taking inherent advantage of don't care bits in test vectors, say corresponding to random pattern resistant faults. The length of the LFSR/SR can be arbitrarily increased to feed several interconnected logic blocks such that all the care bits of any deterministic test vector can be predictably generated without compromising computational efficiency.

This paper presents a new approach for on-chip test pattern generation. The set of test patterns generated by a pseudo-random pattern generator (e.g., an LFSR) is transformed into a new set of patterns that provides the desired fault coverage. The transformation is performed by a small amount of mapping logic that decodes sets of patterns that don't detect any new faults and maps them into patterns that detect the hard-to-detect faults. The mapping logic is purely combinational and is placed between the pseudo-random pattern generator and the circuit under test (CUT). A procedure for designing the mapping logic so that it satisfies test length and fault coverage requirements is described. Results are shown for benchmark circuits which indicate that an LFSR plus a small amount of mapping logic reduces the test length required for a particular fault coverage by orders of magnitude compared with using an LFSR alone. These results are compared with previously published results for other methods, and it is shown that the proposed method requires much less overhead to achieve the same fault coverage for the same test length.

The paper introduces an assertion scheme based on the backward error analysis for error detection in algorithms that solve dense systems of linear equations, Ax=b. Unlike previous methods, this backward error assertion model is specifically designed to operate in an environment of floating point arithmetic subject to round-off errors, and it can be easily instrumented in a Watchdog processor environment. The complexity of verifying assertions is O(n/sup 2/), compared to the O(n/sup 3/) complexity of algorithms solving Ax=b. Unlike other proposed error detection methods, this assertion model does not require any encoding of the matrix A. Experimental results under various error models are presented to validate the effectiveness of this assertion scheme.>

Opens in BiCMOS structures are analyzed here. It is shown that some opens cannot be detected by stuck-fault or other functional tests, since some transistors in BiCMOS gates do not affect the logical function of the gate. A switch-level model for CMOS circuits is extended to include bipolar devices. With this switch-level model, opens that cannot be detected by stuck-faults or other functional tests are easily identified. It is also shown that, in BiCMOS circuits, an open defect in one transistor can accelerate the wearout of another nondefective transistor.>

This paper presents new logic synthesis techniques for generating multilevel circuits with concurrent error detection based on a parity-check code scheme that can detect all errors caused by single stuck-at faults. These synthesis techniques fully automate the design process and allow for a better quality result than previous methods thereby reducing the cost of concurrent error detection. An algorithm is described for selecting a good parity-check code for encoding the outputs of a circuit. Once the code has been chosen, a new procedure called structure-constrained logic optimization is used to minimize the area of the circuit as much as possible while still using a circuit structure that ensures that single stuck-at faults cannot produce undetected errors. The implementation that is generated is path fault secure and when augmented by a checker forms a self-checking circuit. Results indicate that self-checking multilevel circuits can be generated which require significantly less area than using duplication.

Previous approaches to designing random pattern testable circuits use post-synthesis test point insertion to eliminate random pattern resistant (r.p.r.) faults. The approach taken in this paper is to consider random pattern testability during logic synthesis. An automated logic synthesis procedure is presented which takes as an input a two-level representation of a circuit and a constraint on the minimum fault detection probability (threshold below which faults are considered r.p.r.) and generates a multilevel implementation that satisfies the constraint while minimizing the literal count. The procedure identifies r.p.r. faults and attempts to "eliminate" them through algebraic factoring. If that is not possible, then test points are inserted during the synthesis process in a way that minimizes the number of test points that are required. Results are shown for benchmark circuits which indicate that the proposed procedure can generally reduce the random pattern test length by at least an order of magnitude with only a small area overhead.

A new technique for on-line checking of digital systems is proposed. It is shown that, under certain timing restrictions, an off-line delay-fault testing method called Stability Checking can be used for on-line checking. Efficient CMOS on-line Stability Checker designs are presented, and an algorithm for meeting timing restrictions is described. Benchmark results are shown. On-line Stability Checkers detect errors caused by most common reliability failures and transients, and are shown to perform almost as well as duplication at a fraction of the hardware cost. Since outputs are checked independently, good diagnosability is possible.>

To improve the quality of CMOS digital circuits, more complex fault models than single stuck-at have been proposed. This paper focuses on the effect of inaccurate delay modeling on delay fault testing. It is shown that accurate delay models are needed for effective delay fault testing. This is particularly important for large timing optimized circuits with many paths. Limitations of the path delay fault model are shown, and even the assumption that 2-pattern tests are sufficient for delay testing is shown to have limitations.>

Opens in different BiCMOS structures are analyzed here. It is shown that some opens cannot be detected by stuck-fault tests, since some transistors in BiCMOS gates do not affect the logical function of the gate. It is also shown that, in BiCMOS circuits, an open defect in a particular transistor can cause an acceleration in the wearout of another non-defective transistor.>

Correctness of the execution of sorting programs can be checked by two assertions: the order assertion and the permutation assertion. The order assertion checks if the sorted data is in ascending or descending order. The permutation assertion checks if the output data produced by sorting is a permutation of the original input data. Permutation and order assertions are sufficient for the detection of errors in the execution of sorting programs; however, in terms of execution time these assertions cost the same as sorting programs. An assertion, called the order-sum assertion, that has lower execution cost than sorting programs is derived from permutation and order assertions. The reduction in cost is achieved at the expense of incomplete checking. Some metrics are derived to quantify the effectiveness of order-sum assertion under various error models. A natural connection between the effectiveness of the order-sum assertion and the partition theory of numbers is shown. Asymptotic formulae for partition functions are derived.>

This paper introduces new design and synthesis techniques that reduce the area and performance overhead of built-in self-test (BIST) architectures such as circular BIST and parallel BIST. Our goal is to arrange the system bistables into scan paths such that some of the BIST and scan logic is shared with the functional logic. Logic sharing is possible when scan dependence is introduced in the design. Other BIST design techniques attempt to avoid scan dependence because it can reduce the fault coverage of embedded, multiple input signature registers (MISRs). We show that introducing certain types of scan dependence in embedded MISRs can result in reduced overhead and improved fault coverage. We present our results for benchmark circuits that have been synthesized to take advantage of scan dependence in a circular BIST architecture.>

In this paper we propose a very-low-voltage (VLV) testing technique for CMOS logic ICs. Voltage dependence of CMOS logic circuit operation in the presence of resistive shorts and hot carrier damage is studied. It is shown that at certain much-lower-than-normal power supply voltage, weak CMOS logic ICs due to the presence of these flaws can be forced to malfunction while truly good ICs continue to function. Very-low-voltage testing also detects pattern dependent faults caused by resistive shorts. Because of its simplicity and because there is no overhead associated with it, very-low-voltage testing can easily be applied to chips and circuit boards as a production test, field test, or failure diagnosis technique.>

The goal of IC production test is to avoid selling bad parts. The goal of fault grading is to assure that the test is so thorough that only an acceptably small fraction of shipped parts are bad. Fault grading is almost always based on a single-stuck fault, ssf, model.>

The resistance dependence, voltage dependence, temperature dependence, and pattern dependence properties of CMOS logic gate operation in the presence of gate oxide shorts are analyzed. The analysis is based on realistic defect models that incorporate the resistive nature of gate oxide shorts and the difference between gate oxide shorts in n- and p-channel transistors.>

Resistive “shorts“ {unplanned connections) within BiCMOS gates are studied. A simple model to determine the output of a faulty BiCMOS gate is derived. Defective BiCMOS NAND gates with various resistive shorts are simulated using SPICE. Two types of new faults are identified. These faults, which may escape functional tests, are explained through the simple model. Simulation results show that current monitoring is an effective way to detect these faults.

It is shown that the aliasing probability is bounded above by (1+ epsilon )/L approximately=1/L ( epsilon small for large L) for test lengths L less than the period, L/sub c/, of the signature polynomial; for test lengths L that are multiples of L/sub c/, the aliasing probability is bounded above by 1; for test lengths L greater than L/sub c/ and not a multiple of L/sub c/, the aliasing probability is bounded above by 2/(L/sub c/+1). These simple bounds avoid any exponential complexity associated with the exact computation of the aliasing probability. Simple bounds also apply to signature analysis based on any linear finite state machine (including linear cellular automaton). From these simple bounds it follows that the aliasing probability in a signature analysis design using beta intermediate signatures is bounded by ((1+ epsilon )/sup beta / beta /sup beta /)/L/sup beta /, for beta>

A new method for delay fault testing of digital circuits is presented. Unlike catastrophic failures that simply have incorrect steady-state logic values at the circuit outputs, delay faults change the shape of the output waveforms by moving the signal transitions in time. Therefore, since the output waveforms contain information about the circuit delays, instead of only latching the outputs at the sampling time, the output waveforms between samples are analyzed as well. Two classes of output waveform analysis are discussed. In the first technique, the output waveform is observed for any changes after the sampling time, since in a fault-free circuit, the outputs are expected to have stabilized at the desired logic values. In the second technique, information is extracted from the faulty and fault-free waveforms before the sampling time, and compared for any differences. Circuits for the waveform analyzers are presented to show that the method is feasible, and experimental results are given.

Two-pattern test capabilities of autonomous test pattern generator (TPG) circuits for use in built-in self- testing of CMOS circuits are investigated. The TPG circuits treated here are not limited to LFSRs but include arbitrary autonomous linear sequential circuits. Based on the transi- tion matrix of a circuit, a method is shown to analyze how many distinct transitions can occur on each subset of the state variables. The two-pattern test capabilities of LFSRs, cellular automata, and their fast parallel implementation are explored using transition coverage as the metric. The relationships with dual circuits and reciprocal circuits are phase shift as the metric is shown in (Bardell 901.

This paper studies the effects of shorts within CMOS gates. Dynamic as well as static gate properties are analyzed as a function of the short’s resistance. Increased propagation delay is found to be a common dynamic effect. Circuit behavior can change drastically with small variations in a short’s resistance. It is found that faults caused by transistor gate-to-source and gate-to-drain shorts can be dependent not only on inputs of gates containing the faults but also on other signals. This pattern dependence due to “resistive shorts” can invalidate tests generated using normal TPG procedures.

in previous work a simple bound, ~+2 , on the aliasing probability in serial signature analysis for a random test pattern of length L was derived. This simple bound is sharpened here by almost a factor of two. For serial signature analysis, it is shown that the I+& 1 aliasing probability is bounded above by - = L (E L small for large L) for test lengths L less than the period, Lc, of the signature polynomial. The simple bounds derived are compared with exact as well as experimentally measured aliasing probability values. It is conjectured that L-l is the best monotonic bound on the aliasing probability for serial signature analysis.

It is shown that the traditional approach to diagnosing stuck-at faults with fault dictionaries generated for stuck-at faults is not appropriate for diagnosing CMOS bridging faults. A novel technique for using stuck-at-fault dictionaries to diagnose bridging faults is described. Teradyne's LASAR was used to simulate bridging and stuck-at faults in a number of combinational circuits, including parity trees, multiplexers, and the 74ASCI181 4-b, 16-function ALU (arithmetic and logic unit). When the traditional technique was used, between 30%-50% of the bridging faults were mis-diagnosed, with the presence of a failure indicated on a fault-free node. In addition, as the stuck-at-fault diagnostic ability of a test increased, the bridging fault diagnostic ability decreased. By use of the new technique. over 92% of the bridging faults in the circuits used for this research were diagnosed correctly and less than 4% led to misleading diagnoses.>

A control-flow checking method using extended-precision checksums and watchdog assists is proposed. Control-flow checking based on extended-precision checksums is shown to have low error detection latency compared to previously proposed methods. Analytical measures are derived to demonstrate the effectiveness of using extended-precision checksums for control flow checking. It is shown that the error detection latency in the extended-precision-checksum-based control-flow checking remains relatively constant for both single and multiple sequence errors. In the case of signature-based methods, error detection latency increases linearly with the number of sequence errors. A watchdog assist architecture for control-flow checking in programs which addresses several architecture issues is proposed. This watchdog assist architecture can support control-flow checking for multiprocessor, multiprogramming, and cache-based environments. The Hewlett-Packard Precision Architecture is used as an example architecture to demonstrate the feasibility of watchdog assists.>

The effectiveness of extended-precision checksums is thoroughly analyzed. It is demonstrated that the extended-precision checksums most effectively exploit natural redundancy occurring in program codes. Honeywell checksums and cyclic redundancy checks are compared to extended-precision checksums. Two's complement, unsigned, and one's complement arithmetic checksums are treated in a unified manner. Results are also extended to any general radix-p arithmetic checksum. Asymptotic and closed-form formulas of aliasing probabilities for the various error models are derived.>

The critical path technique for determining the single stuck-at faults detected by a test is extended to multiple faults by defining masking paths. A masking tree is used to represent the masking relationships among individual faults. These relationships are then used to determine which multiple faults are actually detected by a test.>

An analysis is presented of error detection characteristics when galois checksums and arithmetic checksums are used simultaneously. By generalizing previous results, it is shown that galois checksums and arithmetic checksums exhibit orthogonal characteristics with respect to error detection. An analytic proof of orthogonality is presented for certain restricted cases. These orthogonal characteristics hold good for equally likely errors, restricted column errors, and restricted word errors. Double-length galois checksums are compared with combined arithmetic and galois checksums.>

Minimal test sets for different implementations of multiplexer are derived. The length of the minimal test set of any multiplexer is shown to be at least twice the number of data inputs. A set of pseudoexhaustive patterns is derived for different implementation. In all the implementations investigated, the length of the test was only 1.5 times the minimal length. The detectability profile of the different multiplexer implementations are derived. These profiles are used to determine the expected fault coverage of pseudorandom test patterns as a function of the test length. This fault coverage compared with coverage from actual simulations.>

The author addresses the question of knowledge transfer between industry and academy in the area of integrated-circuit (IC) testing. He first examines the movement of theory from academia to industrial practice, finding two problems: designers are evaluated on meeting deadlines not on testability; and most designers do not know how to ensure testability in a systematic fashion. The solutions are technological-implementation of either design rules and design-rule checkers to guarantee testability or the use of testability measure programs-and educational, i.e. teaching design for testability as an integral part of logic design. The author then discusses the problems of teaching the relevance of theory to current industrial practice at the University ball. He finds more problems and lists the causes of the irrelevance of theory, including industry-university consulting policies, funding mechanisms that depend on peer review, and the frequent difficulty of determining the relevance of novel theory before its industrial applications.>

The authors examine the question of whether fault grading is necessary and if yes, how high the single-stuck fault coverage must be? They show that, not only is fault grading required, but that extremely high single stuck fault coverage is probable necessary. The results presented are extensions of previous work in this area by T.W. Williams (1985). The authors discuss only functional or Boolean testing, which does not involve measurement, but determines whether logic functions are correct. The question of how thorough a Boolean test procedure need be is the main focus. The need for extremely thorough testing is demonstrated.>

A method is described that provides high detection of bridging faults without requiring extensive fault simulation. Bridging fault coverage can be increased by doing fault simulation and test generation for bridging faults that are identified as hard to detect. These bridging faults occur between nodes that rarely, if ever, differ, or that seldom change value. In addition, if the nodes in the fault-free circuits toggle often, feedback faults are easier to detect. This is true even if the nodes involved always have equal values. Methods for identifying such nodes have been presented. These methods use results available from fault-free simulations. A simple solution is to randomly reorder the test vectors to increase toggling and therefore increase bridging fault coverage. As a result, computer time for test generation will be only slightly greater than the time required for stuck-at fault generation alone.>

An approach to quantify the digital testing system (DTS) attributes is presented. The quantification will help in determining criteria according to which benchmark circuits are selected. Two main parameters that can be used in the comparison are the speed of operation and memory requirements. Attempts are made to relate each of these two parameters to different attributes of the DTS. Experiments were carried out using a commercial automatic test-pattern generator to generate test sets for some ISCAS circuits. The results of the experiments are presented.>

A pseudoexhaustive-test implementation technique is presented which combines the advantages of hardware partitioning and sensitized partitioning, offering lower hardware overhead than hardware partitioning, and lower test-set generation complexity and higher fault coverage than sensitized partitioning.>

Concurrent system-level error detection techniques using a watchdog processor are surveyed. A watchdog processor is a small and simple coprocessor that detects errors by monitoring the behavior of a system. Like replication, it does not depend on any fault model for error detection. However, it requires less hardware than replication. It is shown that a large number of errors can be detected by monitoring the control flow and memory-access behavior. Two techniques for control-flow checking are discussed and compared with current error-detection techniques. A scheme for memory-access checking based on capability-based addressing is described. The design of a watchdog for performing reasonable checks on the output of a main processor by executing assertions is discussed.>

A design technique is given for linear-feedback shift registers (LFSR) that generate test patterns for pseudoexhaustive testing of networks with restricted output dependency. This technique is based on cyclic code theory. Examples indicate that LFSRs based on cyclic codes are easier to implement and have lower hardware overhead than LFSRs that use other linear codes.>

A novel scheme to design built-in self-test programmable logic arrays (PLAs) implemented with CMOS technology is described, which is attractive for large arrays. These PLAs can perform function-independent self-test at normal operating speed, can detect CMOS switch-level faults, and have a lower area overhead than any other BIST scheme. A sequential parity checking technique is used to test for the AND and OR arrays of the PLA. This technique does not require any XOR cascade to evaluate parity data as in the parallel checking technique used by other schemes, thus achieving an order of magnitude reduction in total testing time. The method accounts for switch-level stuck-open and stuck-on faults in addition to conventional stuck-at, crosspoint, and bridging faults. A novel circuit design technique was used to implement the test pattern generator for product lines. It makes use of a Johnson counter and a two-level decoding network to obtain a very low area overhead and to match the pitch between the PLA and the test circuitry.>

A probabilistic model for pseudorandom testing of combinational circuits is presented. The expected fault coverage is shown to be accurately approximated as a series of exponentials that depends on the test length and the fault detectabilities. The derivations do not require the pattern generator to have the same number of stages as there are network inputs.>

Two hybrid schemes for the design of maximum-length sequence generators (MLSGs) are presented. Compared to an n-stage maximum-length LFSR (for generating 2/sup n/-1 nonzero distinct states) that uses m exclusive-or (XOR) gates, this hybrid MLSG will use exactly (m+1)/2 XOR gates if its characteristic polynomial meets certain requirements. For applications such as exhaustive testing, this hybrid MLSG is then reconfigured to include the all-zero state. It is shown that the reconfiguration is very simple and the hardware overhead is low.>

Implementation methods based on cyclic codes are presented for pseudoexhaustive testing of combinational logic networks with restricted output dependency. A modified linear-feedback shift register (LFSR) is used to generate exhaustive test patterns for every output of the circuit. All detectable, combinational faults (those that do not change a combinational circuit to a sequential circuit) in each cone of logic driving a single output are guaranteed to be detected. Examples indicate that LFSRs based on cyclic codes have lower hardware cost and shorter or comparable test lengths than other approaches. These test-pattern generators are well suited to applications where short testing time, low hardware overhead, and 100% single-stuck-at fault coverage are required.>

Two statistical models are developed to estimate the effect of chip failures on cache memory systems. The first one predicts the degradation in the expected Read time taking into account the different failure modes of a memory chip. It is seen that there is a significant degradation in the expected access time after only four weeks of operation even if failed words are deallocated. The second model estimates the degradation in the Miss ratio due to the deallocation of failed sections of cache. Both models can help in setting suitable preventive maintenance schedules as well as in making design decisions.

The process of determining the required test length for a desired level of confidence for pseudorandom testing using a random sampling without replacement model is examined. The differences between random and pseudorandom testing are discussed and developed. The strictly random testing model is shown to be inaccurate for high confidence testing of combinational circuits. A method of calculating the required test length for pseudorandom testing based upon fault detectabilities is described. The result provides a very accurate prediction of required test length applicable to self-test using pseudorandom inputs.

Algorithmic test generation for high fault coverage is an expensive and time-consuming process. As an alternative, circuits can be tested by applying pseudorandom patterns generated by a linear feedback shift register (LFSR). Although no fault simulation is needed, analysis of pseudorandom testing requires the circuit detectability profile.

System failure has many different causes. This presentation identifies and illustrates these causes. An attempt is made to assess their relative importance. Major topics considered are the loss of fault coverage due to imperfect implementation information or because the failure modes are not accurately represented by the single-stuck fault assumption. New temporary failure characterizations derived from laboratory experiments, simulation and system data are also presented.

A new technique for designing easily testable PLA's is presented. The salient features of this technique are: 1) low overhead, 2) high fault coverage, 3) simple design, and 4) little or no impact on normal operation of PLA's. This technique consists of the addition of input lines in such a way that, in test mode, any single product line can be activated and its associated circuitry and device can be tested. Using this technique, all multiple stuck-at faults, as well as all multiple extra and multiple missing device faults, are detected.

This paper presents a design technique for linear feedback shift registers that generate test patterns for pseudoexhaustive testing. This technique is applicable to any combinational network in which none of the outputs depends on all inputs. It does not rewire the original network inputs during in-circuit test pattern generation. Thus, the possibility of undetected faults on some inputs is eliminated.

Two new general designs for totally self-checking (TSC) comparators with an arbitrary number of input vectors are presented. The multipattern comparator combines modified TSC 2-input comparators and a TSC two-rail checker that requires only four patterns for self-testing. The counter-driven comparator adds circuitry to generate an exhaustive set of test patterns. The designs are compared on the basis of input limitations, circuit complexity, and gate delays. It is shown that TSC comparators cannot exist under two sets of conditions associated with 1-bit input vectors and two-level circuit realizations.

It is shown that if a 4-by-n binary matrix has four distinct even-parity rows such that each column has exactly two 0's and two 1's, then there exists a totally self-checking even-parity checker that is tested by the four rows of this matrix. The utility of this result in designing self-testing embedded parity checkers is described.

A new approach to test pattern generation which is particularly suitable for self-test is described. Required computation time is much less than for present day automatic test pattern generation (ATPG) programs. Fault simulation or fault modeling is not required. More patterns may be obtained than from standard ATPG programs. However, fault coverage is much higher—all irredundant multiple as well as single stuck faults are detected. The test patterns are easily generated algorithmically either by program or hardware.

Quantitative measures of self-checking power are defined for evaluation, comparison, and design of self-checking circuits. The self-testing and fault-secure properties have the corresponding quantitative measures testing input fraction (TIF), and secure input fraction (SIF). Averaging these measures over the fault set yields basic figures of merit. These simple averages can conceal faults with low values of TIF or SIF. Improved figures of merit, based on geometric means, are defined to provide greater sensitivity to low TIF or SIF. As a demonstration, self-checking linear feedback shift registers (LFR's) based on duplication and serial parity prediction are evaluated.

A new approach to test pattern generation which is particularly suitable for self-test is described. Required computation time is much less than for present-day automatic test pattern generation (ATPG) programs. Fault simulation is not required. More patterns may be obtained than from standard ATPG programs. However, fault coverage is much higher - all irredundant multiple as well as single stuck faults are detected. Test length is easily controlled. The test patterns are easily generated algorithmically either by program or hardware.

In this correspondence we present a statistical model which relates mean computer failure rates to level of system activity. Our analysis reveals a strong statistical dependency of both hardware and software component failure rates on several common measures of utilization (specifically CPU utilization, I/O initiation, paging, and job-step initiation rates). We establish that this effect is not dominated by a specific component type, but exists across the board in the two systems studied. Our data covers three years of normal operation (including significant upgrades and reconfigurations) for two large Stanford University computer complexes. The complexes, which are composed of IBM mainframe equipment of differing models and vintage, run similar operating systems and provide the same interface and capability to their users. The empirical data comes from identically structured and maintained failure logs at the two sites along with IBM OS/VS2 operating system performance/load records.

A technique for modifying networks so that they are capable of self test is presented. The major innovation is partitioning the network into subnetworks with sufficiently few inputs that exhaustive testing of the subnetworks is possible.

An algebraic system for designing multivalued (four-level) I2L circuits is presented here. It was necessary to develop this system because the use of existing multivalued logic formalisms does not result in efficient I2L circuits. The close relationship between the algebra and the integrated circuits is stressed throughout the paper.

The correspondence between Boolean network probabilities and the design formalisms of Ledley and Aiken is demonstrated.

This paper presents a number of methods for finding sequential circuit output probabilities using regular expressions. Various classes of regular expressions, based on their form, are defined and it is shown how to easily find multistep transition probabilities directly from the regular expressions. A new procedure for finding steady-state probabilities is given which proceeds either from a regular expression or a state diagram description. This procedure is based on the concept of synchronization of the related machine, and is useful for those problems where synchronization sequences exist. In the cases where these techniques can be utilized, substantial savings in computation can be realized. Furthermore, application to other areas such as multinomial Markov processes is immediate.

A family of circuits for multivalued, in particular quaternary, integrated injection logic is described. The basic elements are the I2L current mirror and I2L threshold gates.

In this correspondence two methods are given for calculating the probability that the output of a general combinational network is 1 given the probabilities for each input being 1. We define the notions of the probability of a signal and signal independence. Then several proofs are given to show the relationship between Boolean operations and algebraic operations upon probabilities. As a result of these, two simple algorithms are presented for calculating output probabilities. An example of the usefulness of these results is given with respect to the generation of tests for the purpose of fault detection.

A probabilistic treatment of general combinational networks has been developed. Using the notions of the probability of a signal and signal independence, algorithms have been presented to calculate the probability of the output of a logic circuit being 1. Simplifications to the algorithm result when sets of input probabilities are given the same value, and this process called bundling is described in the paper. Finally, a series of examples illustrate the application of the probabilistic approach to the analysis of faulty logic circuits.

The combination of N-modular redundancy (NMR) and standby sparing has resulted in a promising redundancy technique for protecting those portions of a fault-tolerant system whose continuous real-time operation is essential. This technique, known as hybrid redundancy, uses N + Sp identical modules. N of these are connected to a majority voter to form an NMR core. The remaining Sp are used as standby spares. Disagreement detectors instruct a switch to replace with a standby spare any of the N modules that disagrees with the majority consensus. Since the switch and disagreement detector, as well as the modules, must function properly for the system to perform its designed task, the overall system reliability depends on the disagreement detector, switch, and hybrid reliabilities. Hence the overall reliability is a function of switch reliability. A highly reliable, thus simple, switch is desirable. First, strategies where every spare can be switched into every voter position (totally assigned) are considered. An optimal strategy is developed where the number of states in the switch is the criterion used for optimality. Formulas for the switch state count for the various strategies are derived and the strategies compared. Next, partially assigned switching strategies, strategies where every spare need not be capable of occupying every voter position, are examined. It is shown that designs where all spares are assigned to the same t + 2 of the 2t + 1 voter positions have as good reliability as the more complex totally assigned switching strategy.

A marriage of N-modular redundancy (NMR) and standby sparing has resulted in a promising redundancy technique for protecting those portions of a fault-tolerant system whose continuous real-time operation is essential. This technique, known as hybrid redundancy, consists of N identical modules connected to a majority voter to form an NMR core. Disagreement detectors instruct a switch to replace any of the N modules that disagree with the majority consensus by a standby spare. The switch is essential to the operation of the hybrid redundancy scheme. The system reliability is a product of the reliabilities of the switch and the hybrid redundancy scheme assuming a perfect switch. To realize the demonstrated potential of the latter a highly reliable, thus simple, switch is required. An iterative cell switch is proposed and demonstrated to save at least 25 percent, and more than 80 percent in some instances, of the complexity of a switch design presented elsewhere in the literature. The use of threshold, rather than majority, voters is considered and shown to yield a simpler design in some cases. Three techniques for decreasing the propagation delay through the iterative cell switch are presented as well as a scheme to implement retry of failed modules. Finally, five different switch designs are compared on a cost and complexity basis.

This paper is a study of the effects of faults on the logical operation of combinational (acyclic) logic circuits. In particular, the conditions whereby two different faults can produce the same alteration in the circuit behavior are investigated. This relationship between two faults is shown to be an equivalence relation, and three different types of equivalence relations are specified. Necessary and sufficient conditions for the existence of these equivalence relations are proved. An algorithm for determining the equivalence classes for one of the types of equivalence is presented. Other types of algebraic properties of faults are discussed.

This paper considers the problem of economical assignment of codes to the internal states of sequential circuits. The only restriction placed on these circuits is the fact that they are assumed to be clocked. The internal logic is realized with two-level diode or transistor circuitry, and the methods given here minimize both the number of gates and of gate inputs (diodes) required to realize a given sequential circuit. Methods are first developed for the coding of small fully specified state tables for which only the internal logic is to be minimized. These methods are then successively extended to cover the situations where it is desired to minimize simultaneously both the internal logic and the output logic of a sequential circuit, where the state tables are not fully specified, and where the size of the state tables is arbitrarily large. A method for dealing with the special class of ``counter-like'' state tables is also given. All the procedures presented here are designed to be easily programmable on a digital computer, and several of these methods have been so programmed. Our methods are discussed and compared with other existing procedures.

This paper considers the application of signal flow graph techniques to the problem of characterizing sequential circuits by regular expressions. It is shown that the methods of signal flow graph theory, with the proper interpretation, apply to state diagrams of sequential circuits. The use of these methods leads to a simple algorithm for obtaining a regular expression describing the behavior of a sequential circuit directly from its state diagram.

This paper is primarily concerned with finding, in the most efficient possible way, the set of all solutions to a cyclic prime implicant table. (A solution is a set of rows such that every column contains at least one marked entry in a row belonging to the set and such that no row can be deleted from the set without destroying this property.) Extensive use is made of the relationship between this and the problem of efficiently reducing a Boolean frontal function from the form of a product of sums of single literals to a sum of products. The transformation methods commonly in use today have the disadvantage that they tend to introduce duplicate and redundant products. (A redundant product includes at least one row which can be removed, and the remaining rows will still constitute a solution.) Several methods which appreciably reduce the number of such redundancies are presented. One of these methods (called row branching), applies repeatedly the algebraic transformation f = af(α = 1) + f(μ= 0) where μ is the Boolean variable corresponding to a row of the table, and f is the function corresponding to the given table. The mechanism by which a redundant solution is generated is described. The paper includes other useful transformation procedures such as, for example, a tabular method in which redundancies are avoided systematically at each step.

An important step in the synthesis of sequential switching circuits is the assignment of binary variable states to represent internal states of the circuit. A formula is derived here which indicates the number of different assignments which can be made for flow tables having a given number of rows. There are only three essentially different assignments possible for a four-row table, and there are 140 for a five-row table.

An iterative network is a combinational switching circuit which consists of a series of identical "cells" or sub-networks; for example, the stages of a parallel binary adder. A formal design method for iterative networks is presented. This is similar to the flow table technique for designing sequlential circuits.