Electrical and Computer Engineering Commons^™

Dynamic Task Scheduling For The Atamm Multicomputer Operating System Using Embedded Firmware On Microcontrollers, Sudhir Sastry

Electrical & Computer Engineering Theses & Dissertations

A dynamic task scheduling strategy for the distributed processing of large grain dataflow algorithms using embedded firmware on an ATAMM testbed consisting of interconnected microcontrollers is presented in this thesis. The ODU/NASA developed Algorithm to Architecture Mapping Model, ATAMM, uses marked graph models to specify data and control flow for the execution of iterative, deterministic large grain dataflow algorithms in a multicomputing environment. The testbed consists of a bank of four 68HC11 microcontrollers that communicate over a token bus. The token bus arbitration scheme used is contention free and well suited for real-time computing applications. The execution of data flow …

Clustering Techniques In Speaker Recognition, Douglas N. Prescott

Theses and Dissertations

This thesis presents a comparison based on identification rate, of three clustering techniques applied to cepstral features for speaker identification. LBG vector quantization as developed by Linde, Buzo and Gray; is used to provide benchmark performance for comparison with Fuzzy clustering (based on the unsupervised fuzzy partition-optimal number of classes, UFP-ONC algorithm by Gath and Geva) and an Artificial Neural Network, the Multilayer Perceptron. Cepstral features from the TIMIT, King and AFIT93 corpus speaker databases are used to produce speaker-identification classifiers using each of the clustering algorithms. The experiment reported evaluates the speaker identification performance using the 20-dimensional cepstral features …

Scheduling Of Unstructured Communication On The Intel Ipsc/860, Jhy-Chun Wang, Sanjay Ranka

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

In this paper we present several algorithms for decomposing all-to-many personalized communication into a set of disjoint partial permutations. These partial permutations avoid node contention as well as link contention. We discuss the theoretical complexity of these algorithms and study their effectiveness both from the view of static scheduling and from runtime scheduling. Experimental results for our algorithms are presented on the iPSC/860.

Neural Network Diagnosis Of Malignant Melanoma From Color Images, Fikret Erçal, Hsi-Chieh Lee, William V. Stoecker, Randy Hays Moss, Anurag Chawla

Computer Science Faculty Research & Creative Works

Malignant melanoma is the deadliest form of all skin cancers. Approximately 32,000 new cases of malignant melanoma were diagnosed in 1991 in the United States, with approximately 80% of patients expected to survive 5 years. Fortunately, if detected early, even malignant melanoma may be treated successfully, Thus, in recent years, there has been rising interest in the automated detection and diagnosis of skin cancer, particularly malignant melanoma. Here, the authors present a novel neural network approach for the automated separation of melanoma from 3 benign categories of tumors which exhibit melanoma-like characteristics. The approach uses discriminant features, based on tumor …

Investigation Into Model-Based Fuzzy Logic Control, Michael W. Logan

Theses and Dissertations

This thesis investigates the feasibility of a proposed hybrid linear/Fuzzy controller for nonlinear plants. The proposed controller concept is based on the use of multiple linearizations of a nonlinear plant, which describe the dynamics of perturbations about equilibrium points throughout the desired envelope of operation. A bank of linear compensators is developed, each corresponding to a linearized plant about a different equilibrium. The multiple control signals generated by the bank of compensators are then weighted and summed using Fuzzy Logic to produce a composite control perturbation signal, which is used to drive the nonlinear plant. Experiments were conducted to test …

Filtering, Coding, And Compression With Malvar Wavelets, Stephen R. Hall

Theses and Dissertations

This thesis develops and evaluates a number of new concepts and tools for the analysis of signals using Malvar wavelets lapped orthogonal transforms . Windowing, often employed as a spectral estimation technique, can result in irreparable distortions in the transformed signal. By utilizing the Malvar wavelet, any signal distortion resulting from the transformation can be eliminated or cancelled during reconstruction. This is accomplished by placing conditions on the window and the basis function and then incorporating the window into the orthonormal representation. Paradigms for both a complex-valued and a real-valued Malvar wavelet are summarized. I-lie algorithms for the wavelets were …

Parallel Algorithms For Single-Layer Channel Routing, Ronald I. Greenberg, Shih-Chuan Hung, Jau-Der Shih

Computer Science: Faculty Publications and Other Works

We provide efficient parallel algorithms for the minimum separation, offset range, and optimal offset problems for single-layer channel routing. We consider all the variations of these problems that have linear-time sequential solutions rather than limiting attention to the ``river-routing'' context, where single-sided connections are disallowed. For the minimum separation problem, we obtain O(lgN) time on a CREW PRAM or O(lgN/lglgN) time on a CRCW PRAM, both with optimal work (processor-time product) of O(N), where N is the number of terminals. For the offset range problem, we obtain the same time and processor bounds as long as only one side of …

Developing A Graphical User Interface To Support A Real-Time Digital Signal Processing System, Jeffrey C. Miller

Theses and Dissertations

A graphical software user interface for a VMEbus-based real-time digital signal processing system was designed. Use, requirements were defined and the Rumbaugh object-oriented analysis and design technique was applied to analyze the requirements and produce an object-oriented design. The software design includes a graphical, mouse- and keyboard driven user interface, specialized hardware driver modules, and operating system interfaces. An implementation plan was also developed to map the design into the C programming language using existing system code, automatically generated code, and newly written code. Based on the implementation plan, a limited software system prototype w successfully developed and demonstrated. The …

Feasible Offset And Optimal Offset For Single-Layer Channel Routing, Ronald I. Greenberg, Jau-Der Shih

Computer Science: Faculty Publications and Other Works

The paper provides an efficient method to find all feasible offsets for a given separation in a VLSI channel routing problem in one layer. The prior literature considers this task only for problems with no single-sided nets. When single-sided nets are included, the worst-case solution time increases from Theta(n) to Omega(n^2), where n is the number of nets. But, if the number of columns c is O(n), one can solve the problem in time O(n^{1.5}lg n ), which improves upon a `naive' O(cn) approach. As a corollary of this result, the same time bound suffices to find the optimal offset …

Middle Terminal Cell Models For Efficient Over-The-Cell Routing, Siddharth Bhingarde

Masters Theses

In this thesis, we introduce a new class of cell models called Middle Terminal Models (MTM) which combines the advantages of existing cell models: BTM and CTM. This class contains the models 2MTM, 3MTM-V, and 3MTM+V depending on the number of metal layers and the permissibility of vias in over-the-cell areas. In MTM, two rows of terminals are located in the middle of the cell. This partitions over-the-cell area into three regions and allows allocation of more nets to over-the-cell area in congested channels. We prove that when vias are allowed over-the-cell, in "almost all" cases the MTM based layouts …

A Performance Prediction Model For A Fault-Tolerant Computer During Recovery And Restoration, Rodrigo A. Obando

Electrical & Computer Engineering Theses & Dissertations

The modeling and design of a fault-tolerant multiprocessor system is addressed in this dissertation. In particular, the behavior of the system during recovery and restoration after a fault has occurred is investigated. Given that a multicomputer system is designed using the Algorithm to Architecture To Mapping Model (ATAMM) model, and that a fault (death of a computing resource) occurs during its normal steady-state operation, a model is presented as a viable research tool for predicting the performance bounds of the system during its recovery and restoration phases. Furthermore, the bounds of the performance behavior of the system during this transient …

Recognition Of Quadric Surfaces From Range Data: An Analytical Approach, Ivan X. D. D'Cunha

Electrical & Computer Engineering Theses & Dissertations

In this dissertation, a new technique based on analytic geometry for the recognition and description of three-dimensional quadric surfaces from range images is presented. Beginning with the explicit representation of quadrics, a set of ten coefficients are determined for various three-dimensional surfaces. For each quadric surface, a unique set of two-dimensional curves which serve as a feature set is obtained from the various angles at which the object is intersected with a plane. Based on a discriminant method, each of the curves is classified as a parabola, circle, ellipse, hyperbola, or a line. Each quadric surface is shown to be …

A Systolic Simulation And Transformation System, Ronald I. Greenberg, H.-C. Oh

Computer Science: Faculty Publications and Other Works

This paper presents a CAD tool, SystSim, to ease the design of systolic systems. Given a high-level, functional description of processors, and a high-level description of their interconnection, SystSim will perform simulations and provide graphical output. SystSim will also perform transformations such as retiming, which eases use of the methodology of Leiserson and Saxe of designing a system with broadcasting and then obtaining a systolic system through retiming.

Minimizing Channel Density With Movable Terminals, Ronald I. Greenberg, Jau-Der Shih

Computer Science: Faculty Publications and Other Works

We give algorithms to minimize density for channels with terminals that are movable subject to certain constraints. The main cases considered are channels with linear order constraints, channels with linear order constraints and separation constraints, channels with movable modules containing fixed terminals, and channels with movable modules and terminals. In each case, previous results for running time and space are improved by a factor of L/lg n and L , respectively, where L is the channel length and n is the number of terminals.

Detection Of Skin Tumor Boundaries In Color Images, Fikret Erçal, M. Moganti, William V. Stoecker, Randy Hays Moss

Computer Science Faculty Research & Creative Works

A simple and yet effective method for finding the borders of tumors is presented as an initial step towards the diagnosis of skin tumors from their color images. The method makes use of an adaptive color metric from the red, green, and blue planes that contains information for discriminating the tumor from the background. Using this suitable coordinate transformation, the image is segmented. The tumor portion is then extracted from the segmented image and borders are drawn. Experimental results that verify the effectiveness of this approach are given

Design And Implementation Of Fuzzy Logic Controllers. Thesis Final Report, 27 July 1992 - 1 January 1993, Osama A. Abihana, Oscar R. Gonzalez

Electrical & Computer Engineering Faculty Publications

The main objectives of our research are to present a self-contained overview of fuzzy sets and fuzzy logic, develop a methodology for control system design using fuzzy logic controllers, and to design and implement a fuzzy logic controller for a real system. We first present the fundamental concepts of fuzzy sets and fuzzy logic. Fuzzy sets and basic fuzzy operations are defined. In addition, for control systems, it is important to understand the concepts of linguistic values, term sets, fuzzy rule base, inference methods, and defuzzification methods. Second, we introduce a four-step fuzzy logic control system design procedure. The design …

Real Image Visual Display System, James R. Brandt

Theses and Dissertations

This thesis investigates a technique for improving the perception of three-dimensionality in images generated by a Silicon Graphics workstation. The technique involves using a spherical mirror into which the graphics from the CRT are projected. A real image of the graphic is formed by the mirror and it appears to be floating at the image plane. The three-dimensional effect is improved by adding reflections or shadows of the displayed object. Additionally, a method of using real objects with computer generated shadows and computer generated objects with real shadows is investigated. This is done in an effort to quantify how far …

Etann Hardware Implementation For Radar Emitter Identification, James B. Calvin Jr.

Theses and Dissertations

This study investigated classification of 30 radar emitters with 16 signal features using Intel's 80170NX chip, the Electronically Trainable Analog Neural Network (ETANN). Software tools were developed to characterize the ETANN sigmoidal transfer function for use in a custom simulator, known as Neural Graphics. Neural Graphics operates on a Silicon Graphics workstation. The Intel Neural Network Training System simulators were used in early experiments, but were found to be inefficient in training on data used in this research. Using a modified Neural Graphics simulator, single chip and multi-chip experiments were performed to provide benchmark results prior to performing chip-in-loop training. …

Face Recognition With Neural Networks, Dennis L. Krepp

Theses and Dissertations

This study investigated neural networks for face verification and classification. The research concentrated on developing a neural network based feature extractor and/or classifier to perform authorized user verification in a realistic work environment. Recognition accuracy, system assumptions, training time, and execution time were analyzed to determine the feasibility of a neural network approach. Data was collected using a camcorder and two segmentation schemes: manual segmentation and motion-based, automatic segmentation. Data consisted of over 2000. 32x32 pixel, 8 bit gray scale images of 52 subjects; each subject had two to ten days worth of images collected. Several training and test sets …

On The Difficulty Of Manhattan Channel Routing, Ronald I. Greenberg, Joseph Jaja, Sridhar Krishnamurthy

Computer Science: Faculty Publications and Other Works

We show that channel routing in the Manhattan model remains difficult even when all nets are single-sided. Given a set of n single-sided nets, we consider the problem of determining the minimum number of tracks required to obtain a dogleg-free routing. In addition to showing that the decision version of the problem isNP-complete, we show that there are problems requiring at least d+Omega(sqrt(n)) tracks, where d is the density. This existential lower bound does not follow from any of the known lower bounds in the literature.

Version And Transaction Management In Osmagic: An Object-Oriented Database Implementation Of The Magic Vlsi Layout Design Tool, Gary M. Lightner

Theses and Dissertations

The goal of this thesis was to study the feasibility of using an object-oriented database management system to provide the functionality and performance needed to support a complex computer-aided design tool. We do this by modifying OSMagic, a prototype system of the Magic very large scale integrated (VLSI) circuit design tool implemented on the ObjectStore object- oriented database management system. OSMagic was changed to support three different interfaces to ObjectStore and to work in a networking environment. We then designed and examined the use of version and transaction management models as a means of addressing the weaknesses of the prototype …

A Generic Template Extractor (Gentex) In C For Vlsi Design Verification, Kenneth J. Mcclellan Jr.

Theses and Dissertations

The problem of VLSI design verification through circuit extraction was analyzed. The problems of creating a simple template format, the permutability of pins, maintaining connectivity, and performance were focused on. A generic template extractor (GENTEX) was developed in the C programming language for use as a testbed to find solutions to these problems. Six different extraction algorithms were tested with GENTEX and compared based on performance. EDIF translation programs were used to interface with GENTEX on both the input and output sides. One translation program converted an EDIF representation of a schematic into the template format used by GENTEX. The …

Detection Of Spoofing, Jamming, Or Failure Of A Global Positioning System (Gps), Juan R. Vasquez

Theses and Dissertations

The Air Force has equipped its aircraft with avionic systems such as Global Positioning System (GPS) and Inertial Guidance Systems (INS) capable of providing accurate navigation solutions. The aircrews flying these aircraft require a system that can either survive the hostile environments encountered in combat or notify the aircrew that their performance has been significantly degraded. This research focuses on failure detection and isolation techniques using an extended Kalman filter and generalized likelihood ratios using matched filters. Analysis is conducted using a Kalman filter development package known as the Multimode Simulation for Optimal Filter Evaluation (MSOFE). Both a large order …

Design Of An Artificial Neural Network Based Tactile Sensor For The Utah/Mit Dexterous Hand, Jeffery D. Nering

Theses and Dissertations

The Neural Tactile Sensor (NTS) is a high resolution, easily manufactured tactile sensor consisting of electrodes, a thin resistive 'skin', and pattern recognition circuitry that is capable of resolving dynamic and static contact location, force, and slip throughout the continuum of the sensor's active region. The sensor operates by means of a resistive 'skin' harboring the electric field generated when a current is injected into it, and a plurality of electrodes for taking measurements of said electric field. When current flows through the resistive medium from the location of tactile contact, an electric field within the resistive medium is established, …

Autonomous Face Segmentation, Kevin P. Gay

Theses and Dissertations

The purpose of this study was to implement an autonomous face segmentor as the front end to a face recognition system on a Sun SPARCStation2. Face recognition performance criteria, specifically, the capabilities to isolate and resize faces in an image to a consistent scale, were analyzed to determine current practical limitations. Face images were acquired using a S-VHS camcorder. Segmentation was accomplished using motion detection and predefined rules. Tests were run to determine the suitable of the autonomous segmentor as the front-end to a face recognition system. The segmentation system developed consistently located faces and rescaled those faces to a …

Minimum Separation For Single-Layer Channel Routing, Ronald I. Greenberg, F. Miller Maley

Computer Science: Faculty Publications and Other Works

We present a linear-time algorithm for determining the minimum height of a single-layer routing channel. The algorithm handles single-sided connections and multiterminal nets. It yields a simple routability test for single-layer switchboxes, correcting an error in the literature.

Text-Independent Automatic Speaker Identification Using Partitioned Neural Networks, Laszlo Rudasi

Electrical & Computer Engineering Theses & Dissertations

This dissertation introduces a binary partitioned approach to statistical pattern classification which is applied to talker identification using neural networks. In recent years artificial neural networks have been shown to work exceptionally well for small but difficult pattern classification tasks. However, their application to large tasks (i.e., having more than ten to 20 categories) is limited by a dramatic increase in required training time. The time required to train a single network to perform N-way classification is nearly proportional to the exponential of N. In contrast, the binary partitioned approach requires training times on the order of N². …

On Planar Routing Of Multi-Terminal Nets In Vlsi Physical Design, Jahangir A. Hashmi

Masters Theses

In this thesis, we study two problems related to the physical design of VLSI circuits. One problem is related to the VLSI global routing and the other is related to the detailed routing in a bounded region.

We consider the routing of multiple multi-terminal nets on a single layer. We suggest a new approach for this problem. Our approach is based on simultaneously finding a forest of k non-intersecting spanning trees. We present an O(n^3) algorithm for finding two spanning trees corresponding to two nets on a single layer.

We also study the problem of finding a minimum Steiner tree …

Formant Estimation From Dctc's Using A Feedforward Neural Network, Shubhangi U. Kelkar

Electrical & Computer Engineering Theses & Dissertations

Formants are the natural frequencies of the human vocal tract. Existing methods for estimating formants from speech signals are computationally complex and subject to errors for certain type of speech sounds. This thesis describes a method for estimating vowel formant frequencies from Discrete Cosine Transform Coefficients (DCTC's), a form of cepstral coefficients, using a feedforward neural network with back-propagation training. Experimental results are based on a large multispeaker data base. The results are obtained for both a linear transformation and a feedforward neural network with a nonlinear hidden layer. In general, the neural network transformation is superior to the linear …

Hardware-Verification Through Logic Extraction, Michael A. Dukes

Theses and Dissertations

A Prolog-based system is described which employs logic-extraction to perform hardware-verification. The extraction rules are built automatically from hierarchical structural VHDL models, enabling the equivalence of a structural VHDL description and a layout specification to be verified. Pin-to-pin critical- path analysis is performed within the logic-extraction process; many noncritical paths are pruned early, making pin-to-pin critical path analysis of large circuits feasible. It is demonstrated that a design methodology based on logic extraction, VHDL, and a layout tool can provide a fabricated functionally- correct IC design without circuit-level or switch-level simulation. This methodology is shown to be practical for VLSI …