Computer Sciences Commons^™

An Artificial Neural Approach To The Decomposition Problem, Chandrashekar L. Masti

Electrical & Computer Engineering Theses & Dissertations

The goal of this thesis is to develop an artificial neural approach toward addressing the intractability involved with the decomposition problem. The search for the lattice of substitution property (s. p.) partitions essential to decompositions is cast into the framework of constraint satisfaction. An artificial neural network is developed to provide solutions by performing optimization of a mathematically derived objective function over the problem space. The issue of transitivity is verified to belong to a class of problems beyond the scope of solvability for conventional quadratic-order constraint satisfaction neural networks. A theorem is stated and proved establishing that third-order correlations …

Encoding Phonetic Knowledge For Use In Hidden Markov Models Of Speech Recognition, Danming Qian

Electrical & Computer Engineering Theses & Dissertations

Hidden Markov models (HMM's) have achieved considerable success for isolated-word speaker-independent automatic speech recognition. However, the performance of an HMM algorithm is limited by its inability to discriminate between similar sounding words. The problem arises because all differences between speech patterns are treated as equally important. Thus the algorithm is particularly susceptible to confusions caused by phonetically-irrelevant differences. This thesis presents two types of preprocessing schemes as candidates for improving HMM performance. The aim is to maximize the differences between phonologically-distinct speech sounds while minimizing the effect of variations in phonologically-equivalent speech sounds. The preprocessors presented are a discrete cosine …

Visual Speech Training Aid For The Deaf, Subhashri Venkat

Electrical & Computer Engineering Theses & Dissertations

A computer-based vowel articulation training aid has been developed. A "continuous" acoustic-phonetic transformation is performed to map speech parameters to a lower dimensionality display space. There are two possible approaches to this transformation problem. The transformation could be either linear or a combination nonlinear/linear. The nonlinear transformation is performed using a multi-layered feedforward neural network with linear output layers. Speech parameters are extracted either from an analog filter bank arrangement (band energies) or by a digital signal processing procedure (Discrete Cosine Transform Coefficients). The speech parameters obtained from both methods correspond to the spectral envelope of the speech signals. The …

Efficient Interconnection Schemes For Vlsi And Parallel Computation, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

This thesis is primarily concerned with two problems of interconnecting components in VLSI technologies. In the first case, the goal is to construct efficient interconnection networks for general-purpose parallel computers. The second problem is a more specialized problem in the design of VLSI chips, namely multilayer channel routing. In addition, a final part of this thesis provides lower bounds on the area required for VLSI implementations of finite-state machines. This thesis shows that networks based on Leiserson's fat-tree architecture are nearly as good as any network built in a comparable amount of physical space. It shows that these "universal" networks …

Performance Modeling And Enhancement For The Atamm Data Flow Architecture, Sukhamoy Som

Electrical & Computer Engineering Theses & Dissertations

Algorithm To Architecture Mapping Model (ATAMM) is a new marked graph model from which the rules for data and control flow in a homogeneous, multicomputer, data flow architecture may be defined. This research is concerned with performance modeling and performance enhancement for periodic execution of large-grain, decision-free algorithms in such an ATAMM defined architecture. Performance measures and bounds are established. Algorithm transformation techniques are identified for performance enhancement and reduction of computing element requirements. Operating strategies are developed for optimum time performance and for sub-optimum time performance under limited availability of computing elements. An ATAMM simulator is used to test …

Efficient Multi-Layer Channel Routing, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

No abstract provided.

Randomized Routing On Fat-Trees, Ronald I. Greenberg, Charles E. Leiserson

Computer Science: Faculty Publications and Other Works

Fat-trees are a class of routing networks for hardware-efficient parallel computation. This paper presents a randomized algorithm for routing messages on a fat-tree. The quality of the algorithm is measured in terms of the load factor of a set of messages to be routed, which is a lower bound on the time required to deliver the messages. We show that if a set of messages has load factor lambda on a fat-tree with n processors, the number of delivery cycles (routing attempts) that the algorithm requires is O(lambda + lg n lg lg n) with probability 1-O(1/n). The best previous …

Lower Bounds On The Area Of Finite-State Machines, M. J. Foster, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

There are certain straightforward algorithms for laying out finite-state machines. This paper shows that these algorithm are optimal in the worst case for machines with fixed alphabets. That is, for any s and k, there is a deterministic finite-state machine with s states and k symbols such that any layout algorithm requires Ω(ks log s) area to lay out its realization. Similarly, any layout algorithm requires Ω(ks^2) area in the worst case for nondeterministic finite-state machines with s states and k symbols.

Mulch: A Multi-Layer Channel Router Using One, Two, And Three Layer Partitions, Ronald I. Greenberg, Alex T. Ishii, Alberto L. Sangiovanni-Vincentelli

Computer Science: Faculty Publications and Other Works

Chameleon, a channel router for three layers of interconnect, has been implemented to accept specification of an arbitrary number of layers. Chameleon is based on a strategy of decomposing the multilayer problem into two- and three-layer problems in which one of the layers is reserved primarily for vertical wire runs and the other layer(s) for horizontal runs. In some situations, however, it is advantageous to consider also layers that allow the routing of entire nets, using both horizontal and vertical wires. MulCh is a multilayer channel router that extends the algorithms of Chameleon in this direction. MulCh can route channels …

Implementing Ray Tracing Algorithm In Parallel Environment, Tjah Jadi

Dissertations and Theses

Ray tracing is a very popular rendering algorithm in the field of computer graphics because it can generate highly-realistic images from three-dimensional models. Unfortunately, the computational cost is very expensive. To speed up the rendering process we present both static and dynamic scheduling (balancing) strategies for a multiprocessor system. Hence, the load balancing among the processors is the most important problem in parallel processing. The implementation of the algorithm is based on a modified octree structure.

Model Of Hot-Film Sensor With Substrate Effects, David Mcalpine Judge

Electrical & Computer Engineering Theses & Dissertations

A detailed mathematical model is constructed to investigate the frequency response of a hot-film anemometer system. Since several diverse factors affect the frequency response, the analysis is broken down into three main parts. Each part is a detailed mathematical model. The first model consists of the ordinary differential equations which govern the electronics of the feedback system and heat transfer of the sensor. An important simplification in this model is that the rate of heat conduction from the sensor to its substrate is constant.

In the second model the unsteady state heat transfer properties of the substrate are examined by …

Wind Streamline Ambiguity Removal Of Microwave Scatterometer Data, Hans W. Zaepfel

Electrical & Computer Engineering Theses & Dissertations

There is a class of satellite microwave scatterometers that return oceanographic information which includes wind vectors with directional ambiguity. The first part of the ambiguity removal process is to reduce the data to a directional ambiguity of 180°. This thesis shows that wind direction change contains the information required for streamline ambiguity removal and that syntactic pattern recognition techniques can be used to locate the areas of wind direction change. Spreading the information along the areas of wind direction change results in the removal of the streamline ambiguity. The algorithm is implemented and the results are presented showing that it …

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 …

Retrospective Data Filter, Richard J. Prengaman, Robert E. Thurber, Joe Phipps, Ronald I. Greenberg, Wai L. Hom, James F. Jaworski, Guy W. Riffle

Computer Science: Faculty Publications and Other Works

In a target detection communication system, apparatus and method for determining the presence of probable targets based on contacts (which can indicate the presence of a target, noise, chatter, or objects not of interest) detected within a predefined position sector or sectors over a specified number of scans. The position of each detected contact, as a contact of interest, is compared with the positions of contacts detected at previous times or scans. Velocity profiles indicate which previous contacts support the likelihood that the contact of interest represents a target having a velocity within a defined band. The likelihood, which can …

Design Of Multivariable Feedback Control Systems Via Spectral Assignment, Mohsen Marefat

Electrical & Computer Engineering Theses & Dissertations

During the past 15 year s significant advances have been made towards developing viable synthesis- techniques for multivariable feedback control systems. The entire aggregate of this theoretical work has been reviewed and consolidated. Diverse notations have been standardized into a single system. A two-step design philosophy for spectral assignment has been developed which first meets stability and time response requirements by assigning eigenvalues and eigenvector s and then provides for attainment of secondary objectives without significant deviation from the initial assignment. Finally, a computer-aided design package has been created to streamline the process of mathematical calculation and to allow users …

High Performance Switching Circuits For Vlsi, Ali Reza Feizi

Electrical & Computer Engineering Theses & Dissertations

Interconnection topology and device performance are of major concern in the design of LSI/VLSI systems, Pass networks are very suitable in this regard because of low power consumption, high density, and simple interconnection topology. A special type of pass networks called Binary Tree Structured (BTS) pass networks uses almost minimum number of transistors for the design of switching circuits. An algorithmic procedure is developed here for BTS pass networks which is very efficient in terms of both execution time and memory space. Based on these networks, the necessary and sufficient conditions are derived for the design of multiple-output pass networks. …

Randomized Routing On Fat-Trees, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

Fat-trees are a class of routing networks for hardware-efficient parallel computation. This paper presents a randomized algorithm for routing messages on a fat-tree. The quality of the algorithm is measured in terms of the load factor of a set of messages to be routed, which is a lower bound on the time required to deliver the messages. We show that if a set of messages has load factor lambda on a fat-tree with n processors, the number of delivery cycles (routing attempts) that the algorithm requires is O(lambda+lgnlglgn) with probability 1-O(1/ …

Color Display Of Vowel Spectra As A Training Aid For The Deaf, Amir Jalali Jagharghi

Electrical & Computer Engineering Theses & Dissertations

The objective of this research was to develop a transformation for mapping speech parameters to color parameter. This transformation is done in real-time, and the resulting color parameter are continuously displayed on a color monitor. This visual speech display is to be used as a speech articulation training aid for the deaf. The conversion of speech acoustic signals into speech parameter was accomplished using special -purpose electronics. The real-time conversion of speech parameter to display parameter was controlled by an 8086/8088 microprocessor operating in an S-100 bus structure. The coefficients of the Karhunen-Loeve series expansion of speech power spectra were …

Design Of Infrasound-Detection System Via Adaptive Lmstde Algorithm, Camille S. Khalaf

Electrical & Computer Engineering Theses & Dissertations

A proposed solution to an aviation safety problem is based on passive detection of turbulent weather phenomena through their infrasonic emission. This thesis describes a system design that is adequate for detection and bearing evaluation of infrasounds. An array of four sensors, with the appropriate hardware, is used for the detection part. Bearing evaluation is based on estimates of time delays between sensor outputs. The generalized cross correlation (GCC), as the conventional time-delay estimation (TOE) method, is first reviewed. An adaptive TUt approach, using the least mean square (LMS) algorithm, is then discussed. A comparison between the two techniques is …

A Dimensionality Reduction Algorithm For The Karhunen Loeve Transform, Salomi T. Charalambous

Computational Modeling & Simulation Engineering Theses & Dissertations

The Karhunen Loeve Transform has conclusively been shown to be the optimum data compression algorithm for signals belonging to the same second order stationary process. Consequently, researchers have been searching for a fast implementation for the transform. Fast imple­mentation methods similar to those developed for other orthogonal transforms are generally not applicable to the Karhunen Loeve Transform (KLT). Also, since the basis vectors composing the transformation matrix of the KLT are the eigenvectors of the covariance matrix of the input process, they must be computed first. The research re­ ported here is an attempt to reduce the dimensionality of the …

An Efficient Dft Algorithm Using The Walsh Transform, Albert P. Gerheim

Electrical & Computer Engineering Theses & Dissertations

The matrix transformation relating the sequency and frequency domains is derived. It is shown that these­ frequency-to-frequency conversion can be performed via a computationally efficient sparse matrix algorithm. The sequency-to-frequency algorithm can be used with a fast Hadamard transform to implement a discrete Fourier trans­ form. The efficiencies of this combined algorithm and a radix-two fast Fourier transform are compared.

The algorithm is applied to the sequency domain de­ sign of a Wiener digital filter. Improved computational efficiencies are achieved relative to the procedure de­veloped by Kahveci and Hall (9).

Digital Computer Solution Of Electromagnetic Transients In Large Power Systems, Bijan Navidbakhsh

Dissertations and Theses

This thesis is an introduction to the solution of electromagnetic transients by a combination of the Bergeran method of characteristics and the application of trapezoidal rule of integration.

Three test examples solved by digital computer illustrate the step by step solution and computer programming.

To compare this method with the Laplace transformation technique, a test problem solved by both methods and also digital computer is illustrated. In conclusion, the advantages and disadvantages of both methods are compared.

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 …