# State Merging and Splitting Strategies for Finite State Machines Implemented in FPGA
## 2 Materials and Methods
### General FSM Synthesis Method
```
1:best_FSM \(\leftarrow\) FSM, last_FSM \(\leftarrow\) FSM
2:G \(\leftarrow\)FindMergePairs(FSM)
3:D \(\leftarrow\)FindSplitStates(FSM)
4:Q\({}_{\mathrm{l}}\gets 0.5\)
5:WHILE G \(\
eq\varnothing\) and D \(\
eq\varnothing\)DO
6:Q\({}_{\mathrm{m}}\gets 0\)
7:WHILE G \(\
eq\varnothing\)DO
8:Save(FSM)
9:FSM \(\leftarrow\)Merge(FSM, (a\({}_{\mathrm{s}}\), a\({}_{\mathrm{t}}\)) \(\in\) G)
10:Encode(FSM)
11:IF TransformationRatio(FSM) > Q\({}_{\mathrm{m}}\)THEN
12:Q\({}_{\mathrm{m}}\leftarrow\)TransformationRatio(FSM)
13:Selected_Pair \(\leftarrow\)(a\({}_{\mathrm{s}}\), a\({}_{\mathrm{t}}\))
14:END IF
15:Restore(FSM)
16:END WHILE
17:Q\({}_{\mathrm{s}}\gets 0\)
18:WHILE D \(\
eq\varnothing\)DO
19:Save(FSM)
20:Encode(FSM)
21:FSM \(\leftarrow\)Split(FSM, a\({}_{\mathrm{i}}\) \(\in\) D)
22:IF TransformationRatio(FSM) > Q\({}_{\mathrm{l}}\)THEN
23:Q\({}_{\mathrm{s}}\leftarrow\)TransformationRatio(FSM)
24:Selected_State \(\leftarrow\)(a\({}_{\mathrm{i}}\))
25:END IF
26:Restore(FSM)
27:END WHILE
28:IF\({}_{\mathrm{m}}\) > Q\({}_{\mathrm{s}}\)THEN
29:FSM \(\leftarrow\)Merge(FSM, SelectedPair)
30:Q\({}_{\mathrm{l}}\leftarrow\)Q\({}_{\mathrm{m}}\)
31:ELSE
32:IF Q\({}_{\mathrm{s}}\) > TransformationRatio(Last_FSM)THEN
33:FSM \(\leftarrow\)Split(FSM, Selected_State)
34:Q\({}_{\mathrm{l}}\leftarrow\)Q\({}_{\mathrm{m}}\)
35:Last_FSM \(\leftarrow\)FSM, No_Split \(\leftarrow\)FALSE
36:ELSEAt the start of Algorithm 2, an initial FSM form is stored as the best one (line 1). Next, the subroutines for seeking couples for merging (building the set \(G\)) and states for splitting (building the set \(D\)) are performed (lines 2-3). If merging or splitting the states are impossible, the algorithm goes to the end, otherwise, the trial merging and splitting procedures are executed as follows. At the beginning, the present FSM is stored and next, merging or splitting procedures are executed, then the states are encoded, and the transformation ratio of FSM is determined (lines 7-27). Among all solutions, the one is selected for which the transformation ratio \(Q_{i}=\max(Q_{s},\,Q_{m})\) is maximal, where \(Q_{s}\) and \(Q_{m}\) are the transformation quality ratios for splitting and merging, respectively. Finally, the real merging or splitting procedure is performed, and the subroutine for the selection of states for the next merging or splitting is executed again (lines 40-47). The final FSM form is the one with the highest transformation quality ratio from all considered equivalent forms (lines 40-41). The splitting process may be divergent, like in the previously mentioned strategies. For that reason, the stop condition for splitting should be included. It is made in lines 32-38 of Algorithm 2. After execution of one of the variants of the general algorithm of synthesis, the minimization of the number of FSM transitions and minimization of the number of input variables should be also made, if necessary, as it was explained in [39]. ## 3 Results

The proposed three strategies for synthesis of FSMs were implemented as a part of a system for the optimization of digital systems based on programmable logic devices. To estimate the efficiency of the proposed strategies, we used MCNC FSM benchmarks [41]. Four methods of state assignment were investigated: binary, one-hot, JEDI (default output dominant algorithm) [42] and power optimized sequential encoding [43]. For all three strategies (MS, SM and COMB), three different optimization criterions were used: power consumption, speed of operation and balanced variant with identical weights for power and speed parameters (50%). If we also consider four types of encodings, we have 36 different variants of synthesis method considered in the paper.