Theory and Algorithms Commons^™

A Software Design Tool For Predictable Performance In Real-Time, Data Flow Architectures, Brij Mohan V. Mandala

Electrical & Computer Engineering Theses & Dissertations

A software design tool which aids in the performance evaluation and selection of operating points for an algorithm implemented in ATAMM defined data flow architectures is presented in this thesis. ATAMM (Algorithm To Architecture Mapping Model) is a new graph theoretic model developed by researchers at Old Dominion University and the NASA-Langley Research Center. ATAMM is capable of modeling the execution of large-grained algorithms on distributed data flow architectures. A software tool is required for predicting the performance, determining the resource requirements and for selecting suitable operating points for an ATAMM based system. The ATAMM Design Tool presented in this …

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 …

A Root Finding Algorithm For Parallel Architecture Machines, Stuti Moitra

Computer Science Theses & Dissertations

In this thesis a parallel algorithm for determining the zeros of any given analytic function is described. Parallelism is achieved by modifying the traditional bisection algorithm for architecture machines.

Given any user supplied function f(X), continuous on the interval A_o ≤ x ≤ B₀, and the tolerance of accuracy an algorithm of determining up to ten roots, with error of approximation less than or equal to tolerance, on parallel systems like Distributed Array Processor (OAP) and N-cube is considered.

A variation of the bisection method has been adapted for this purpose. At each level of iteration a …

Diagnostics Software For Concurrent Processing Computer Systems, Robert L. Jones Iii

Electrical & Computer Engineering Theses & Dissertations

Diagnostics software for analyzing ATAMM based concurrent processing systems is presented in this thesis. ATAMM (Algorithm to Architecture Mapping Model) is a new model developed by researchers at Old Dominion University and the NASA-Langley Research Center. ATAMM is capable of modeling the execution of large grain algorithms on distributed data flow architectures. Investigating a real or simulated ATAMM based system requires the aid of software tools. The software tool presented in this thesis can evaluate the behavior and performance of an ATAMM based system. The tool graphically portrays algorithm activities and processor activities. The tool's measurement capabilities indicate computing speed, …

Pipelining Data Compression Algorithms, R. L. Bailey, R. Mukkamala

Computer Science Faculty Publications

Many different data compression techniques currently exist. Each has its own advantages and disadvantages. Combining (pipelining) multiple data compression techniques could achieve better compression rates than is possible with either technique individually. This paper proposes a pipelining technique and investigates the characteristics of two example pipelining algorithms. Their performance is compared with other well-known compression techniques.

Efficient Schemes To Evaluate Transaction Performance In Distributed Database Systems, R. Mukkamala, S. C. Bruell

Computer Science Faculty Publications

Database designers and researchers often need efficient schemes to evaluate transaction performance. In this paper, we chose two important performance measures: the average number of nodes accessed and the average number of data items accessed per node by a transaction in a distributed database system. We derive analytical expressions to evaluate these metrics. For general applicability, we consider partially replicated distributed database systems. Our first set of analytic results are closed-form expressions for these two measures. These are based on some fairly restrictive simplifying assumptions. When these assumptions are relaxed, no closed-form expressions exist for these averages. Hence, we develop …

Optical Machine Recognition Of Lower-Case Greek Characters Of Any Size, Ivan X. D. D'Cunha

Electrical & Computer Engineering Theses & Dissertations

An algorithm utilizing a syntactic approach and a criterion based on normalized moments is defined for the reliable, automatic, machine recognition of handwritten and printed Greek characters of any size and font. In this approach a binary image of the character in question is obtained initially; its skeleton is then produced by utilizing a standard thinning algorithm. The classification process then incorporates the topological features of the characters such as existence of closed curves, number of intersections, number and location of free ends, axial symmetry, and the criteria derived from normalized moments to uniquely identify each pattern. Experiments conducted demonstrated …

Software Tools For Performance Evaluation Of Concurrent Processing, Rodrogo A. Obando

Electrical & Computer Engineering Theses & Dissertations

The development and use of software tools for performance evaluation of concurrent processing is presented in this thesis. The particular concurrent processing architecture proposed by Stoughton and Mielke is investigated. The modelling of this architecture is based on Petri net theory and it can be studied making use of circuit theory. Computation of lower bounds for Time Between Outputs (TBO) and Time Between Input and Output (TBIO) can be accomplished by using principles of circuit theory, among others. This new modelling needs to be deeply evaluated and studied. This evaluation and study is accomplished with the tools developed and presented …

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 …

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. …

Analog Computer Simulation With Automatic Scaling By Digital Computer, Mark Anthony Motter

Electrical & Computer Engineering Theses & Dissertations

A computer-aided design approach for the simplification of analog computer simulation is presented. The simulation configuration consists of an EAI 2000 analog computer with serial communications link to a PDP — 11/24 digital computer. Under control of the PDP-11, the analog simulations are realized with appropriate time and magnitude scaling which adjusts the range of the simulation coefficients and prevents overloads of the analog components. The analog computer hardware configuration accommodates both stable plants up to eighth order and closed-loop systems up to tenth order. Cascade compensation is provided for the closed-loop systems.

The plant may be described by either …

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 …

Block Encoding Of Speech Spectral Principal Components, James R. Holland Jr.

Electrical & Computer Engineering Theses & Dissertations

A Karhunen-Loeve series expansion was used to block encode speech spectral principal components as a function of time. Each of ten principal components was first obtained as a linear combination of 2© speech spectral band energies. Using a fixed block length of 10 frames (0.128 s), the K-L basis vectors were computed separately for various speakers for each principal component. In all cases the resulting basis vectors were essentially a set of discrete cosine basis vectors. Synthesis of speech from the block encoded parameters showed that very little information is lost with up to 70% data reduction. The block encoding …

Suboptimal Algorithms For Improvement Of Pipeline Through Insertion Of Delays, Sukhamoy Som

Electrical & Computer Engineering Theses & Dissertations

Pipelining is now widely used in the design of high speed processors in order to overcome the intrinsic speed limitations imposed by the technology. For a good performance and avoidance of internal conflicts, the concurrent operations within different subunits of a pipeline architecture should be properly scheduled This scheduling problem is known to be intrinsically difficult" and a member of the "NP complete class of problems. The aim of this thesis is to develop heuristic suboptimal algorithms whose execution time is a polynomial function of the number of items to be scheduled. Insertion of delay is used as a basic …

A Direct Formulation And Computer-Implementation Of A Symbolic Network Analysis Algorithm, Timothy James Knerr

Electrical & Computer Engineering Theses & Dissertations

An algorithm for the symbolic analysis of linear, time-invariant, active or passive networks is presented. The algorithm incorporates the best features of earlier numerical and topological methods of symbolic analysis. A hybrid set of equations is formulated for a closed linear graph and arranged in matrix form. A numerical evalu­ation procedure for the determinant of this hybrid matrix results in an efficient method of symbolic analysis. A proof of the algorithm based on determinant evaluation by a permutation product expansion provides insight into relationships with other methods of symbolic analysis. A computer program implementation of the algorithm is described and …

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 Algorithm For The Electromagnetic Scattering Due To An Axially Symmetric Body With An Impedance Boundary Condition, F. Stenger, M. Hagmann, J. Scheing

Computer Science Faculty Publications

Let B be a body in R³, and let S denote the boundary of B. The surface S is described by S = {(x, y, z): (x² + Y²)^½= ƒ(z), -1≤ z ≤ I}, where ƒ analytic function that is real and positive on (-1, 1) and ƒ(±1) = 0. An algorithm is described for computing the scattered field due to a plane wave incident field, under Leontovich boundary conditions. The Galerkin method of solution used here leads to a block diagonal matrix involving 2M …

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).