Replacing State Variables for Moore FSMs with Twofold State Assignment

Authors:
Open Access
Publisher website
Google Scholar
Abstract
In this paper, a new method of structural decomposition is proposed. The method focuses on FPGA-based Moore finite state machines (FSMs). The method makes it possible to improve both spatial and temporal characteristics of the FSM circuits. Each internal state is represented by two codes. One of them is a partial state code representing a state as an element of some class of compatibility. The second code is represented by a concatenation of two codes: a code of output collection and a code of identifier. The method can be applied if FSM circuits are implemented using look-up table (LUT) elements of field-programmable gate arrays. The resulting FSM circuit includes three logic blocks. The first block generates partial Boolean functions representing partial output collections and identifiers. These functions depend on partial state codes. The partial codes are assigned in a way minimizing the number of arguments in partial functions. This allows generating all partial functions by single-LUT circuits. The second block generates codes of output collections and identifiers. The third block transforms them into FSM outputs and partial state codes. The paper includes an example of FSM synthesis by applying the proposed method. The experiments are conducted using standard benchmark FSMs. The experiments show that the proposed approach can be used for complex FSMs where the total number of FSM inputs and state variables are at least twice the number of inputs of the base LUT. The results of experiments show that the proposed method allows improving both the spatial and temporal characteristics for complex FSMs compared with their counterparts based on methods used by the Vivado tool.