Hardware Reference
In-Depth Information
Chapter 10
Computation of Flexibility in Sequential
Networks
There is a long history of resynthesizing an FSM, given its surrounding
environment. Much of the work was modeled after results for combinational
networks. Thus input sequential don't cares and output sequential don't cares
were defined in analogy to satisfiability and observability don't cares. For example,
input sequential don't cares were defined as input sequences that can never happen
at a state because of the FSM input environment. An elegant theory was provided by
Kim and Newborn for treating the case of a cascade of two FSMs. This is discussed
in Sect.
10.1
as well as an extension by Wang and Brayton in Sect.
10.2
.These
results provide reasonable computational procedures and can be used for resynthesis
of an FSM. However, attempts at extending to output sequential don't cares became
overly complicated and were unsuccessful. It was surprising then that Watanabe
came up with a computation for the full flexibility for an FSM embedded in an envi-
ronment, which captures all input and output sequential don't cares. This was called
the “E-machine” and was constructed by a somewhat complicated construction. It
became clear later that this construction essentially modeled the subset construction.
Now we know that this full flexibility embodied by the E-machine is simply the
largest FSM solution obtained by language solving, and a simpler construction is
the one given in this topic and discussed in this chapter in more detail.
10.1
The Kim-Newborn's Procedure
J. Kim and M.M. Newborn [69] devised a procedure to compute an incompletely
specified machine which takes account of all input sequences which can never
occur in a cascade connection of two FSMs. The topology considered is shown
in Fig.
10.1
,where
M
A
and
M
B
are FSMs.
We review the procedure:
1. Construct an NFA
A
0
to accept the
u
-language produced by machine
M
A
.This
can be achieved by removing the input part in the STG of
M
A
, and considering
Search WWH ::
Custom Search