Marek Perkowski

Date of Award

Spring 5-29-2015

Document Type


Degree Name

Doctor of Philosophy (Ph.D.) in Electrical and Computer Engineering


Electrical and Computer Engineering

Physical Description

1 online resource (viii, 120 pages)


Logic circuits -- Design and construction, Reversible computing, Quantum computers




Power dissipation in modern technologies is an important matter and overheating is a severe concern for both manufacturer (impossibility of introducing new and smaller scale technologies and limited temperature range for operating the product) and customer (power supply, which is especially important for mobile systems). One of the main profits that reversible circuit carries is theoretically the zero power dissipation in the sense that it is independent of underlying technology; irreversibility means heat generation. In the other words, reversible circuits may offer a feasible solution in the future that will aid certain reduction of the power loss.

Reversible circuits are circuits that do not lose information during computation. These circuits can create unique output vector from each input vector, and vice versa, that is, there is a one-to-one mapping between the input and the output vectors. Historically, the reversible circuits have been inspired by theoretical research in low power electronics as well as practical progress of bit-manipulation transforms in cryptography and computer graphics. Interest in reversible circuit is also sparked by its applications in several up-to-date technologies, such as Nanotechnology, Quantum Computing, Optical Computing, Quantum Dot Cellular Automata, and Low Power Adiabatic CMOS. However, the most important application of reversible circuits is in Quantum Computing.

Logic synthesis methodologies for reversible circuits are very different from those for classical CMOS and other technologies. The dissertation introduces a new concept of reversible logic circuits synthesis based on EXOR-sum of Products-of-EXOR-sums (EPOE). The motivation for this work is to reduce the number of the multiple-controlled Toffoli gates as well as the numbers of their inputs. To achieve these reductions the research generalizes from the existing 2-level AND-EXOR structures (ESOP) commonly used in reversible logic to a mixture of 3-level EXOR-AND-EXOR structures and ESOPs. The approaches can be applied to reversible and permutative quantum circuits to synthesize both completely and incompletely specified single-output functions as well as multiple-output functions.

This dissertation describes the research intended to examine the methods to synthesize reversible circuits based on this new concept. The examinations indicate that the synthesis of reversible logic circuits based on EPOE approach produces circuits with significantly lower quantum costs than the common ESOP approach.

Persistent Identifier