Optimum and Heuristic Algorithms for Finite State Machine Decomposition and Partitioning.

摘要

Techniques have been proposed in the past for various types of finite state machine (FSM) decomposition that use the number of states or edges in the decomposed circuits as the cost function to be optimized. These measures are not reflective of the true logic complexity of the decomposed circuits. These methods have been mainly heuristic in nature and offer limited guarantees as to the quality of the decomposition. In this paper we present optimum and heuristic algorithms for the general decomposition of 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. 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 show that this is an easier problem than optimum state assignment. A procedure of constrained prime-implicant generation and covering represents an optimum FSM decomposition algorithm, under the specified cost function. Exact procedures are not viable for large problem instances. A novel iterative optimization strategy of symbolic-implicant expansion and reduction, modified from two-level Boolean minimizers, represents a heuristic algorithm based on our exact procedure. Reduction and expansion are performed on functions with symbolic, rather than binary-valued outputs. Preliminary experimental results illustrate both the efficacy of the proposed algorithms and the validity of the selected cost function. (jhd)