Graphical Method of Reversible Circuits Synthesis

Abstract

This paper presents a new approach to designing reversible circuits. Reversible circuits can decrease energy dissipation theoretically to zero. This feature is a base to build quantum computers. The main problem of reversible logic is designing optimal reversible circuits i.e. circuits with minimal gates number implementing the given reversible function. There are many types of reversible gates. Most popular library is a set of three types of gates so called CNT (Control, NOT and Toffoli). The method presented in this paper is based only on the Toffoli gates. A graphical representation of the reversible function called s-maps is introduced in the paper. This representation allows to find optimal reversible circuits. The paper is organized as follows. Section 1 recalls basic concepts of reversible logic. In Section 2 a graphical representation of the reversible functions is presented. Section 3 describes the algorithm whereby all optimal solutions of the given function could be obtained.