# 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:S\({}_{i}\leftarrow\) MAX_P_VALUE
3:G \(\leftarrow\) FindMergePairs(FSM)
4:WHILE G \(\
eq\) OD
5:S\({}_{m}\leftarrow\) MAX_S_VALUE
6:WHILE G \(\
eq\) OD
7:Save(FSM)
8:FSM \(\leftarrow\) Merge(FSM, (a\({}_{s}\), a\({}_{t}\)) \(\in\) G)
9:Encode(FSM)
10:IF CriticalPath(FSM) \(<\) S\({}_{m}\)THEN
11:S\({}_{m}\leftarrow\) CriticalPath(FSM)
12:Selected_Pair \(\leftarrow\) (a\({}_{s}\), a\({}_{t}\))
13:END IF
14:Restore(FSM)
15:END Whille
16:FSM \(\leftarrow\) Merge(FSM, Selected_Pair)
17:Last_FSM \(\leftarrow\) FSM
18:IF S\({}_{m}\) < CriticalPath(best_FSM)THEN
19:best_FSM \(\leftarrow\) FSM, S\({}_{i}\) \(\leftarrow\) S\({}_{m}\)
20:END IF
21:G \(\leftarrow\) FindMergePairs(FSM)
22:END Whille
23:D \(\leftarrow\) FindSplitStates(FSM)
24:WHILE D \(\
eq\) OD DO
25:WHILE D \(\
eq\) OD DO
26:Save(FSM)
27:Encode(FSM)
28:FSM \(\leftarrow\) Split(FSM, a\({}_{t}\)\(\in\) D)
29:IF CriticalPath(FSM) \(<\) S\({}_{t}\)THEN
30:S\({}_{s}\) \(\leftarrow\) CriticalPath(FSM)
31:Selected_State \(\leftarrow\) (a\({}_{t}\))
32:END IF
33:Restore(FSM)
34:END Whille
35:IF S\({}_{s}\) < CriticalPath(Last_FSM)THEN
36:FSM \(\leftarrow\) Split(FSM, Selected_State)
37:Last_FSM \(\leftarrow\) FSM, No_Split \(\leftarrow\) FALSE
38:ELSE
39:No_Split \(\leftarrow\) TRUE
40:END IF
41:IF P\({}_{s}\) < CriticalPath(best_FSM)THEN
42:best_FSM \(\leftarrow\) FSM, S\({}_{t}\) \(\leftarrow\) S\({}_{s}\)
43:END IF
44:IF No_Split = FALSETHEN
45:D \(\leftarrow\) FindSplitStates(FSM)
46:ELSE
47:D \(\leftarrow\) OD
48:END IF
49:END Whille
50:END
```  
**Algorithm 1** General algorithm for FSM synthesis (power-aware merge-then-split strategy). After the merging phase, the subroutine for seeking states for splitting (building the set \(D\)) is performed (line 23). If there is no possibility to split any states, the algorithm stops, otherwise, the trial splitting is executed as follows. First, the present FSM is saved, splitting is executed, then the states are encoded, and the critical path ratio of FSM is determined (lines 25-34). Among all solutions, the one is selected for which the critical path ratio \(S_{i}\) is minimal. Then the real splitting is performed, and a selection of states for the next splitting is executed once more (lines 35-48). The final FSM form is the one with the lowest critical path ratio from all considered equivalent forms during the work of the algorithm. The splitting process may be divergent, and therefore the stop condition for splitting is included in the algorithm. It is made in lines 35-40 of Algorithm 1, where the critical path ratio \(S_{s}\) of the splitting FSM at this time is compared to the identical value determined for the last completed splitting. If the splitting does not lead to a further decrease in the critical path, it should not be executed. In the split-then-merge (SM) strategy, there is always a splitting performed first, and after all possible splits, the merging of states should be done. The algorithm for this strategy can be obtained from Algorithm 1. The only operation which should be performed is to replace lines 3-22 with lines 23-49 in Algorithm 1. In the combined strategy (COMB), at each step, the trial merging and trial splitting is performed. Then, the decision of which transformation (splitting or merging) finally should be performed (depending on selected criteria) is made. The combined strategy with the consideration of the balanced variant of optimization is described in the form of Algorithm 2.