Exsisting approaches to state assignment.

A State Assignment Problem is to assign codes to the internal states of FSM in order to mimimize some cost function related to the circuit's realization (like PLA area or number of gates).

Most of the research papers discuss only the problem of assigning internal states, assuming that the user specifies codes for input and output states. However, there are efforts based on very similiar principles which assign input states and output states (specified initially by names) with binary codes. They have found, for instance, application in minimization of microprogrammed control units [57] or in designing control units with PLAs [103].

The problem is a classic in Switching Circuits Theory, but relatively few programs have been widely available until recent years. In the early sixties the basic main approaches to state assignment and structural theory of FSMs were formulated. Few of them were programmed and the programming results were rather unsatisfactory. Recently the state assignment problem is again gaining momentum because of widespread attempts to realize a logic level silicon compiler for VLSI [52] - [61], [121, 122], [138] - [143].

We will not characterize and evaluate in more detail the existing approaches here. The reader can find respective discussion in [52, 55, 59, 122]. However, some comparison of the known approaches will serve to present the main theoretical and practical issues that must be solved to make the respective software tools useful.

There are basically seven approaches to state assignment:

1. Partition theory of Hartmanis, Stearns, Kohavi [92, 93, 91, 168, 106, 113]. The theory is based on a concept of the partition of states of machine into blocks. Partitions are found from state tables and used to find sets of partitions producing unique and optimal encodings. This theory is very elegant from mathematical point of view, gives an insight into the nature of structural properties of machines, as well it is very general (it permits also for decomposition of FSMs, state minimization, realization with shift-registers, etc.). However, the published results of programs that use this theory, as well as our own experience with this approach prove that in general, this approach is intractable for computer solutions of FSMs with more than 10 states, 10 inputs, and 10 outputs.
2. Column evaluation approach of Dolotta and Mc Cluskey [69], extended by Curtis [40, 41], Weiner [182], Vavilov [179], Torng [176]. The columns of the state table are scored with respect to many various criteria influencing quality of assignment. The scores are used to find good partitions and next the assignment. This approach can produce very good realizations (also for various types of flip-flops); the results are even better than those from approach 1, but is also intractable for machines of more than 12 states.
3. Enumerative approach of Story [170]. All posible partitions are evaluated as candidates for assignment separately by calculating the complexities of realizations of the corresponding Boolean functions, and assuming that all other partitions have been optimally selected for them. The subset of partitions with the best scores, also mutually matching, is selected for assignment. This approach gives better results than the approach from 2, but it is even slower.
4. Branch and bound approach of Perkowski, Lee and Zasowska [138, 187, 121, 122, 141]. This approach has two variants. The first permits realization of machines with 8 input, 8 internal and 8 output states and gives optimum realizations for arbitrary technology and flip-flops. However, in this variant nearly all possible partitions have to be evaluated. This is perhaps the program that generates most optimum solutions of all the published programs, but is very slow. The approximate method based on this method [122] does not evaluate all partitions, but only heuristically selected best partitions. It permits for realization of machines with 12 states, but can be extended to 18 - 20 states. Both approaches permit for state assignment combined with state minimization.
5. Quadratic assignment approaches of Armstrong, De Micheli and Perkowski [6, 7, 52, 144]. All these approaches are based on embedding some graphs created from FSM table to hypercube graphs. This approach permits for realization of machines to 100 states but according to evaluations from [6], it gave solutions too far from optimum. Some theoretical improvements were made in [7], but not programmed. De Micheli implemented two algorithms for state assignment, while at UC Berkeley. The first of them was based on the quadratic assignment method - state assignment is reduced to the graph embedding problem. The second algorithm was based on other principles since he was not satisfied with quality of results. The results from [144], where both creation of the graph for embedding and the embedding algorithm were done on new principles, seem to be very satisfactory (machines with 136 states have been assigned), but no detailed comparison with other approaches is yet available.
6. Approach of Moroz [128]. This is a very fast constructive embedding algorithm that is widely used in design automation systems in Soviet Union. The author has implemented this algorithm and observed that it can find assignments for machines with more than 100 states, but that the quality of solutions for small machines was far from optimum. This is perhaps the fastest program currently available. The speed results from the fact that it does not solve the quadratic assignment but simple edges embedding problem, and also the graph for embedding is created directly from the state graph.
7. Approach of De Michelli, Brayton and Sangiovanni-Vincentelli [52] - cite[DeMi 85b], [23, 151] (KISS program). This approach is based on minimization of multiple-valuated Boolean functions to find state groups and then constructive assignment by embedding of these groups to the faces of a hypercube. Its strategy is very innovative and the computer results are very good. It is perhaps the best product currently available from the point of quality/time ratio. It was applied to machines with up to 100 states, but the largest published result is for 27 states. The groups of states are found with the use of multi-valued Boolean minimization program Espresso-mv [23, 150, 151] applied to FSM before state assignment. This method of finding groups of states (blocks), combined with fast Boolean minimization was a source of program's success. The Kiss program is now widely available in universities and is used by many companies to build commercial software. A program extending this approach was built in Intel [36].