Optimum and heuristic algorithms for an approach to finite state machine decomposition

摘要

Optimum and heuristic algorithms for the general decomposition of finite state machines (FSMs) such that the sum total of the number of product terms in the one-hot-coded and logic-minimized submachines is minimum or minimal are presented. This cost function is much more reflective of the area of an optimally state-assigned and minimized submachine than the number of states/edges in the submachine. The problem of optimum two-way FSM decomposition is formulated as one of symbolic output partitioning, and it is shown that this is an easier problem than optimum state assignment. A procedure of constrained prime implicant generation and covering that represents an optimum FSM decomposition algorithm, under the specified cost function, is described. It is shown that by means of this formulation, arbitrary decomposition topologies can be targeted by suitably modifying the constraints on the ability to encode during the covering. A novel iterative optimization strategy of symbolic implicant expansion and reduction, modified from two-level Boolean minimizers, that represents a heuristic algorithm based on the exact procedure is presented. Reduction and expansion are performed on functions with symbolic rather than binary-valued outputs. Preliminary experimental results that illustrate both the efficacy of the proposed algorithms and the validity of the selected cost function are presented.