Partitioning of Mealy Finite State Machines

As widely accepted, the most popular way for realization of control units are finite state machines. Up-to-date control unit circuits very often are implemented using programmable logic devices. Microprocessors can be also considered as a solution taking costs into account. But very often microprocessors are too slow for realization control units of digital systems. The partitioning of state machines can be a solution for this problem allowing a parallel execution of sub-state machines, keeping performance, cost, and energy consumption at adequate levels. In this case, the time critical part of the control unit (associated with specific sub-state machines) can be implemented in fast FPGA device and other parts can be realized by cheaper platforms (namely based on microprocessors). Additional advantage of such solution is that each part can be synthesized using different methods. The problems and algorithms of partitioning of state machines are discussed in this paper. A CAD tool for partitioning implementing the proposed algorithm is also presented.