# Logic Synthesis Strategy Oriented to Low Power Optimization
## 2 Theoretical Background  
One of the main tasks of logic synthesis geared toward FPGAs is to map the implemented logic structure into FPGA resources. The technology mapping in the case of combinational circuits comes down to the mapping of the implemented function from LUT logical blocks included in the circuit. It turns out that LUT logical blocks are capable of executing any logic function with a limited number of variables. The number of \(k\) inputs of the LUT (number of function variables) is small. Therefore, there is a problem of dividing the implemented circuit. The mathematical model of such a division is the decomposition of a function. The decomposition theorem was formulated by [PERSON] [32] and developed by [PERSON] [33] as early as the 1960s. In the classical approach, simple serial decomposition comes down to splitting all variables into two sets: bound set \(Xb\) and free set \(Xf\). The variables contained in the bound set are variables for the bound functions \(g\)[33], which are implemented in the bound block. On the other hand, the bound functions and the variables from the free set are variables of the free function realized in the free block. From the point of view of efficient partitioning, the key is the number of bound functions \(p\), which corresponds to the number of wires between the bound and free blocks. Let \(f\) be n-input and m-output logic function reflecting \(B^{n}\) set into \(B^{m}\) set i.e., f: \(B^{n}\to B^{m}\), where \(B=\{0,1\}\). Function f: \(B^{n}\to B^{m}\) may be presented as \(Y=f(I_{n-1},\ldots,I_{1},I_{0})\), where \(Y=\{y_{m-1},\ldots,y_{1},y_{0}\}\). Function f: \(B^{n}\to B^{m}\) is subjected to decomposition, i.e.,  
\[f(X_{2},X_{1})=F[g_{1}(X_{b}),g_{2}(X_{b}),\ldots,g_{p}(X_{b}),X_{f}] \tag{1}\]  
if and only if column multiplicity of Karnaugh map \(\
u(X_{f}\Big{|}X_{b})\leq 2^{p}\)[32; 33], where \(X_{b}\cup X_{f}\) = \(\{I_{n-1},\ldots,I_{1},I_{0}\}\) and \(X_{b}\cap X_{f}=\varphi\). Simple serial decomposition leads to the division shown in Figure 1.  
The method of describing a function plays a key role in the decomposition process, which determines the computational complexity of individual operations and memory usage. It turns out that in this respect, the representation of the function in the form of BDD [34; 35; 36] is very effective. Of course, there are many different forms of BDD. In this paper, the authors refer to the reduced and ordered form of BDD (ROBDD) when using the term BDD. The essence of BDD decomposition is to cut the diagram horizontally. This divides the nodes into those above the cut line and the nodes below the cut line. The variables associated with the top of the diagram belong to the bound set \(X_{b}\). On the other hand, the variables associated with the bottom of the diagram belong to the free set \(X_{f}\). In the case of BDD, column multiplicity corresponds to the number of cut nodes. Cut nodes are the nodes at the bottom of the diagram (below the cut line) to which the edges above the cut line are drawn. The essence of the implementation of decomposition with the use of BDD is shown in Figure 2.  
Figure 1: The essence of simple serial decomposition. There are also some modifications to the presented method. As shown in the works [37; 38], the decomposition can also be realized by introducing several cut lines for one BDD. Simple serial decomposition is the basis for more complex decomposition models, such as multiple or iterative decomposition, which can also be realized with the use of BDD [39; 40]. In order to obtain efficient decomposition, the aim is to limit the number of bound functions, which allows the complexity of the bound block to be reduced. It is, therefore, necessary to limit the number of cut nodes. It turns out that the number of cut nodes depends on two factors: the level of BDD cut and the order of variables in the diagram. The cut level determines the cardinality of the bound set \(card(X_{b})\). This value corresponds to the number of inputs in LUT block (\(k\)).