KISS: A PROGRAM FOR OPTIMAL STATE ASSIGNMENT OF FINITE STATE MACHINES.

Abstract

The authors address the state assignment problem for deterministic synchronous finite-state machines implemented by programmable logic arrays and feedback registers. Optimal state assignment aims at a minimal-area implementation. They present an innovative strategy: logic minimization of the combinational component of the finite-state machine is applied before state encoding. Logic minimization is performed on a symbolic (code-independent) description of the finite-state machine. The minimal symbolic representation defines the constraints of a new encoding problem, whose solutions are the state encodings that allow to implement the PLA with at most as many product-terms as the cardinality of the minimal symbolic representation. In this class, an optimal encoding is one of minimal length. A heuristic algorithm is used to construct a solution of the constrained encoding problem. The algorithm has been coded in the computer program KISS, and tested on various examples of finite-state machines. Experimental results are reported.