## 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 main aim of the logic function decomposition is to reduce the number of LUT blocks of the destination device. Realization of the system within an FPGA imposes a limit on the number of variables of a single function. Therefore, if a function contains more variables than the number of inputs of the LUT block, it ought to be decomposed to make the implementation possible. In general, the essence of the decomposition refers to the proper division of the system into blocks with a given number of inputs. The function of \(n\)-variables \(f(X)\), \(X=x_{1},x_{2},\ldots,x_{n}\) can be represented as \(h\Big{(}g_{1}(X_{b}),\ldots,\ g_{m}(X_{b}),\ X_{f}\Big{)}\), where \(X_{b}\) is the bound set and \(X_{f}\) is a free set (\(X=X_{b}\cup X_{f}\)), when the number of column patterns of the partition matrix is less than or equal to \(2^{m}\)[52]. The division of variables involves searching for the sets \(X_{b}\) and \(X_{f}\). If the common part of the sets \(X_{b}\) and \(X_{f}\) is empty, we say that the decomposition is disjoint. Splitting the variables into two subsets is equivalent to making a cut in a binary decision diagram. The nodes above the cut line form a bound set, and those below are a free set. The nodes below the cut line that are pointed by the cut edges are called cutnodes. The number of cut nodes corresponds to the number of column patterns in the Ashenhurst-Curtis decomposition or the number of equivalence classes in the Roth-Karp decomposition [52]. In the general case, for \(n\) cut nodes, \(\log_{2}(n)\) bits are needed to distinguish them. Several functions \(g_{i}\) are then created, \(i=1,\ldots,\log_{2}(n)\). The number of cut nodes depends on the choice of variables that create the free and bound set, i.e., on the order of variables in the graph and on the level at which the cut will take place. When looking for a decomposition allowing the implementation of the circuit using \(k\)-input LUT blocks, the cutting level is usually set to \(k\), counting from the root of the diagram. Let us explain the decomposition by an example. Assume a function of four variables \(f(x_{1},x_{2},x_{3},x_{4})\) to be realized within a LUT3 block (\(k=3\)). Since the number of variables (four) exceeds the number of available inputs of the LUT (three), the function ought to be decomposed. Figure 5 illustrates the decomposition process. Firstly, the BDD is cut off below the third level of nodes counting from the root (Figure 5a). The bound set is formed by variables \(\{x_{1},\ x_{2},\ x_{3}\}\), and free set by \(\{x_{4}\}\). There are four cut nodes **a**, **b**, **c**, and **d**. To encode four patterns, \(\log_{2}(4)=2\) bits are required (two \(g\) functions: \(g_{1}\) and \(g_{2}\)). The encoding of cut nodes by \(g_{1},g_{2}\) functions is shown in Figure 5b, \(g_{1},g_{2}=0\)-**a**, 01-**b**, 10-**c**, 11-**d**, which means that two new functions \(g_{i}(x_{1},x_{2},x_{3})\) are created. Replacing the upper part of the BDD for function \(f\) (variables marked in green in Figure 5a) with newly created \(g_{i}\) functions gives diagram \(h(x_{4},g_{1},g_{2})\), which is presented in Figure 5c (\(h\) is functionally equivalent to \(f\)). Furthermore, the \(g_{i}\) functions define the bound block of the partitioned circuit (Figure 5d), and the free block is defined by \(h\). The number of inputs of both obtained blocks does not exceed three; thus, the system can be implemented within a three-input LUT block. This means that the aim of the decomposition has been achieved. The above example shows the general idea of the decomposition technique applied in this work. However, in practice, the number of variables very often significantly exceeds the number of LUT inputs. In such a case, the decomposition steps are iteratively repeated. Figure 6 illustrates such a situation. There are six arguments in the initial function that are going to be realized with three-input LUTs.