Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 7 of 7
Full-Text Articles in Engineering
Ternary Logic Design In Topological Quantum Computing, Muhammad Ilyas, Shawn Cui, Marek Perkowski
Ternary Logic Design In Topological Quantum Computing, Muhammad Ilyas, Shawn Cui, Marek Perkowski
Electrical and Computer Engineering Faculty Publications and Presentations
A quantum computer can perform exponentially faster than its classical counterpart. It works on the principle of superposition. But due to the decoherence effect, the superposition of a quantum state gets destroyed by the interaction with the environment. It is a real challenge to completely isolate a quantum system to make it free of decoherence. This problem can be circumvented by the use of topological quantum phases of matter. These phases have quasiparticles excitations called anyons. The anyons are charge-flux composites and show exotic fractional statistics. When the order of exchange matters, then the anyons are called non-Abelian anyons. Majorana …
Application Of Cuda In The Boolean Domain For The Unate Covering Problem, Eric Paul, Bernd Steinbach, Marek Perkowski
Application Of Cuda In The Boolean Domain For The Unate Covering Problem, Eric Paul, Bernd Steinbach, Marek Perkowski
Electrical and Computer Engineering Faculty Publications and Presentations
NVIDIA’s Compute Unified Device Architecture (CUDA) is a relatively-recent development that allows to realize very fast algorithms for several Constraint Satisfaction and Computer Aided Design tasks. In this paper we present an approach to use Graphics Processing Units (GPU) and CUDA for solving Unate Covering Problem, a practical problem related to SAT. In particular we present a CUDA-enabled Petrick Function Minimizer. We compare the performance of a pipeline-processor (CPU) and a parallel processor (GPU) implementation of the matrix-multiplication method for solving unate covering problems.
Logic Synthesis For Layout Regularity Using Decision Diagrams, Malgorzata Chrzanowska-Jeske, Alan Mishchenko, Jinsong Zhang, Marek Perkowski
Logic Synthesis For Layout Regularity Using Decision Diagrams, Malgorzata Chrzanowska-Jeske, Alan Mishchenko, Jinsong Zhang, Marek Perkowski
Electrical and Computer Engineering Faculty Publications and Presentations
This paper presents a methodology for logic synthesis of Boolean functions in the form of regular structures that can be mapped into standard cells or programmable devices. Regularity offers an elegant solution to hard problems arising in layout and test generation, at no extra cost or at the cost of increasing the number of gates, which does not always translate into the increase of circuit area. Previous attempts to synthesize logic into regular structures using decision diagrams suffered from an increase in the number of logic levels due to multiple repetitions of control variables. This paper proposes new techniques, which …
Function-Driven Linearly Independent Expansions Of Boolean Functions And Their Application To Synthesis Of Reversible Circuits, Pawel Kerntopf, Marek Perkowski
Function-Driven Linearly Independent Expansions Of Boolean Functions And Their Application To Synthesis Of Reversible Circuits, Pawel Kerntopf, Marek Perkowski
Electrical and Computer Engineering Faculty Publications and Presentations
The paper presents a family of new expansions of Boolean functions called Function-driven Linearly Independent (fLI) expansions. On the basis of this expansion a new kind of a canonical representation of Boolean functions is constructed: Function-driven Linearly Independent Binary Decision Diagrams (fLIBDDs). They generalize both Function-driven Shannon Binary Decision Diagrams (fShBDDs) and Linearly Independent Binary Decision Diagram (LIBDDs). The diagrams introduced in the paper, can provide significantly smaller representations of Boolean functions than standard Ordered Binary Decision Diagrams (OBDDs), Ordered Functional Decision Diagrams (OFDDs) and Ordered (Pseudo-) Kronecker Functional Decision Diagrams (OKFDDs) and can be applied to synthesis of reversible …
Logic Synthesis For Regular Layout Using Satisfiability, Marek Perkowski, Alan Mishchenko
Logic Synthesis For Regular Layout Using Satisfiability, Marek Perkowski, Alan Mishchenko
Electrical and Computer Engineering Faculty Publications and Presentations
In this paper, we propose a regular layout geometry called 3×3 lattice. The main difference of this geometry compared to the known 2×2 regular layout geometry is that it allows the cofactors on a level to propagate to three rather than two nodes on the lower level. This gives additional freedom to synthesize compact functional representations. We propose a SAT-based algorithm, which exploits this freedom to synthesize 3×3 lattice representations of completely specified Boolean functions. The experimental results show that the algorithm generates compact layouts in reasonable time.
Implicit Algorithms For Multi-Valued Input Support Manipulation, Alan Mishchenko, Craig Files, Marek Perkowski, Bernd Steinbach, Christina Dorotska
Implicit Algorithms For Multi-Valued Input Support Manipulation, Alan Mishchenko, Craig Files, Marek Perkowski, Bernd Steinbach, Christina Dorotska
Electrical and Computer Engineering Faculty Publications and Presentations
We present an implicit approach to solve problems arising in decomposition of incompletely specified multi-valued functions and relations. We introduce a new representation based on binaryencoded multi-valued decision diagrams (BEMDDs). This representation shares desirable properties of MDDs, in particular, compactness, and is applicable to weakly-specified relations with a large number of output values. This makes our decomposition approach particularly useful for data mining and machine learning. Using BEMDDs to represent multi-valued relations we have developed two complementary input support minimization algorithms. The first algorithm is efficient when the resulting support contains almost all initial variables; the second is efficient when …
Bi-Decomposition Of Multi-Valued Relations, Alan Mishchenko, Marek Perkowski, Bernd Steinbach
Bi-Decomposition Of Multi-Valued Relations, Alan Mishchenko, Marek Perkowski, Bernd Steinbach
Electrical and Computer Engineering Faculty Publications and Presentations
This presentation discusses an approach to decomposition of multivalued functions and relations into networks of two-input gates implementing multi-valued MIN and MAX operations. The algorithm exploits both the incompleteness of the initial specification and the flexibilities generated in the process of decomposition. Experimental results over a set of multi-valued benchmarks show that this approach outperforms other approaches in the quality of final results and CPU time.