Engineering Commons^™

Development Of A Configurable Real-Time Event Detection Framework For Power Systems Using Swarm Intelligence Optimization, Umar Farooq

Dissertations and Theses

Modern power systems characterized by complex topologies require accurate situational awareness to maintain an adequate level of reliability. Since they are large and spread over wide geographical areas, occurrence of failures is inevitable in power systems. Various generation and transmission disturbances give rise to a mismatch between generation and demand, which manifest as frequency events. These events can take the form of negligible frequency deviations or more severe emergencies that can precipitate cascading outages, depending on the severity of the disturbance and efficacy of remedial action schema. The impacts of such events have become more critical with recent decline in …

Methodologies For Quantum Circuit And Algorithm Design At Low And High Levels, Edison Tsai

Dissertations and Theses

Although the concept of quantum computing has existed for decades, the technology needed to successfully implement a quantum computing system has not yet reached the level of sophistication, reliability, and scalability necessary for commercial viability until very recently. Significant progress on this front was made in the past few years, with IBM planning to create a 1000-qubit chip by the end of 2023, and Google already claiming to have achieved quantum supremacy. Other major industry players such as Intel and Microsoft have also invested significant amounts of resources into quantum computing research.

Any viable computing system requires both hardware and …

Quantum Grover's Oracles With Symmetry Boolean Functions, Peng Gao

Dissertations and Theses

Quantum computing has become an important research field of computer science and engineering. Among many quantum algorithms, Grover's algorithm is one of the most famous ones. Designing an effective quantum oracle poses a challenging conundrum in circuit and system-level design for practical application realization of Grover's algorithm.

In this dissertation, we present a new method to build quantum oracles for Grover's algorithm to solve graph theory problems. We explore generalized Boolean symmetric functions with lattice diagrams to develop a low quantum cost and area efficient quantum oracle. We study two graph theory problems: cycle detection of undirected graphs and generalized …

Classical Search And Quantum Search Algorithms For Synthesis Of Quantum Circuits And Optimization Of Quantum Oracles, Sazzad Hossain

Dissertations and Theses

We observe an enormous increase in the computational power of digital computers. This was due to the revolution in manufacturing processes and controlling semiconductor structures on submicron scale, ultimately leading to the control of individual atoms. Eventually, the classical electric circuits encountered the barrier of quantum mechanics and its effects. However, the laws of quantum mechanics can be also used to produce computational devices that lead to extraordinary speed increases over classical computers. Thus quantum computing becomes a very promising and attractive research area. The Computer Aided Design for Quantum circuits becomes an essential ingredient for such emerging research which …

Ternary Quantum Logic, Normen Giesecke

Dissertations and Theses

The application of Moore's Law would not be feasible by using the computing systems fabrication principles that are prevalent today. Fundamental changes in the field of computing are needed to keep Moore's Law operational. Different quantum technologies are available to take the advancement of computing into the future. Logic in quantum technology uses gates that are very different from those used in contemporary technology. Limiting itself to reversible operations, this thesis presents different methods to realize these logic gates. Two methods using Generalized Ternary Gates and Muthukrishnan Stroud Gates are presented for synthesis of ternary logic gates. Realizations of well-known …

Design And Evaluation Of A Specialized Computer Architecture For Manipulating Binary Decision Diagrams, Robert K. Hatt

Dissertations and Theses

Binary Decision Diagrams (BDDs) are an extremely important data structure used in many logic design, synthesis and verification applications. Symbolic problem representations make BDDs a feasible data structure for use on many problems that have discrete representations. Efficient implementations of BOD algorithms on general purpose computers has made manipulating large binary decision diagrams possible. Much research has gone into making BOD algorithms more efficient on general purpose computers. Despite amazing increases in performance and capacity of such computers over the last decade, they may not be the best way to solve large, specialized problems. A computer architecture designed specifically to …

Jitter And Wander Reduction For A Sonet Ds3 Desynchronizer Using Predictive Fuzzy Control, Kevin Blythe Stanton

Dissertations and Theses

Excessive high-frequency jitter or low-frequency wander can create problems within synchronous transmission systems and must be kept within limits to ensure reliable network operation. The emerging Synchronous Optical NETwork (SONET) introduces additional challenges for jitter and wander attenuation equipment (called desynchronizers) when used to carry payloads from the existing Plesiochronous Digital Hierarchy (PDH), such as the DS3. The difficulty is primarily due to the large phase transients resulting from the pointer-based justification technique employed by SONET (called Pointer Justification Events or PJEs). While some previous desynchronization techniques consider the buffer level in their control actions, none has explicitly considered wander …

Minimization Of Sum-Of-Conditional-Decoders Structures With Applications In Finite Machine Epld Design And Machine Learning, Sanof Mohamedsadakathulla

Dissertations and Theses

In order to achieve superior speed in sequencer designs over competing PLD devices, Cypress brought to market an innovative architecture, CY7C361. This architecture introduced a new kind of universal logic gate, the CONDITION DECODER (CDEC). Because there are only 32 macrocells in the chip, saving only one CDEC gate can be quite important (the well-known "fit/no-fit problem"). A problem that is related to the fitting problem of the Cypress CY7C361 chip is the SOC Minimization. Due to the limited low number of macrocells in CY7C361, a high quality logic minimization to reduce the number of macrocells is very important. The …

An Analysis Of Approaches To Efficient Hardware Realization Of Image Compression Algorithms, Kamran Iravani

Dissertations and Theses

In this thesis an attempt has been made to develop a fast algorithm to compress images. The Reed-Muller compression algorithm which was introduced by Reddy & Pai [3] is fast, but the compression factor is too low when compared to the other methods. In this thesis first research has been done to improve this method by generalizing the Reed-Muller transform to the fixed polarity Reed-Muller form. This thesis shows that the Fixed Polarity Reed-Muller transform does not improve the compression factor enough to warrant its use as an image compression method. The paper, by Reddy & Pai [3], on Reed-Muller …

High Level Preprocessor Of A Vhdl-Based Design System, Karthikeyan Palanisamy

Dissertations and Theses

This thesis presents the work done on a design automation system in which high-level synthesis is integrated with logic synthesis. DIADESfa design automation system developed at PSU, starts the synthesis process from a language called ADL. The major part of this thesis deals with transforming the ADL -based DIADES system into a VHDL -based DIADES system. In this thesis I have upgraded and modified the existing DIADES system so that it becomes a preprocessor to a comprehensive VHDL -based design system from Mentor Graphics. The high-level synthesis in the DIADES system includes two stages: data path synthesis and control unit …

Minimization Of Generalized Reed-Muller Expansion And Its Sub-Class, Xiaoqiang Zeng

Dissertations and Theses

Several classes of AND-EXOR circuit expressions have been defined and their relationship have been shown. A new class of AND-EXOR circuit, the Partially Mixed Polarity Reed-Muller Expression(PMPRM), which is a subclass of the Generalized Reed-Muller expression, is created, along with an efficient minimization algorithm. This new AND/EXOR circuit form has the following features: • Since this sub-family of ESOP (with a total of n2n-I22n-i - (n-1)2n forms which includes the 2n Fixed-Polarity Reed-Muller forms) is much larger than the Kronecker Reed-Muller(KRM) expansion(with 3n forms), generally the minimal form of this expansion will be much closer to the minimal ESOP than …

Investigation Of Solution Space Of Trees And Dags For Realization Of Combinational Logic In At 6000 Series Fpgas, Philip Ho

Dissertations and Theses

Various tree and Directed Acyclic Graph structures have been used for representation and manipulation of switching functions. Among these structures the Binary Decision DiagramJilave been the most widely used in logic synthesis. A BDD is a binary tree graph that represents the recursive execution of Shannon's expansion. A FDD is a directed function graph that represents the recursive execution of Reed Muller expansion. A family of decision diagrams for representation of Boolean function is introduced in this thesis. This family of Kronecker Functional Decision Diagrams (KFDD) includes the Binary Decision Diagrams (BDD) and Functional Decision Diagrams (FDD) as subsets. Due …

Vertex Ordering For A Partitioning-Based Fitting Algorithm For An Epld Device, Tongjun Gao

Dissertations and Theses

As the Application-Specific Integrated Circuit(ASIC) technology develops to the trend of high density and modulization, the ASIC device market has been dominated gradually by the more complex Erasable Programmable Logic Devices (EPLDs) and the Field Programmable Gate Array(FPGAs) instead of the ordinally Programmable Logic Devices(PLDs). Meanwhile, the design automation system for such programmable devices has also moved from schematic entry design to high level hardware description language entry design. Usually, the whole design automation process consists of three phrases, the high level hardware description language compiler, the logic synthesis stage and the layout synthesis stage. Though the layout synthesis stage …

Designing And Simulating A Multistage Sampling Rate Conversion System Using A Set Of Pc Programs, David Joseph Hagerty

Dissertations and Theses

The thesis covers a series of PC programs that we have written that will enable users to easily design FIR linear phase lowpass digital filters and multistage sampling rate conversion systems. The first program is a rewrite of the McClellan-Parks computer program with some slight modifications. The second program uses an algorithm proposed by Rabiner that determines the length of a lowpass digital filter. Rabiner used a formula proposed by Herrmann et al. to initially estimate the filter length in his algorithm. The formula, however, assumes unity gain. We present a modification to the formula so that the gain of …

Quasi-Static Deflection Compensation Control Of Flexible Manipulator, Jingbin Feng

Dissertations and Theses

The growing need in industrial applications of high-performance robots has led to designs of lightweight robot arms. However the light-weight robot arm introduces accuracy and vibration problems. The classical robot design and control method based on the rigid body assumption is no longer satisfactory for the light-weight manipulators. The effects of flexibility of light-weight manipulators have been an active research area in recent years. A new approach to correct the quasi-static position and orientation error of the end-effector of a manipulator with flexible links is studied in this project. In this approach, strain gages are used to monitor the elastic …

A Robust High Precision Algorithm For Sinewave Parameter Estimation, Kendall Ann Rydell

Dissertations and Theses

The estimation of sinewave parameters has many practical applications in test and data processing systems. Measuring the effective bits of an analog-to-digital converter and linear circuit identification are some typical examples. If a sinew ave's frequency is known, there is an established linear method to estimate the other parameters. But when none of the parameters are known (which is usually the case in practical situations), the estimation problem becomes more difficult. Traditional approaches to this task applied an iterative, sinewave curve-fit algorithm. Two problems with this technique are that convergence is often slow and not always guaranteed and the results …

Minimization Of Permuted Reed-Muller Trees And Reed-Muller Trees For Cellular Logic Programmable Gate Arrays, Lifei Wu

Dissertations and Theses

The new family of Field Programmable Gate Arrays, CLI 6000 from Concurrent Logic Inc realizes truly Cellular Logic. It has been mainly designed for the realization of data path architectures. However, the realizable logic functions provided by its macrocells and their limited connectivity call also for new general-purpose logic synthesis methods. The basic cell of CLi 6000 can be programmed to realize a two-input multiplexer ( A*B + C*B ), an AND/EXOR cell ( A*B Ea C ), or the basic 2-input AND, OR and EXOR gate. This suggests to using these cells for tree-like expansions. These "cellular logic" devices …

Minimization Of Exclusive Sum Of Products Expressions For Multiple-Valued Input Incompletely Specified Functions, Ning Song

Dissertations and Theses

In recent years, there is an increased interest in the design of logic circuits which use EXOR gates. Particular interest is in the minimization of arbitrary Exclusive Sums Of Products (ESOPs). Functions realized by such circuits can have fewer gates, fewer connections, and take up less area in VLSI and especially, FPGA realizations. They are also easily testable. So far, the ESOPs are not as popular as their Sum of Products (SOP) counterparts. One of the main reasons it that the problem of the minimization of ESOP circuits was traditionally an extremely difficult one. Since exact solutions can be practically …

Effectiveness Of Additive Correction Multigrid In Numerical Heat Transfer Analysis When Implemented On An Intel Ipsc2, James D. Padgett

Dissertations and Theses

The effectiveness of the Additive Correction Multigrid (ACM) algorithm, a line-byline Tri-diagonal Matrix Algorithm (TDMA), and simple Gauss-Seidel (GS) iteration in numerical heat transfer analysis is investigated on a conventional single processor computer and on a distributed memory parallel computer. The performance of these methods is studied by solving a two-dimensional, steady heat conduction problem. The execution time of ACM on a single processor is proportional to the number of unknowns to the 1.5 power. This is in contrast to the execution time of the TDMA for which the execution time is proportional to the number of unknowns to the …

Mapping Programs To Parallel Architectures In The Real World, Dezheng Tang

Dissertations and Theses

Mapping an application program to a parallel architecture can be described as a multidimensional optimization problem. To simplify the problem, we divide the overall mapping process into three sequential substeps: partitioning, allocating, and scheduling, with each step using a few details of the program and architecture description. Due to the difficulty in accurately describing the program and architecture and the fact that each substep uses incomplete information, inaccuracy is pervasive in the real-world mapping process. We hypothesize that the inaccuracy and the use of suboptimal, heuristic mapping methods may greatly affect the mapping or submapping performance and lead to a …

Ignoring Interprocessor Communication During Scheduling, Chintamani M. Patwardhan

Dissertations and Theses

The goal of parallel processing is to achieve high speed computing by partitioning a program into concurrent parts, assigning them in an efficient way to the available processors, scheduling the program and then executing the concurrent parts simultaneously. In the past researchers have combined the allocation of tasks in a program and scheduling of those tasks into one operation. We define scheduling as a process of efficiently assigning priorities to the already allocated tasks in a program. Assignment of priorities is important in cases when more than one task at a processor is ready for execution. Most heuristics for scheduling …

A Partitioning-Based Approach To The Fitting Problem In Special Architecture Eplds, Steffan Goller

Dissertations and Theses

In this thesis, we describe an architecture-driven fitting algorithm for an Application-Specific EPLD, the CY7C361, from Cypress Semiconductor. Traditional placement and routing tools for PLDs perform placement and routing separately. Several placement possibilities are created and the router tries to realize the connections between the physical locations of the cells on the chip. The Cypress CY7C361 has a very unique chip architecture with a highly limited connectivity between the physical cells. Therefore, it is necessary to consider the mutability when the placement of cells is performed. The combination of the two stages is called fitting. The specific architecture-dependent constraints, imposed …

Improved I/O Pad Positions Assignment Algorithm For Sea-Of-Gates Placement, Shyang-Kuen Her

Dissertations and Theses

A new heuristic method to improve the I/O pad assignment for the sea-of-gates placement algorithm "PROUD" is proposed. In PROUD, the preplaced I/O pads are used as the boundary conditions in solving sparse linear equations to obtain the optimal module placement. Due to the total wire length determined by the module positions is the strong function of the preplaced I/O pad positions, the optimization of the I/O pad circular order and their assignment to the physical locations on the chip are attempted in the thesis. The proposed I/O pad assignment program is used as a predecessor of PROUD. The results …

Parplum : A System For Evaluating Parallel Program Optimization Methods, Jingsong Fu

Dissertations and Theses

The diversity of application programs and parallel architectures makes the mapping problem complicated and hard to evaluate. The quality of mapping is machine and application dependent and varies due to inaccurate values of application and architecture characteristics.

A system for developing, applying and evaluating mappings must have four characteristics: (1) Simplicity: A mapping procedure can be evaluated by separately evaluating its submapping, so the complicated problem can be simplified. (2) Generality: A wide range of application programs and architectures can be easily represented and all mapping algorithms can be easily implemented. (3) Multifunctionality: all the mapping steps, application programs, target …

A Practical Parallel Algorithm For The Minimization Of KröNecker Reed-Muller Expansions, Paul John Gilliam

Dissertations and Theses

A number of recent developments has increased the desirability of using exclusive OR (XOR) gates in the synthesis of switching functions. This has, in turn, led naturally to an increased interest in algorithms for the minimization of Exclusive-Or Sum of Products (ESOP) forms. Although this is an active area of research, it is not nearly as developed as the traditional Sum of Products forms. Computer programs to find minimum ESOPs are not readily available and those that do exist are impractical to use as investigative tools because they are too slow and/or require too much memory. A practical tool would …

An Effective Cube Comparison Method For Discrete Spectral Transformations Of Logic Functions, Ingo SchäFer

Dissertations and Theses

Spectral methods have been used for many applications in digital logic design, digital signal processing and telecommunications. In digital logic design they are implemented for testing of logical networks, multiplexer-based logic synthesis, signal processing, image processing and pattern analysis. New developments of more efficient algorithms for spectral transformations (Rademacher-Walsh, Generalized Reed-Muller, Adding, Arithmetic, multiple-valued Walsh and multiple-valued Generalized Reed- Muller) their implementation and applications will be described.

Endless State-Of-Polarization Control For Coherent Optical Communication Systems Using Nematic Liquid Crystal, Scott H. Rumbaugh

Dissertations and Theses

One of the obstacles to coherent fiber-optic communications is the unpredictable polarization drift which necessitates the use of an active polarization controlling system to match the polarizations of the signal and local oscillator. The polarization match must be maintained during the reset of any of the finite range components to prevent loss of data. We present a novel and practical system which uses three liquid crystal devices for the polarization matching process. Also, the required reset control algorithm and its derivation are described in detail.