A GENERALIZED MODEL FOR MEMORY BASED FINITE STATE MACHINES (DIGITAL SYSTEMS, AUTOMATA, DECOMPOSITION, ARCHITECTURE)

A general model for memory based and PLA based finite state machine architectures is introduced, the 2('k)-Decision machine (2('k)-D). The classical (2('n)-D) and binary decision (2-D) architectures are shown to be special cases of the 2('k)-D architecture. The equivalence among the 2('k)-D solutions for different values of k follows from the sequentialization principle, which is stated in the thesis. A cost measure is defined in terms of the area or real estate required by the implementations in a LSI and VLSI context, and a procedure to determine the 2('k)-D memory based architecture which offers minimum cost, given that the speed of operation is 1 state transition per clock cycle, is presented. It is shown that this architecture is not in general the minimum cost solution when the speed of the circuit is not a critical design factor. Also discussed are the optimization problems to be solved when a minimum cost 2('k)-D architecture is desired. In addition, bounds on the cost of the 2('k)-D architecture are calculated in terms of simple measures taken from the mathematical model describing the behavior of the state machine. The results of this research are particularly attractive when LSI and VLSI technologies are considered. State machines constitute fundamental building blocks in systems to be fabricated as integrated circuits. Memory based implementations offer a short design time, regularity of structure, and expandability. PLA based implementations offer cost optimization at expense of greater design time and less flexibility. This research also introduces the local coding architecture, a novel machine decomposition that offers cost efficient solutions for a class of state machines.