# State Merging and Splitting Strategies for Finite State Machines Implemented in FPGA
## 1 Introduction
In [14], a modification of the feedback of asynchronous FSMs and convergent state encoding is proposed. In this approach, asynchronous FSMs can be realized as simply as synchronous ones. Ref. [15] presents the extended burst-mode architecture, based on local synchronization signals, which allows using approaches for synchronous machines, for the synthesis of asynchronous machines. The increase in speed of FSM can be achieved also by using a state splitting procedure. Ref. [16] presents the method based on the splitting of internal states, which makes it possible to decrease the ranks of transition functions and decrease the number of logic levels of transition functions. Many approaches to the power consumption reduction of state machines have been recently proposed. They are mostly based on special state encoding procedures, decomposition, device clocking control and others. In Ref. [17] a genetic fuzzy c-mean clustering-based decomposition method, named GFCM-D, is offered for FSM partition into a set of c-fuzzy clusters. For reaching low power consumption, the target function of GFCM-D is minimized with the application of a genetic algorithm. A partitioning is widely used for FSM power minimization because most of time, only one of sub-FSMs should be clocked; in consequence, the energy is saved. Ref. [18] proposes a multi-population evolution strategy, denoted as MPES to accomplish the task of searching for a low power state encoding in FSM synthesis. MPES resolves this problem by using inner and outer evolution strategies (ES). In the inner strategy, subpopulations evolve independently and are responsible for local search in separate regions, while the outer strategy plays the role of a shell to optimize the subpopulations of inner-ES for improved solutions. Ref. [19] proposes a fast algorithm based on state transitions probability and simple control logic to realize the partitioned machines. An effective method for decreased dynamic power by reducing the switching activity is clock gating. Ref. [20] presents a consolidated and close-grained architecture-level clock gating mechanism for low-power hardware accelerators which are automatically created by a high-level synthesis tool. Another method includes the conception of clock gating into both the state logic (DGS) and output logic (DGO) in FSM individually and can be applied in most cases in any FSM [21]. The gating control logic automatically extracts information from the FSM state description. The desired adjacency graph to reduce the power dissipation is used in the method from [22]. A low-power state-encoding technique with upper bound peak current constraints is proposed in [23]. Ref. [24] presents a synthesis methodology dedicated to low power implementations of combinatorial circuits in FPGA devices. In this method, Boolean functions are defined by BDD (binary decision diagram). A brand-new structure of the switch activity BDD is suggested, which uses a function decomposition to minimize the switching activity of the logic. The algorithm of state encoding based on a decomposition and probabilistic description of the FSM is proposed in [25]. In this method, a binary tree with nodes created by sharing a finite state machine is used. In several papers, the area is reduced concurrently with the minimization of the power dissipation in the phase of state encoding. Most works [26; 27; 28; 29] propose genetic algorithms for this purpose. A new methodology of logic decomposition with application of BDDs is offered in [30]. The core of the proposed algorithm is the multiple cutting of a BDD. Additionally, methods of searching for the finest technology mapping focused on the configurability of FPGA logic blocks are described. Refs. [31; 32] propose a novel technology-dependent design method which produces FSMs with three levels of logic blocks and regular systems of connections between the logic levels. The algorithm is based on splitting the set of internal states into two subsets. Each subset relates to a unique fragment of an FSM.