Decompositional state assignment with reuse of standard designs : using counters as sub-machines and using the method of maximal adjacencies to select the state chains and the state codes
L. Jóźwiak, TG Kwaaitaal-Spassova · TU/e Research Portal · 1990
One of the most important steps in the design of finite state machines is the assignment of values to the binary state variables to represent the symbolic internal states of the machine. The complexity of the resulting implementation can vary extensively from assignment to assignment. From our experiments with more than 20 sequential machines follows, that the silicon area for the best assignment that we found, was typically about half that for the worst assignment. The problem of finding an optimal state assignment is computationally complex. It is NP-hard. In a strict sense, it has never been solved, except for exhaustive search, which for large machines is unpractical or impossible, even using a computer. In this situation, some approximated heuristic approaches must be used. Using some knowledge about the internal structure of a sequential machine, these approaches try to reduce the search space to a manageable size and to keep the high quality solutions in that reduced space. They produce often very good solutions, but they do not guarantee the strict optimality for them. Most of the known heuristic state assignment methods work better for small than for large machines. For the above reasons, decompositional state assignment approaches are interesting.