Computer Sciences Commons^™

Design For Testability And Test Generation With Two Clocks, Vishwani D. Agrawal, Sharad C. Seth, Jitender S. Deogun

School of Computing: Conference and Workshop Papers

We propose a novel design for testability method that enhances the controllability of storage elements by use of additional clock lines Our scheme is applicable to synchronous circuits but is otherwise transparent to the designer. The associated area and speed penalties are minimal compared to scan based methods, however, a sequential ATPG system is necessary for test generation. The basic idea Is to use independent clock lines to control disjoint groups of flip-flops. No cyclic path are permitted among the flip-flops of the same group. During testing, a selected group can be made to hold its state by disabling its …

Estimating The Quality Of Manufactured Digital Sequential Circuits, Dharam Vir Das, Sharad C. Seth, Vishwani Agrawal

School of Computing: Faculty Publications

Detection of a fault in a sequential circuit requires a sequence of test vectors. This sequence activates the fault and propagates the effect of the fault to a primary output. To accomplish this, the test sequence must set flip-flops through a series of states. Unlike a combinational circuit, many faults in a sequential circuit cannot be detected by a single vector. We propose a statistical model in which. a fault is characterized by two parameters: a pervector detection probability and an integer-valued latency. Irrespective of its detection probability, the fault cannot be detected by a vector sequence shorter than the …

Design Of A Dynamically Reconfigurable, Integrated, Parallel Vision System, Ashok K. Samal

School of Computing: Conference and Workshop Papers

Multiprocessors can be used to speed up the process of object recognition. Building a parallel vision system is a two step process: (a) design and implement parallel algorithms for individual operations, and (b) integrate them into a coherent system. So far the emphasis has been on the first step. The second step has not received enough attention. A framework for building a parallel vision system is presented here. The necessary and desirable features of such a system have been identified. An initial design which incorporates these features is also given.

A Statistical Theory Of Digital Circuit Testability, Sharad C. Seth, Vishwani D. Agrawal, Hassan Farhat

School of Computing: Faculty Publications

When test vectors are applied to a circuit, the fault coverage increases. The rate of increase, however, could be circuit dependent. A relation between the average fault coverage and circuit testability is developed in this paper. The statistical formulation allows computation of coverage for deterministic and random vectors. We discuss the following applications of this analysis: determination of circuit testability from fault simulation, coverage prediction from testability analysis, prediction of test length, and test generation by fault sampling.

High-Level Microprogramming: An Optimising C Compiler For A Processing Element Of A Cad Accelerator, Paul Kenyon, Prathima Agrawal, Sharad C. Seth

School of Computing: Faculty Publications

The development of a high-level language compiler for a micro-programmable processing element (PE) in the MARS multicomputer is described. MARS, an MIMD message passing machine, was designed to speed up VLSI CAD and similar other non-numerical applications. The need for sup port of a high-level language at the PE level of a multicomputer is considered, and the choice of C as an appropriate programming language is justified. Special features found in VLSI processors are examined along with compiler support for them.

Conventional re-targetable compiler techniques are shown to be inadequate for the highly concurrent micro-programmable PE. These techniques must be …

An Experimental Study On Reject Ratio Prediction For Vlsl Circuits: Kokomo Revisited, Dharam Vir Das, Sharad C. Seth, Paul T. Wagner, John Anderson, Vishwani Agrawal

School of Computing: Faculty Publications

Assuring product quality is becoming increasingly more important for the semiconductor chip manufacturers. The reject ratio (defect level) provides a simple and accurate measure of a product's quality. However, measuring the reject ratio of tested chips is often not feasible or accurate. Statistical techniques for reject ratio prediction provide a possible way out of this dilemma. In this paper, we report on an experiment to verify the accuracy of reject ratio predictions by the available approaches. The data collection effort includes instrumenting the wafer probe test to obtain chip failures as a function of applied vectors and running a fault …

Signal Probabilities In And-Or Trees, Lester Lipsky, Sharad C. Seth

School of Computing: Faculty Publications

In this paper, we consider a class of AND-OR tree circuits and study their response to random-pattern inputs as the depth of the tree is allowed to increase indefinitely. Each binary input of a circuit is independently chosen to be one (zero) with probability x (1 - x). The logic of the circuit determines the probability of success (one) at the output as a monotonically increasing S-shaped function of x called the probability transfer function. The probability transfer function of an AND-OR tree is shown to have just one interior fixed point (w.r.t. changes in depth of …

Design Of Parity Testable Combinational Circuits, Bhargab B. Bhattacharya, Sharad C. Seth

School of Computing: Faculty Publications

The parity testability of a single output is related to its partition in terms of maximal supergates and then a scheme is proposed for making an untestable circuit parity testable by augmenting its maximal supergates. Only a small amount of extra logic and a single external test-mode pin is required to complete the design. The test procedure is simple and the hardware overhead is low.

A Theory Of Testability With Application To Fault Coverage Analysis, Sharad C. Seth, Vishwani Agrawal, Hassan Farhat

School of Computing: Faculty Publications

When test vectors are applied to a circuit, the fault coverage increases. The rate of increase, however, could be circuit-dependent. In fact, the actual rise of fault coverage depends on the characteristics of vectors, as well as, on the circuit. The paper shows that the average fault coverage can be computed from circuit testability. A relationship between fault coverage and circuit testability is derived. The mathematical formulation allows computation of coverage for deterministic and random vectors. Applications of this analysis include: determination of circuit testability from fault simulation, coverage prediction from testability analysis, prediction of test length, and test generation …

Testability Analysis Of Synchronous Sequential Circuits Based On Structural Data, Raghu V. Hudli, Sharad C. Seth

School of Computing: Faculty Publications

Bounds on test sequence length can be used as a testability measure. We give a procedure to compute the upper bound on test sequence length for an arbitrary sequential circuit. We prove that the bound is exact for a certain class of circuits. Three design rules are specified to yield circuits with lower test sequence bounds.

Parallel Split-Level Relaxation, Thomas C. Henderson, Ashok K. Samal

School of Computing: Conference and Workshop Papers

The goal of the scene labeling problem is to identify a set of regions in a given image. There are several approaches to solve this problem, including backtracking, graph matching, etc. A new method called split-level relaxation based on discrete relaxation was proposed in. It takes care of multiple semantic constraints, by considering each of them independently. The problem is NP-complete, so it takes a long time to solve this problem. With the advent of multiprocessors, it is now imperative to see if the problem can be solved faster in the average case.

We give a framework for solving the …

Test Generation By Fault Sampling, Vishwani Agrawal, Hassan Farhat, Sharad C. Seth

School of Computing: Conference and Workshop Papers

This paper presents a novel technique of generating tests from a random sample of faults. The entire fault population of the circuit is randomly divided into two groups. Only one group, usually the smaller one, is used for test generation by the test-generator and fault-simulator programs. This group is known as the sample and its coverage is deterministic. The coverage of faults in the remaining group is similar to that of random vectors and is estimated from the distribution of fault detection probabilities in the circuit. As the sample size increases, the fraction of unsampled faults reduces. At the same …

A Fast Fault Simulation Algorithm For Combinational Circuits, Wuudiann Ke, Sharad C. Seth, Bhargab B. Bhattacharya

School of Computing: Conference and Workshop Papers

The performance of a fast fault simulation algorithm for combinational circuits, such as the critical path tracing method, is determined primarily by the efficiency with which it can deduce the detectability of stem faults (stem analysis). We propose a graph based approach to perform stem analysis. A dynamic data structure, called the criticality constraint graph, is used during the backward pass to carry information related to self masking and multiple-path sensitization of stem faults. The structure is updated in such a way that when stems are reached their criticality can be found by looking at the criticality constraints on their …

What Is The Path To Fast Fault Simulation?, Miron Abramovici, Balaji Krishnamurthy, Rob Mathews, Bill Rogers, Michael Schulz, Sharad C. Seth, John Waicukauski

School of Computing: Faculty Publications

Motivated by the recent advances in fast fault simulation techniques for large combinational circuits, a panel discussion has been organized for the 1988 International Test Conference. This paper is a collective account of the position statements offered by the panelists.

The Computer As A Collection Management Tool, Suzanne B. Mclaren, Hugh H. Genoways, Duane A. Schlitter

University of Nebraska State Museum: Mammalogy Papers

Since the mid-1960s, discussion of computer use for information retrieval in museum collections has usually focused on research potential. Much attention has been given to the idea of networking and the ability to access data across great distances. However, the potential for collection management usage has also proven to be a legitimate rationale for computerization. Numerous aspects of collection management are discussed for which the computer may be employed. Topics include creating cross-reference files, updating taxonomic and geographic information, pinpointing mismatched specimens, locating lost and uncataloged material, controlling loan procedures, producing accession files for insurance purposes, curating all or part …

Decoding Substitution Ciphers By Means Of Word Matching With Application To Ocr, George Nagy, Sharad C. Seth, Kent Einspahr

School of Computing: Faculty Publications

A substitution cipher consists of a block of natural language text where each letter of the alphabet has been replaced by a distinct symbol. As a problem in cryptography, the substitution cipher is of limited interest, but it has an important application in optical character recognition. Recent advances render it quite feasible to scan documents with a fairly complex layout and to classify (cluster) the printed characters into distinct groups according to their shape. However, given the immense variety of type styles and forms in current use, it is not possible to assign alphabetical identities to characters of arbitrary size …

An Exact Analysis For Efficient Computation Of Random-Pattern Testability In Combinational Circuits, Sharad C. Seth, Bhargab B. Bhattacharya, Vishwani Agrawal

School of Computing: Conference and Workshop Papers

Experimental evidence shows that low testability in a typical circuit is much more likely due to poor observability than poor controllability. Thus, from theoretical and practical standpoints, it is important to develop an accurate model for observability computation. One such model, in terms of supergates, is proposed in the first part of this paper thus complimenting our earlier work. It is now possible to obtain exact random-pattern testability for each line in a circuit.

The second part of the paper analyzes the supegate structure of a circuit from a graph theoretic viewpoint. Finding a supergate is related to determining the …

An Analysis Of The Use Of Rademacher-Walsh Spectrum In Compact Testing, Ten-Chuan Hsiao, Sharad C. Seth

School of Computing: Faculty Publications

Earlier approaches to random compact testing use a random pattern generator which depends on the combinational function under test and a circuit signature which remains the same independent of the circuit. In this correspondence we analyze the performance of a new scheme in which the pattern generator is simple and independent of the function being tested but the circuit signature is chosen to be a coefficient from the Rademacher-Walsh (RW) spectrum of the function under test. The analysis provides guidelines for choosing an RW coefficient, a test length, and an error tolerance so as to minimize the probabilities of rejecting …

Characterizing The Lsi Yield Equation From Wafer Test Data, Sharad C. Seth, Vishwani D. Agrawal

School of Computing: Faculty Publications

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

Hierarchical Representation Of Optically Scanned Documents, George Nagy, Sharad C. Seth

School of Computing: Conference and Workshop Papers

The objective of the research to be pursued is to develop a schema for representing raster-digitized (scanned) documents, The representation is to retain not only the spatial structure of a printed document, but should also facilitate automatic labeling of various components, such as text, figures, subtitles, and figure captions, and allow the extraction of important relationships (such as reading order) among them. Intended applications include (1) data compression for document transmission and archival, and (2) document entry, with out rekeying, into editing, formatting, and information retrieval systems.

Candide's Practical Principles Of Experimental Pattern Recognition, George Nagy

School of Computing: Faculty Publications

This correspondence calls attention to several frequently used assumptions and techniques culled from the pattern recognition literature.

A Simplified Method To Calculate Failure Times In Fault-Tolerant Systems, Sharad C. Seth, Lester Lipsky

School of Computing: Faculty Publications

A simplified method is presented to calculate moments of failure time and residual lifetime of a fault-tolerant system. The method is based on recent results in queueing theory. Its effectiveness is illustrated by considering a dual repairable system from the literature.

Fault Coverage Requirement In Production Testing Of Lsi Circuits, Vishwani D. Agrawal, Sharad C. Seth, Prathima Agrawal

School of Computing: Faculty Publications

A technique is described for evaluating the effectiveness of production tests for large scale integrated (LSI) circuit chips. It is based on a model for the distribution of faults on a chip. The model requires two parameters, the average number (n₀) of faults on a faulty chip and the yield (y) of good chips. It is assumed that the yield either is known or can be calculated from the available formulas. The other parameter, n₀, is determined from an experimental procedure. Once the model is fully characterized, it allows calculation of the field …

Forecasting Reject Rate Of Tested Lsi Chips, Sharad C. Seth, Vishwani D. Agrawal

School of Computing: Faculty Publications

The reject rate of LSI chips due to incomplete fault coverage of the tests is the fraction of faulty chips, among the chips that pass the tests. This reject rate, which is a measure of the tested chip quality, contributes to the field returns. It is, however, difficult to determine the tested chip quality from the field return data which may also include rejects due to handling damages, infant mortality, etc. Also, a large number of chips must be in use in the field before an adequate amount of field return data can be obtained. This paper gives a method …

A Graph Model For Pattern-Sensitive Faults In Random Access Memories, Sharad C. Seth, K. Narayanaswamy

School of Computing: Faculty Publications

This correspondence generalizes Hayes' recent ideas for generating an optimal transition write sequence which forms the "backbone" of his algorithm for testing semiconductor RAM'S for pattern-sensitive faults. The generalization, presented in graph theoretic terms, involves two sequential steps. The first step results in assigning of a "color" to each memory cell. In the second step, each color is defined as a distinct sequence of bits representing the sequence of states assumed by the correspondingly colored cell. The constraints imposed at each step lead to interesting and general problems in graph theory: the standard graph coloring problem in the first step, …

Lsi Product Quality And Fault Coverage, Vishwani D. Agrawal, Sharad C. Seth, Prathima Agrawal

School of Computing: Conference and Workshop Papers

At present, the relationship between fault coverage of LSl circuit tests and the tested product quality is not satisfactorily understood. Reported work on integrated circuits predicts, for an acceptable field reject rate, a fault coverage that is too high (99 percent or higher). This fault coverage is difficult to achieve for LSl circuits. This paper proposes a model of fault distribution for a chip. The number of faults on a defective chip is assumed to have a Poisson density for which the average value is determined through experiment on actual chips. The procedure, which relates the model to the chip …

On Combinational Networks With Restricted Fan-Out, K. L. Kodandapani, Sharad C. Seth

School of Computing: Faculty Publications

Fan-out-free networks of AND, OR, NOT, EXOR, and MAJORITY gates are considered. Boolean functions for which such networks exist are defined to be fan-out free. The paper solves the following problems regarding the fan-out-free networks and functions.
1) Characterization of the class of fan-out-free functions: The characterization given is constructive in the sense that if a given function is fan-out free one obtains a fan-out-free network to realize it.
2) Counting the class of fan-out-free functions: After establishing a correspondence between a fan-out-free function and a normalized network realizing it, a series of formulas are developed to count distinct normal …

Diagnosis Of Faults In Linear Tree Networks, Sharad C. Seth, K. L. Kodandapani

School of Computing: Faculty Publications

The problem of fault detection and location in tree networks of two input EXCLUSIVE-OR (EOR) gates is considered. The fault model assumes that an EOR gate can change to any other function of its two inputs except the equivalence function. An efficient procedure for single fault location is presented. In the worst case the number of tests necessary to locate single faults is bounded by a linear function of the number of input variables. Constructive upper bounds are obtained for the number of tests to detect multiple faults. Optimality of these bounds is argued and extension of results to other …

Digital Video Display System Using Cathode-Ray Tube, George M. Low, Arthur I. Zygielbaum, Warren L. Martin, Alexander Engel

School of Natural Resources: Faculty Publications

A digital video display system (DWDS) is disclosed for display of image, alphanumeric and other data on a cathode-ray tube (CRT) with sequential raster scan and two, four or eight gray shades. The DVDS includes a central processing unit for ac tivating the system, selecting the X (horizontal axis) and Z (in tensity modulation) modes, and designating the starting loca tion of two successive rasters of data from a memory accessed by a data multiplexer subsystem (DMS). At the end of each raster, the DMS interrupts the computer for a new starting lo cation of a raster of data to …