Improved ordering of ESOP cubes for Toffoli networks
Loading...
Files
Date
2011
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of New Brunswick
Abstract
Logic synthesis deals with the problem of finding a cost-effective realization of a given logic function. This uses several state-of-the-art techniques and involves several tools of mathematical origin. In recent years reversible logic has been suggested to address the power consumption associated with computation. To accomplish such a task, synthesis of reversible logic function is needed. Several new synthesis methods have been developed. In this thesis methods are proposed that improve on a given synthesis method. In particular, interest has been demonstrated in the optimization of this class of circuits which use the particular Exclusive-or Sum of Product (ESOP) terms representation. The advantage this representation format offers is in the ease of mapping the function to a network of Toffoli logic gates. However, this synthesis technique provides non-optimal results which could be improved. This problem has roots in both the representation and mapping processes of synthesis. It is well-known that the order of the terms in the ESOP expression will have a direct effect on the cost of the implementation. The problem of finding the optimal order can be mapped into the Generalized Traveling Salesman Problem. Another route of optimization involves reducing the number of terms used to represent the function. This can be achieved by canonical representation of functions. Both of these have proven to offer enhancements over existing synthesis techniques and have been developed in this thesis. Experimental results show that significant improvements can be achieved with the proposed methods.