Improved ordering of ESOP cubes for Toffoli networks

dc.contributor.advisorDueck, Gerhard
dc.contributor.authorHamza, Zakaria
dc.description.abstractLogic 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.
dc.description.copyright© Zakaria Hamza, 2011
dc.description.note(UNB thesis number) Thesis 8777. (OCoLC)810261535.
dc.description.noteM.C.S. University of New Brunswick, Faculty of Computer Science, 2011
dc.format.extentvi, 95 pages : illustrations
dc.identifier.otherThesis 8777
dc.publisherUniversity of New Brunswick
dc.subject.disciplineComputer Science
dc.subject.lcshElectric circuit analysis.
dc.subject.lcshQuantum logic.
dc.subject.lcshLogic circuits.
dc.subject.lcshGate array circuits -- Design.
dc.subject.lcshLogic design -- Data processing.
dc.subject.lcshCombinatorial optimization -- Data processing.
dc.subject.lcshTraveling salesman problem.
dc.subject.lcshComputer algorithms.
dc.titleImproved ordering of ESOP cubes for Toffoli networks
dc.typemaster thesis Science of Computer Science of Computer Science of New Brunswick


Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
1.06 MB
Adobe Portable Document Format