When the machine is already available as a table or a set of 4-tuples (3-tuples for Moore machines), the systems apply one of two approaches, a simple one or the advanced one.
In most of the current systems this conversion is done in a straightforward - primitive method. Widely available and used is the program Peg from UC Berkeley, which accepts FSM description in simple hardware desrcuption language on input and produces logic equations on output [89]. This program is integrated into UC Berkeley VLSI tools so finally PLA artwork can be generated from it. State symbols are replaced with codes of states and the state table is rewritten to the truth table format for D type flip-flops. The assignment of codes to states is done either according to the order of their specification, which is practically random, or the user can declare his/her own codes.
In more advanced systems not yet available commercially, several optimization and analysis operations are done on the state table first to the truth table conversion. We will first concentrate on synchronous machines.
The optimization operations include some (or usually one) of the following:
The analysis includes simulation of the machine and testability analysis, as well as analysis of hazards in output functions of machines' realization.
In some systems the state table is enhanced with additional columns and/or rows to increase its testability with methods like LSSD or other [80, 1].
Many other FSM analysis methods have been theoretically investigated [114], and some of them were implemented in the academic environment, but industrial systems do not yet incorporate these methods.
Finally, the analysed and optimized state table is converted to a truth table. This truth table can be created for various types of flip-flops and has the primary input signals and outputs from flip-flops as inputs, and primary outputs and inputs to flip-flops as outputs. In most of current systems only the type D flip-flops are assumed, in some others the user has a choice of flip-flop types (RS, JK, T, D, RST) realized in an array. Selection of an appropriate flip-flop type can essentially decrease the area of logic realization for some machines, (like counters). In yet another system each flip-flop can be of a different type to further minimize silicon area for both logic and flip-flop components. Some interesting work on new types of flip-flops for VLSI implementation have been also published that will possibly even further reduce area for Boolean logic implementation, increasing slightly the area for flip-flops.
In the next stage the truth table is minimized and realized as a logic network. In most of the current systems a two-level realization of logic is assumed, but the recently realized systems also investigate the multi-level designs for many various technologies. Developments in this area will have also an essential influence on FSM optimization. For instance, the popular state assignment program Kiss [55] gives worse results when the assigned machine is realized with many levels of logic, than when it is realized in a two-level PLA. Existence of fast multi-level circuit minimizers will have the same positive effect on next generation assignment programs as PLA minimizer Espresso had on a creation of Kiss.
Below, we will discuss state assignment, minimization of number of states and other approaches to design FSMs, as well as design of asynchronous machines. State assignment will be discussed with most details, since it seems that this is an issue of most immediate practical applications.
FSM design systems are described in [2, 174, 15, 48, 27, 73, 36, 100, 123, 138, 139].