Engineering Commons^™

A Transformation-Based Approach To Implication Of Gste Assertion Graphs, Gouwu Yang, William N. N. Hung, Xiaoyu Song, Wensheng Guo

Electrical and Computer Engineering Faculty Publications and Presentations

Generalized symbolic trajectory evaluation (GSTE) is a model checking approach and has successfully demonstrated its powerful capacity in formal verification of VLSI systems. GSTE is an extension of symbolic trajectory evaluation (STE) to the model checking of -regular properties. It is an alternative to classical model checking algorithms where properties are specified as finite-state automata. In GSTE, properties are specified as assertion graphs, which are labeled directed graphs where each edge is labeled with two labeling functions: antecedent and consequent. In this paper, we show the complement relation between GSTE assertion graphs and finite-state automata with the expressiveness of regular …

Improved Complexity Of Quantum Oracles For Ternary Grover Algorithm For Graph Coloring, Marek Perkowski, Yushi Wang

Electrical and Computer Engineering Faculty Publications and Presentations

The Graph Coloring Grover Algorithm has several applications in logic synthesis, scheduling, allocation, planning, robot motion, robot communication, resource allocation, conflict resolution, floor-planning, and many others.

It can serve as a “generic CSP solver” similar to a general SAT solver.

Search For Universal Ternary Quantum Gate Sets With Exact Minimum Costs, Marek Perkowski, Normen Giesecke, Dong Hwa Kim, Sazzad Hossain

Electrical and Computer Engineering Faculty Publications and Presentations

The choice of the best set of universal ternary gates for quantum circuits is an open problem. We create exact minimum cost ternary reversible gates with quantum multiplexers using the method of iterative deepening depth-first search (IDDFS) [25]. Such search is better for small problems than evolutionary algorithms or other search methods. Several new gates that are provably exact minimum cost have been discovered. These gates are next used as library building blocks in the minimization of larger ternary quantum circuits like highly testable GFSOP cascades [15,16] (that generalize ESOP) as well as the wave cascades [24] generalized to ternary …

Realization Of Incompletely Specified Functions In Minimized Reversible Cascades, Marek Perkowski, Manjith Kumar, Bala Iyer, Natalie Metzger, Ying Wang

Electrical and Computer Engineering Faculty Publications and Presentations

There is a need to convert non-reversible functions to their corresponding reversible functions to be realized as reversible cascades. The original MMD (D.M.Miller, D. Maslov, and G.W.Dueck) algorithm for synthesis of reversible functions using cascades of reversible gates [1] can be modified to allow for the inclusion of “don't cares” within the given function's truth table (reversible or irreversible). This was achieved in the approach presented, by first initializing the “don't cares” to binary values, synthesizing the network using the base MMD algorithm, comparing the cost, and iterating to find an implementation with the smallest possible cost. The “don't care” …

A Transformation Based Algorithm For Ternary Reversible Logic Synthesis Using Universally Controlled Ternary Gates, Marek Perkowski, Eric Curtis

Electrical and Computer Engineering Faculty Publications and Presentations

In this paper a synthesis algorithm for reversible ternary logic cascades is presented. The algorithm can find a solution for any reversible ternary function with n inputs and n outputs utilizing ternary inverter gates and the new (quantum realizable) UCTG gates which are a powerful generalization of ternary Toffoli gates and Generalized Ternary Gates [4]. The algorithm is an extension of the algorithm presented by Dueck, Maslov, and Miller in [3]. A unique feature of this algorithm is that it utilizes no extra wires to generate the outputs. A basic compaction algorithm is defined to improve the results of the …

Exact Graph Coloring For Functional Decomposition: Do We Need It?, Marek Perkowski, Rahul Malvi, Lech Jozwiak

Electrical and Computer Engineering Faculty Publications and Presentations

Finding column multiplicity index is one of important component processes in functional decomposition of discrete functions for circuit design and especially Data Mining applications. How important it is to solve this problem exactly from the point of view of the minimum complexity of decomposition, and related to it error in Machine Learning type of applications? In order to investigate this problem we wrote two graph coloring programs: exact program EXOC and approximate program DOM (DOM cab give provably exact results on some types of graphs). These programs were next incorporated into the multi-valued decomposer of functions and relations NVGUD. Extensive …