# Reversible Circuit Synthesis Time Reduction Based on Subtree-Circuit Mapping
## 4 BDD-Based Synthesis of Reversible Circuits  
Designing reliable and dependable systems that consume minimal amounts of power and energy is considered to be an important challenge to tackle now and in the near future. This can be done by arranging the reversible logical gates in a way that causes the synthesized circuit to transmit signals with high integrity. A set of heuristics for a smart method of reversible logic synthesis has to be met in the process of synthesizing reversible circuits. The following considerations are examples of those that have to be considered by the synthesizing algorithms: (1) the minimization of the output gates or subgates as far as possible; (2) the reuse of these outputs as inputs to other gates; (3) the minimization of garbage signals; (4) the minimization of constants at the inputs of the gates; (5) the creation of an acyclic resulting circuit; and (6) the algorithm must be circuit size-independent and be possible to apply generally [22]. Since fan-out is not permitted, a reversible logic circuit can realize the inverse specification simply by applying the gates in the reverse order. Thus, synthesis can be carried out from the inputs toward the outputs or from the outputs toward the inputs. The literature provides us with a large number of technologies which have been used to synthesize reversible circuits, where both circuit size and synthesis time are of a great consideration. Some of these methods depend on the truth table of a given function as the origin of the synthesis process, while others start from BDD: composition methods, decomposition methods, EXOR logic based methods, genetic algorithms, search methods, group-theoretic methods, the synthesis of regular structures such as nets, lattices, and RPGAs, spectral techniques, exhaustive search and Binary Decision Diagram (BDD)-based methods in which a Boolean function can be represented by BDD [23]. A Binary Decision Diagram (BDD) is a data structure that is used to represent a Boolean function (following Shannon decomposition). It is a directed acyclic graph \(G(V,E)\) with a set of nodes where a given node \(v\in V\) is either a leaf (with values 0 or 1) or a non-terminal node. The latter node is labeled with one of the input variables of the Boolean function, where Shannon decomposition is applied following Equation (1), where \(x_{i}\) and \(\bar{x_{i}}\) represent a Boolean variable and its complement, respectively. \(f\) represents the Boolean function (represented by BDD), \(f_{x_{i}}\) represents the value of the function \(f\) when \(x_{i}=1\) and \(f_{x_{i}}\) represents the value of the function \(f\) when \(x_{i}=0\)[24]. \[f=\bar{x_{i}}f_{x_{i}}+x_{i}f_{x_{i}} \tag{1}\]  
As an example, Figure 3 illustrates the BDD for the Boolean function \(f(x_{1},x_{2},x_{3})=x_{1}\oplus x_{2}\cdot x_{3}\), where the symbol \(\oplus\) reflects the XOR bitwise operation. However, each path in the BDD starting from the root node until some leaf represents one of the rows in the truth table of the given function represented by the BDD. For example, if we traverse the leftmost path in the graph, we see that the output of the input vector 110 equals 1 where the input vector is \(x_{1}x_{2}x_{3}\). The size of a BDD is related to the number of the internal nodes it contains (the non-terminal ones). For example, the size of the BDD shown in Figure 3 equals 5. However, in order to reduce the size of the BDD, some reduction rules can be applied without altering its fidelity in representing the required Boolean function. Such rules include shared nodes, complemented edges and BDD node reordering. Notice that BDD reordering should be accompanied by reduction rules to effectively reduce its size. Therefore, both exact and heuristic approaches have been proposed to find the optimal or near-optimal order of the variables in the BDD [26].