# Reversible Circuit Synthesis Time Reduction Based on Subtree-Circuit Mapping
## 5 Synthesis Time Reduction
### Subtree-Based Mapping Process  
In this section, we illustrate the process of the subtree-based mapping process in detail. Given an OUT file (OUT files are textual representations of the reduced BDDs that originally represent some Boolean functions, taken from the Rivkit project as testing materials for our work), we intended to construct the reduced BDD from its OUT file in order to alter the data structure of the nodes to make them suitable for the subtree-based mapping. During the BDD construction, our algorithm marks the nodes that represent the parents of all composing BDD subtrees (the marking process is simply used to update the node data structure with a suitable hash key, as mentioned above), taking into account the fact that each subtree is composed of at most three nodes (one parent and two children). During this process, our algorithm studies these subtrees, taking into account the possibilities that were previously investigated during the look.up table construction illustrated above. As a result, each parent node of the subtrees of the BDD is given a code similar to that given to the similar subtree (the key) during the construction of the look-up table. A link to each parent node is saved in a special table with its corresponding hash key. The result of this process is a table (parent table) containing links to all possible parents (with their corresponding keys) of all composing subtrees for the given BDD. However, in this work, and because the time consumed in altering the data structure of the parental nodes is beyond the scope of this study since this alteration can be done during the reduction process of BDDs, we intended to execute the alteration process in order to make the BDD structure suitable for our subtree-based mapping process. We therefore obtain a smaller set of nodes (parent table) as in Figure 6, where each node represents its subtree as well as its corresponding hash key; we can search for the keys of all nodes in the look-up table, and for each matched key, the algorithm adds the corresponding cascade of reversible gates and adds them to the generated reversible circuit. Figure 7 below represents the activities related to the subtree-based mapping process. For example, Figure 6 represents the BDD for the Boolean function \(f(x)=x_{1}x_{2}\overline{x_{3}x_{4}}+\overline{x_{1}}x_{2}x_{3}x_{4}+x_{1} \overline{x_{2}}x_{3}\overline{x_{4}}+x_{1}x_{2}\overline{x_{3}x_{4}}\), where the dashed, numbered subtrees represent the sequence of their determination in order to convert them into suitable cascade reversible gates. Figure 8 represents the generated reversible circuit of the BDD, where the numbers 1, 2 and 3 associated with a set of reversible gates correspond to the same numbers representing the subtrees in Figure 6.  
Figure 6: BDD representation of the Boolean function \(f(x)=x_{1}x_{2}\overline{x_{3}x_{4}}+\overline{x_{1}}x_{2}x_{3}x_{4}+x_{1} \overline{x_{2}}x_{3}\overline{x_{4}}+x_{1}x_{2}\overline{x_{3}}\overline{x_{4}}\), where three subtrees are investigated and the construction of their suitable hash keys was performed as long as their parental nodes were identified. Figure 7: Subtree-based realization of reversible circuits. The pseudocode which appears in Listing 2 below illustrates the abstracted process of reversible circuit synthesis operation based on subtree mapping. The code starts by calling the method \(constructParametersTable()\), which takes \(bdd\) as a parameter; using a Depth-First Search method, it visits all BDD nodes, and during the visit, the method decides weather the visited node is a parent for a a subtree or only one of the two children that it might have. The output of this method is the table \(parentsTable\) that contains all subtree parents nodes with their keys. The keys are computed in the same way as that during the construction of the look-up table, taking into account the number of inbound and outbound links. The \(Convert()\) method is then executed, which takes the parents table \(parentsTable\) and \(lookupTable\) as parameters.