Authors: Stojković, Suzana
Stanković, Radomir 
Moraga, Claudio
Stanković, Milena
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Reversible Circuits Synthesis from Functional Decision Diagrams by using Node Dependency Matrices
Journal: Journal of Circuits, Systems and Computers
Volume: 29
Issue: 5
First page: 2050079
Issue Date: 1-Apr-2020
Rank: M23
ISSN: 0218-1266
DOI: 10.1142/S0218126620500796
Decision diagrams are a data structure suitable for reversible circuit synthesis. Functional decision diagrams (FDDs) are particularly convenient in synthesis with Toffoli gates, since the functional expressions for decomposition rules used in them are similar to the functional expressions of Toffoli gates. The main drawback of reversible circuit synthesis based on decision diagrams is the usually large number of ancilla lines. This paper presents two methods for the reduction of the number of ancilla lines in reversible circuits derived from FDDs by selecting the order of implementation of nodes. In the first method, nodes are implemented by levels, starting from the bottom level to the top. The method uses appropriately defined level dependency matrices for choosing the optimal order of implementation of nodes at the same level. In this way, the optimization is performed level by level. The second method uses a diagram dependency matrix expressing mutual dependencies among all the nodes in the diagram. This method is computationally more demanding than the first method, but the reductions of both the number of lines and the Quantum cost of the circuits are larger.
Keywords: Decision diagrams | dependency matrices | functional decision diagrams | nodes dependency | reversible circuits | reversible synthesis
Publisher: World Scientific

Show full item record


checked on May 20, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.