# State Merging and Splitting Strategies for Finite State Machines Implemented in FPGA
## 1 Introduction  
A digital system can be described as a collection of finite state machines (FSM) and combinational circuits. FSMs are often used as independent modules as control devices. Usually, the original machines must be created by the engineer any time when he wants to create a new project. The success of the entire project is largely determined by the parameters of the FSMs built in the digital circuit. Therefore, the questions of finding the optimal representation of a finite state machine are always topical. Currently, field-programmable gate arrays (FPGA) are commonly applied for building digital systems. A substantial number of optimization algorithms for finite state machines are focused on their implementation in FPGA. The criteria for optimizing FSMs are generally the area (cost of implementation), speed (critical delay path) and power consumption (dissipation). The area criterion is not a critical restriction because new FPGAs have a great number of logical elements built from look-up tables (LUT). Recently, the most significant optimization criteria are critical path delay and energy consumption. The traditional process of the synthesis of finite state machines contains the following phases, which are sequentially executed: a minimization of the number of states (state merging), an encoding of states (state assignment) and a synthesis of the combinational part of finite state machine. Nevertheless, traditional methods frequently contradict the FSM optimization target at the stage of logic synthesis because all of the above-mentioned design phases totally ignore the characteristics of the technological base and the constraints of the logic synthesis process. A classic attempt to solution of the problem of machine state merging relies on a creation of sets of matching states and searching for a minimal closed cover, which is an NP-complete problem [1]. Ref. [2] describes an exact minimization method based on the mapping of incompletely specified FSMs to a FSMs tree. In [3], a branch-and-bound search algorithm for the determination of sets of matching states is presented. One of the mostknown solutions is the STAMINA program [4], which can work in heuristic and exact variants and applies explicit enumeration to the solution of the state minimization task. The other implementation of merging procedure is presented in Ref. [5], which describes a program for parallel state reduction and state encoding, where incompletely specified state codes can be built. The value of splitting the states of FSMs in state encoding procedure was declared in [6] and soon after in [7], where the splitting operation was used to decrease the power dissipation and resource utilization of the designed FSM. Ref. [8] describes an application of state splitting for the simultaneous state minimization and the state assignment of the FSM. Many authors have pondered the synthesis methods for high-speed FSMs implemented on programmable logic devices with a large variety of approaches. Ref. [9] considers the problem of state encoding and optimization of the combinational part upon the implementation of high-performance FSMs in complex programmable logic devices (CPLD). Ref. [10] presents a novel architecture that is particularly optimized for implementation of reconfigurable FSMs; this architecture is called the transition-based reconfigurable FSM (TR-FSM) and shows a significant reduction in area, speed, and power consumption in relation to FPGA architectures. In [11], the implementation of finite state machines in FPGA with the application of integral blocks of read-only memory (ROM) is described. The presented approach shows two pieces of FSMs structure with multiplexers on inputs of ROM blocks, which allow decreasing the area and increasing the FSM speed. Ref. [12] presents BT-FSM, which is a finite state machine with a single bit input, where the state transition graph is in a form of a binary tree. The architecture of FSM is based on the previously developed model of the finite virtual state machine (FSVM) [13].