Finite state machines (FSMs), as we all know them from basic Digital Design courses are represented on inputs to the CAD systems by state graphs or by state tables. Most of the current systems use either tabular descriptions or textual descriptions corresponding to the FSM tables. Sometimes tables are specified as sets of transitions:
(present state, input state, next state, output state),
where present state and next state are the internal states of the machine, and the input and output states are values of combinations of input and output signals, respectively. The internal states are either names or numbers or in the case of encoded (assigned) machines, they are strings of ones and zeros. The Number of elements in the string correspond to the number of flip-flops in a machine.
State tables are very useful for many types of machines, however they have two disadvantages: they cannot be used for large machines and also are not easily modifiable - adding new input signals or transitions often requires rewriting the whole table.
Three approaches are then used in the systems:
In the first approach, which is mainly caused by systems' and technology's inability to deal with oversized machines, the user is responsible for specifying the machine not as a single entity, but as a collection of mutually communicating smaller machines, each of them with smaller numbers of internal states, input and output signals. Unfortunately, little guidance is given as how to decompose the machine. Some ancient theoretical papers are well known [116, 188], see also their listing in [114], but as far as we are aware of, no working implementations of these methods are available as usable computer programs. Recently, a new approach to decomposition of machines is advocated by both university and industrial researchers that can possibly lead to better software tools [32]. It is based not on classical partition-based FSM decomposition theory, developed first by Harrison and Hartmanis/Stearns, but on graph-partitioning methods applied to FSM graph.
The second approach, high level description of FSM, is currently used mostly in academical systems and in some systems from large companies. Behavioral register-transfer (rt) languages are the most commonly used medium at this point [159]. The methods to convert rt-description to FSM state tables are well known [110, 28, 164]. This description makes it also easy to integrate the CAD system around it: with tools like rt-simulators, that simulate the circuit on behavioral level; flow-graph optimizers, that optimize speed and cost of both data-path and control unit parts of the circuit's realization; data-path allocators, that help to find optimum structures/floor plans of data paths, and other tools to design both the control unit and the data path parts of the system under design [135, 138, 139].
Recently, there has also been an interest in other forms of high-level description: regular expressions and Petri Nets. Regular expressions are expressions that describe a class of regular languages. They compose expressions E1 and E2 with use of operations of sum of expressions: E1 or E2, concatenation: E1 next E2 and iteration: E1 repeated arbitrary number of times. The systems to design FSMs from regular expressions have been designed in some universities, including: Stanford [75], Carnegie-Mellon and Columbia [76], McGill [78], and Portland State [144]. The Stanford system uses a special language, which is a combination of state machines and regular expressions. The first version used certain rules to directly map expressions to layout; the improved, second version uses a more classical approach where the expression is first converted to FSM, encoded and realized with Boolean functions [75]. The system from PSU uses the Brzozowski's method of derivatives of regular expressions [30], to convert a vector of regular languages to a Mealy or Moore machine. The program is written in the Artificial Intelligence language Prolog [33]. The regular expressions in this system can be of extended type, which means that operations of product of expressions, difference and negation of expressions are available, as well as those of sum, iteration and concatenation of expressions used in most of other systems [144].
The systems to design from Petri Nets are implemented in Universities of Paderborn and Dortmund in Germany [28]. Petri Nets are a form of graphs with parallelism and concurrency of execution of separate paths. They are commonly used to describe operating systems, controllers, and real time systems. Applications of Petri Nets in hardware descriptions on many levels has recently been gaining momentum.
Another interesting form of initial description includes predicate calculus clauses [102] (similiar to Prolog programs) and recursion equations [101] (similiar to Lisp programs).
The third method of FSM specification - graphical interface, seems to be very promising for future systems and can be used in conjunction with all other specification methods discussed above. Graphical schematic capture and window/menu systems are used for capture of logic schemata, block schemata and real-time system diagrams for software design. In two existing systems: one from Daisy and one from Intel, schematic capture is used to capture FSM graphs. However, a very similiar method can be applied also to capture flow-diagrams, Petri Nets, regular expressions or non-deterministic automata. We are not aware of any actual implementations, but supposedly they are coming. The graphical interfaces for these data should have all standard capabilities, like panning, zooming, pull-down menus, separate windows for graphics and text that can be selected from higher level pictorial descriptions. They should permit the introduction of hierarchially organized obiect-oriented data like the hierarchical, parallel automata of Harel [Hare 84].
Numerous papers and algorithms are devoted to the topic of converting high-level FSM descriptions to either FSM tables, or to lower level descriptions like logic networks. Some methods of direct conversion of flow-graphs, regular expressions or Petri Nets, even to the level of schematic geometrical layout have been also created.
Some of the conversions are NP-complete combinatorial problems [81], which make them difficult to apply for larger machines, and the decomposition is again a must. It also seems that not enough research was done on finding efficient transformation methods, which would make more use of algorithmic and heuristic methods developed recently both in other areas of VLSI CAD and in Artificial Intelligence and Mathematical Programming. Introduction of more powerful "personal supercomputers", like iPSC from Intel, should soon dramatically improve the prospects, since many of the conversion algorithms are very well amenable for parallelization.