Optimal state chains and state codes in finite state machines

A method is presented for the synthesis of optimal regular digital control structures in VLSI circuits. The controllers are modeled as finite-state machines and implemented using counter-based programmable-logic-array structures. Although those structures have already been used in the past, their complete automated design was impossible, due to missing state-assignment algorithms. The state-assignment algorithms presented to 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