Minimization of mealy finite-state machines by using the values of the output variables for state assignment

Abstract

Structural models of finite-state machines (FSMs) that make it possible to use the values of the output variables for encoding the internal states are studied. To minimize the area (the parameter area is used to denote cost in the context of this paper) of FSM implementation, it is proposed to use the structural model of the class D FSM. A method for the design of the class D FSM in FPGA is proposed. This method involves two phases—splitting the internal states of the FSM (to satisfy the necessary conditions for the construction of the class D FSM) and encoding the internal states (to ensure that the codes are mutually orthogonal). It is shown that the proposed method reduces the area of FSM implementation for all families of FPGAs of various manufacturers by a factor of 1.41–1.72 on average and by a factor of two for certain families. Practical issues concerning the method and the specific features of its use are discussed, and possible directions of the elaboration of this approach are proposed.