Digital Commons Network^™

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 …

An Analysis And Implementation Of Linear Derivation Strategies, Winston M. Tabada

Theses: Doctorates and Masters

This study examines the efficacy of six linear derivation strategies: (i) s-linear resolution, (ii) the ME procedure; (iii) t-linear resolution, (iv) SL -resolution, (v) the GC procedure, and (vi) SLM. The analysis is focused on the different restrictions and operations employed in each derivation strategy. The selection function, restrictive ancestor resolution, compulsory ancestor resolution on literals having atoms which are or become identical, compulsory merging operations, reuse of truncated literals, spreading of FALSE literals, no-tautologies resection, no two non-B-literals having identical atoms restriction, and the use of semantic information to trim irrelevant derivations from the search tree are the major …

The Problem Of Mutual Exclusion: A New Distributed Solution, Rajeev Chawla

Theses and Dissertations

In both centralized and distributed systems, processes cooperate and compete with each other to access the system resources. Some of these resources must be used exclusively. It is then required that only one process access the shared resource at a given time. This is referred to as the problem of mutual exclusion. Several synchronization mechanisms have been proposed to solve this problem. In this thesis, an effort has been made to compile most of the existing mutual exclusion solutions for both shared memory and message-passing based systems. A new distributed algorithm, which uses a dynamic information structure, is presented to …

Implementation Of Object Oriented University Database Using Vodak/Vml-0 Prototype, Abhay V. Bhave

Theses

In recent years object - oriented programming has gained a tremendous popularity in the design and implementation of emerging data - intensive application systems. Object oriented knowledge based approaches have proved to be very powerful vehicle when developing, integrating complex systems.

Using a University database demonstrated here is an object oriented model. This model uses VODAK/VML-0 prototype which was developed by GMD - IPSI, Darmstadt FRG. The Conceptual Schema of this database was done using The Dual Model, but as the current VODAK/VML version does not support dual model, the schema was modified before use. There are 167 classes defined …

Cascading Of Ever Adaptive Variation Of Lzw Algorithm With Arithmetic Coding Method, Ramesh Vishwanatham, Ketan Tejani

Theses

Two known compression algorithms appropriate for communication are LZW and the Arithmetic Coding method. Both algorithms are adaptive and require no extra communication from the encoder to the decoder. We have considered a variation of LZW algorithm known as Online version which result in better compression. Here we present a scheme to cascade Online LZW with Arithmetic algorithms into an Ever Adaptive data compression algorithm which achieves higher compression ratio and is appropriate for communication.

A Tight Upper Bound On The Benefits Of Replication And Consistency Control Protocols, Donald B. Johnson, Larry Raab

Computer Science Technical Reports

We present an upper bound on the performance provided by a protocol guaranteeing mutually exclusive access to a replicated resource in a network subject to component failure and subsequent partitioning. The bound is presented in terms of the performance of a single resource in the same network. The bound is tight and is the first such bound known to us. Since mutual exclusion is one of the requirements for maintaining the consistency of a database object, this bound provides an upper limit on the availability provided by any database consistency control protocol, including those employing dynamic data relocation and replication. …

Three Degrees Of Freedom Compliant Motion Control For Robotic Aircraft Refueling, Clayton M. Andersen

Theses and Dissertations

The Air Force Institute of Technology (AFIT) supports on-going research in application of robotic technology to enhance assembly tasks. As a testbed, AFIT supports the ground-based aerial refueling project, with an emphasis on visual servoing techniques and compliant motion control. This thesis focuses on compliant motion control. Previous research developed the testing environment, which includes a PUMA-560 industrial manipulator, and a half scale mock-up of an aerial refueling system. This effort corrected and expanded the existing two degree of freedom (DOF) compliant controller to three DOF. Three DOF compliance was demonstrated by inserting the refueling nozzle into the receiver port. …

Array Reshaping -- A Mechanism For Optimizing Array Storage On Parallel Architecture, Ko-Yang Wang

Department of Computer Science Technical Reports

No abstract provided.

Heuristic Guided Pre-Optimized Algorithm Substitution For Parallel Computers, Ko-Yang Wang

Department of Computer Science Technical Reports

No abstract provided.

The Duke Internet Programming Contest, Owen Astrachan, Vivek Khera, David Kotz

Dartmouth Scholarship

On the evening of October 23, 1990, electronic mail messages started to pour into the computers at the Duke University Computer Science Department. Teams of programmers from all over the world were registering to compete in the first global (as far as the authors are aware) programming contest to be held on the Internet. During the three hour competition, modeled after the annual ACM scholastic programming contest, 60 teams from 37 institutions in 5 countries attempted to solve a set of six programming problems using C or Pascal. Their solutions were sent by electronic mail to Duke, where their programs …

Models And Algorithms For Co-Scheduling Compute-Intensive Tasks On A Network Of Workstations, Mikhail J. Atallah, Christina Lock, Dan C. Marinescu, Howard J. Seigel, Thomas L. Casavant

Department of Computer Science Technical Reports

No abstract provided.

Voronoi Diagrams In A River, Kokichi Sugihara

Department of Computer Science Technical Reports

No abstract provided.

Brep-Index: A Multi-Dimensional Space Partitioning Tree, George Vanĕček

Department of Computer Science Technical Reports

No abstract provided.

Implementing Expert System Rule Conditions By Neural Networks, Henry Tirri

Department of Computer Science Technical Reports

No abstract provided.

Fitting Semantics For Conditional Term Rewriting, Chilukuri K. Mohan

Electrical Engineering and Computer Science - Technical Reports

This paper investigates the semantics of conditional term rewriting systems with negation which do not satisfy useful properties like termination. It is shown that the approach used by Fitting [5] for Prolog-style logic programs is applicable in this context. A monotone operator is developed, whose fixpoints describe the semantics of conditional rewriting. Several examples illustrate this semantics for non-terminating rewrite systems which could not be easily handled by previous approaches.

Balancing A Pipeline By Folding, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

A pipeline for Householder reduction is folded several times across an array of processors to achieve approximate load balancing. The performance of the folded pipeline is analyzed and measured on a Computing Surface.

The All-Pairs Pipeline, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

An all-pairs problem is a computation on every possible subset consisting of two elements chosen from a set of n elements. N-body simulation and Householder reduction are all-pairs problems. The paper defines the all-pairs problem concisely by means of precedence matrices and derives a parallel algorithm. The algorithm is presented in both coarse-grain and medium-grain form. The all-pairs paradigm is illustrated by a pipeline for Householder reduction of a matrix to triangular form.

Analyzing Images Containing Multiple Sparse Patterns With Neural Networks, Rangachari Anand, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

We have addressed the problem of analyzing images containing multiple sparse overlapped patterns. This problem arises naturally when analyzing the composition of organic macromolecules using data gathered from their NMR spectra. Using a neural network approach, we have obtained excellent results in using NMR data to analyze the presence of amino acids in protein molecules. We have achieved high correct classification percentages (about 87%) for images containing as many as five substantially distorted overlapping patterns.

Real-Time Flight Simulation And The Head-Mounted Display - An Inexpensive Approach To Military Pilot Training, Philip A. Platt

Theses and Dissertations

The integration of the low-cost head-mounted display (HMD), an inexpensive graphics workstation-based flight simulator, and a communications network was investigated to determine if the prototype of an inexpensive multi- aircraft Virtual Flight Simulator could be built. Previous research efforts have coupled HMD technology and flight simulation; however, the cost of these systems has been high. This thesis effort emphasized the use of joystick devices to emulate pilot control, the implementation of a fully enclosed virtual flight simulator, and the utilization of low-cost NTSC-based television technology to produce a prototype. The virtual flight simulator also contained a basic set of instruments …

A Biologically-Inspired Neural Network Architecture For Image Processing, Laurence E. Lazofson

Theses and Dissertations

This thesis project included a literature survey of biological and artificial neural network research followed by development and testing of high- order and image recognition hierarchical neural network algorithms. Following training, performance testing of second-order and third-order networks yielded maximum accuracies comparable to those achieved by multilayer perceptron classifiers operating on test data sets. Several versions of an image classification algorithm were tested for learning performance using pixel data from forward-looking infrared (FLIR) images of tanks, trucks, target boards, and clutter. Employing the biologically-motivated Lambertization and contrast normalization of pixel windows, correlations with multiple Gabor function wavelets, and a 'phase …

A Multi-Scale Approach For Recognizing Complex Annotations In Engineering Documents., Andrew Francis Laine, William Ball, Arun Kumar

All Computer Science and Engineering Research

This paper describes a novel method of character recognition targeted for extracting complex annotations found in engineering documents. The results of this work will make it possible to capture the information contained in documents used to support facilities management and manufacturing. The recognition problem is made difficult in part because characters and text may be expressed in arbitrary fonts and orientations. Our approach includes a novel incremental strategy based on the multi-scale representation of wavelet decompositions. Our approach is motivated by biological mechanisms of the human visual systems. Using wavelets as a set of basis functions, we may decompose an …

Householder Reduction, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

This tutorial discusses Householder reduction of n linear equations to a triangular form which can be solved by back substitution. The main strengths of the method are its numerical stability and suitability for parallel computing. We explain how Householder reduction can be derived from elementary matrix algebra. The method is illustrated by a numerical example and a Pascal algorithm. We assume that the reader has a general knowledge of vector and matrix algebra but is less familiar with linear transformation of a vector space.

Automatic Determination Of Recommended Test Combinations For Ada Compilers, James S. Marr

Theses and Dissertations

Ada compilers are validated using the Ada Compiler Validation Capability (ACVC) test suit, containing over 4000 individual test programs. Each test program focuses, to the extent possible, on a single language feature. Despite the advantages of this atomic testing methodology, it is often the unexpected interactions between language features that result in compilation problems. This research investigated techniques to automatically identify recommended combinations of Ada language features for compiler testing. A prototype program was developed to analyze the Ada language grammar specification and generate a list of recommended of features to be tested. The output from this program will be …

Computer Generated Holography As A Three-Dimensional Display Medium, Bryant L. Stuart

Theses and Dissertations

A process was developed to produce three dimensional images using computer generated holography (CGH). This process consisted of a series of steps that began with a geometric description of an object and concluded with a three dimensional holographic image being computed from a synthetic wavefront. The objects used in this series of steps (or CGH pipeline) were described geometrically as a collection of three dimensional points. The modular nature of the CGH pipeline provided a flexible platform from which to evaluate various object geometries, interference calculations algorithms, and interference pattern recording and reduction techniques. This system was implemented with general …

An Empirical Study Of Combining Communicating Processes In A Parallel Discrete Event Simulation, Ann K. Lee

Theses and Dissertations

The primary goal of distributed discrete event simulations is to achieve speedup in simulation execution time by distributing the processing of the simulation over multiple processors. When partitioned for distribution in this fashion, simulations are typically partitioned such that there are more processes than processors. This thesis reviews existing methods for distributed discrete event simulations, and proposes general guidelines for efficient partitioning for a given communications topology based on empirical evidence. A performance analysis is conducted for two approaches to partitioning the system. The first method chosen is a mapping of multiple processes to a processor and the second approach …

Use Of Grasp Force Focus Positioning To Enhance The Torque Resistance Capability Of Robotic Grasps, Stephen G. Edwards

Theses and Dissertations

Three-point-contact grasps are unique in that the homogeneous solution for the contact forces always produces a grasp force focus. Careful positioning of this focus point in the grasp plane can help avoid two things; slipping at the contact points, and violation of joint torque limits. The focus placement method is explored theoretically by examining two types of grasps on cylinders; 1) fingertip grasps using three independently operated fingers, and 2) single-finger power grasps with one contact point on each of three links. Constraint maps are generated for various fingertip grasps in order to show how proper placement of the grasp …

Computer Model Of An Injection Locked Pulsed Co2 Laser, Allen M. Susie

Theses and Dissertations

With the discovery of the laser there have been continual attempts to increase the 'spectral brightness' of a laser for applications such as signal processing and lidar. To this end techniques using either passive or active cavity elements have been developed to isolate a single longitudinal mode in both continuous and pulsed laser systems. Although passive elements have useful applications in continuous systems their use in pulsed systems is difficult to control. The injection of an external signal has proved very successful.

Problems To Test Parallel And Vector Languages -- Ii, John R. Rice, Jin Jing

Department of Computer Science Technical Reports

No abstract provided.

Model-Based 3-D Recognition System Using Gabor Features And Neural Networks, Phung D. Le

Theses and Dissertations

A different approach to pattern recognition was attempted using Gabor features, artificial neural nets, and an image generator. The Gabor features and artificial neural nets are sound biological-based, and the image generator provides complete access to any view of an object. This thesis tested the idea that their integration could form a robust 3-D recognition system. The results of the research showed that the Gabor features together with a neural net were used successfully in classifying objects regardless of their positions, out-of- plane rotations, and to a lesser extent in-plane rotations. The Gabor features were obtained by correlating the image …