State minimization of finite state machines using implicit techniques
Timothy Kam · 1996
State minimization is an important step in sequential synthesis of VLSI circuits. This dissertation addresses state minimization problems of various classes of finite state machines (FSM's). An exact algorithm usually consists of generation of compatibles and solution of a binate covering problem. State-of-the-art explicit minimizers fail on FSM's requiring an exponential number of compatibles, or huge binate tables. Such difficult examples do arise in practice. This dissertation first contributes a fully implicit algorithm for exact state minimization of incompletely specified FSM's, and a software implementation called ISM. Novel techniques are developed to represent and generate various subsets of compatibles implicitly. scISM can handle sets of compatibles and prime compatibles of cardinality up to 2$\sp{1500}.$ The dissertation also presents the first published algorithm for fully implicit exact binate covering. scISM can reduce and solve binate tables with up to 10$\sp6$ rows and columns. The entire branch-and-bound procedure is carried out implicitly. To handle a more general and more useful class of FSM's, the first implicit algorithm for exact state minimization of pseudo non-deterministic FSM's is presented. Its implementation scISM2 is shown experimentally to be superior to a previous explicit formulation. scISM2 could solve exactly all but one problem of a set of published benchmarks, while the explicit program could complete approximately one half of the examples, and in those cases with longer running times. A theoretical solution is presented for the problem of exact state minimization of general non-deterministic FSM's, based on the proposal of generalized compatibles. This gives an algorithmic foundation for exploring behaviors contained in an NDFSM. Recent research in sequential synthesis, verification and supervisory control relies, as a final step, on the selection of an optimum behavior to be implemented at a component FSM within a network of FSM's. This dissertation contributes an exact condition characterizing when an FSM-composition is well-defined. Exact and heuristic algorithms are proposed to find a minimum behavior contained in a PNDFSM (capturing all permissible behaviors) such that it is Moore or its composition with another DFSM (representing the environment) is well-defined, and the global behavior meets a specification.