Exploitation of Flexibility in Sequential Networks - The Unknown Component Problem: Theory and Applications - page 217

Chapter 14
Exploitation of Flexibility in Sequential
Networks

14.1 The Problem

We have seen how language equations can be solved by manipulating automata
or FSMs, and that a largest solution can be obtained in terms of a deterministic
automaton. If the solution is required as a finite state machine, then the solution
can be made prefix-closed and (input)-progressive. At this point, we have the
largest (non-deterministic, in general) FSM solution which contains all possible
deterministic FSMs that are a solution; usually a deterministic FSM solution can
be obtained by selecting a submachine of the largest solution. In some problems, it
is enough to know that a solution exists and any one solution will be adequate. In
other problems, we want a solution which can be implemented in an efficient way,
say with small area, or power or delay.
It is surprisingly difficult to find small solutions. The problem is that the solution
obtained in the language solving paradigm is a description of a state transition graph
(STG) and we want to convert this into a netlist consisting of interconnections
of logic gates and latches. This requires making choices on how to use the non-
determinism, possibly minimizing the number of states, and encoding the states
by associating values in the latches to each state. These are hard problems for
which there exist some algorithms for solving them either exactly or (more often)
heuristically. The most work has been on FSMs where the non-determinism is in
the form of incomplete specification. Therefore, the material in this part of the topic
reviews some of these techniques to understand how they can be used.
It should be noted that the automata solutions computed by the methods of this
topic are deterministic because the last step in the solving method is complementa-
tion. The only effective method for complementing a non-deterministic automaton
(as far as we know) is to determinize it first and then negate the accepting conditions.
Hence the answer is always in the form of a deterministic automaton. There is
an effective method for state-minimizing a deterministic automaton and this is
embodied in the BALM command minimize . Mostly this should be used as a
final step, but it does not produce what we want. What we want is a reduction or