Optimal State Chains and State Codes in Finite State Machines

Abstract

This paper presents a method for the synthesis of optimal regular digital control structures in VLSI circuits. The controllers are modeled as finite state machines (FSM-s) and implemented using counter-based PLA structures. Although those structures have already been used in the past, their complete automated design was impossible, due to missing state assignment algorithms. The presented state assignment algorithms that close this gap optimize the required silicon area of the controllers. They are divided into two steps: state chain calculation and state chain coding. In state chain calculation the internal states of a finite state machine are ordered to maximally exploit the counter characteristics. In state chain coding the internal states are coded so that the state sequences are maintained, while coding constraints are satisfied that permit a further minimization of the circuit. First algorithms for the state chain calculation and coding are described. Then results are presented, that were obtained with SUCIM, the implementation of the algorithms. Finally it is shown that the new state assignment algorithms yield significantly smaller areas than conventional solutions. © 1989 IEEE