## 1 Introduction and Problem Formulation
### Optimization of the Verilog HDL Code of the Concurrent Control System
#### 2.3.2 Optimization of the Combinational Part of the System (Decomposition of Logic Functions)
The first step of the decomposition is similar to the previous example. The diagram of function \(f\) is cut off below the third level of nodes, as shown by green dashed line in Figure 6a. Figure 5: Simple decomposition process with BDD: (**a**) cutting of diagram \(f\), (**b**) upper part replaced with \(g\) functions, (**c**) encoding of functions \(g\), (**d**) schema of the final decomposition. Four cut nodes **a**, **b**, **c**, and **d** are encoded with two functions \(g_{1},g_{2}\). The upper part of the diagram with variables \(\left\{x_{1},\ x_{2},\ x_{3}\right\}\) is replaced with nodes associated with \(g_{1},g_{2}\), and it forms a new diagram \(h_{1}(g_{1},g_{2},x_{4},x_{5},x_{6})\) (Figure 6c). The \(h_{1}\) function still has too many variables to implement with LUT3 blocks; thus, another round of decomposition is performed. This time, the diagram is cut below nodes associated with \(x_{4}\) (Figure 6c). Below the magenta dashed line, there are only two cut nodes **a** and **c**, and just a single \(g_{3}\) function is necessary to distinguish them (Figure 6d). By replacing the upper part of diagram \(h_{1}\) (variables \(\left\{g_{1},\ g_{2},\ x_{4}\right\}\)) with \(g_{3}\) once more, the \(h_{2}\) diagram is obtained (Figure 6e). The resulted decomposition is suitable for hardware implementation with LUT3 blocks. The partitioned system is presented in Figure 6f. Another important task that involves the functional decomposition is related to the multi-output functions that are more commonly used instead of single functions. In order to perform the optimization, the synthesis tools try to optimize the number of LUT blocks by sharing resources between functions. The essence of the problem is to find bound functions \(g\) which, by assigning the appropriate codes, are used in several functions of the entire group. The idea of sharing bound functions is explained by an example shown in Figure 7. It is assumed that multi-output function \(f_{1}f_{2}\) is going to be implemented within LUT3 blocks. The cutting line of the diagrams is drawn below the third level of the nodes. In the case of a separate implementation of both functions, four LUT3 blocks are required (Figure 7a,b). Another possibility is merging \(f_{1}\) and \(f_{2}\) diagrams into the single multiterminal diagram, allowing for a common bound block (Figure 7c). There are six cut nodes (**1**, \(\ldots\), **6**), and thus \(\log_{2}(6)=3\) functions \(g_{1},g_{2},g_{3}\) are required to encode the patterns. Before the decomposition, each of the functions \(f_{1}\) and \(f_{2}\) consist of four arguments. After the decomposition, the free blocks still include four variables \((g_{1},g_{2},g_{3},x_{4})\) (Figure 7c). This means that in such a case, the decomposition is useless, since no reduction in the number of inputs is achieved. Figure 6: Iterative decomposition with BDD: (**a**) cutting of diagram \(f\), (**b**) encoding of \(g_{1}\) and \(g_{2}\), (**c**) replacement of the upper part with \(g_{1}\) and \(g_{2}\) functions, (**d**) encoding of \(g_{3}\), (**e**) replacement of the upper part with \(g_{3}\) function, (**f**) schema of the final decomposition. The above example clearly shows that the sharing of all bound functions is not always effective. Indeed, the crucial aspect refers to the determination of if an effective bound function common to \(f_{1}\) and \(f_{2}\) could be found. Figure 6d shows a table of cut nodes and paths leading from the root node to the cut nodes. Note that node **c** can be reached from the root \(f_{1}\), traversing the path \(x_{1}x_{2}x_{3}\) = 000 or 100 (Figure 7a) as indicated in columns 000 and 100 in the node table. Based on the node table, a graph of compliance is created, as shown in Figure 7e. Individual nodes are associated with paths of bound variables (columns of the node table). If the nodes of the graph (or columns of the table) are assigned with the same symbol (e.g., **c** for 000 and 100), then they are connected by an edge (e.g., red edge for **c**).