Hardware Reference
In-Depth Information
3. Compute M
B
as the product of A
o
M
A
and M
B
,
1
except that transitions going
into states of the product machine containing F are considered as unspecified
transitions (in other words, they are sent to a dummy state
DC
with a self-
loop under every input asserting every output). So M
B
is an ISFSM that
can be reduced using conventional algorithms for state minimization. After
minimization, M
B
is guaranteed to have no more states than M
B
.
In [121] a heuristic was provided to reduce the number of states of A
o
M
A
by
discarding some don't care information; still A
o
M
A
has to be built first. More
heuristics to approximate input don't care sequences were explored in [139].
Later on, Wang and Brayton [139] showed that input don't care sequences for
a component in a network of FSMs with an arbitrary topology can be exploited in
the same way as in a series topology and that computing input don't care sequences
for an arbitrary topology can be reduced to computing them for a series topology.
Given the FS
Ms
M
A
and M
B
composed in a two-way topology, M
A
$
M
B
,itwas
proved that if
L
x
ar
e the input don't cares sequences for M
B
,andifM
B
is obtained
from M
B
using
L
x
as unspecified transitions and M
0
B
is obtained from M
B
after
state minimization, it holds that M
A
$
M
B
D
M
A
$
M
0
B
, i.e., the behavior of the
network is preserved when M
0
B
replaces M
B
.
An FSM network with an arbitrary topology and including FSM M
B
can be
reduced to the case of a two-way topology, by lumping together as FSM M
A
all
the FSM components except for M
B
. In this way, the original network is reduced
to either a series topology or a two-way topology of FSMs M
A
and M
B
.Asa
result, input don't care sequences for a component in a general FSM network can be
exploited using state minimization procedures for incompletely specified FSMs. To
compute the input don't care sequences with the procedure of Kim and Newborn,
a further step is needed to reduce from a two-way topology to a series topology, as
follows: consider a network M
A
$
M
B
and call it
N
,thennetwork
N
produces the
N
0
drawn in Fig.
5.1
, because M
A
$
M
B
produces
the same U and V sequences in
same I/O sequences as network
N
0
, therefore M
A
and M
B
behave
N
as it does in
N
0
as they do in
N
0
produces the same
under U and V in network
N
,andso
I/O sequences as network
. By this transformation from a two-way topology to
a series topology, the input don't care sequences respectively of M
A
and M
B
are
preserved. The driving machine is in both cases the composition of FSMs M
A
and
M
B
, M
A
$
M
B
, and it is called the abstract driving machine of the FSM network.
In general, given an FSM network and a component FSM M
B
whose input don't
care sequences should be computed, the abstract driving machine is the network
itself, unless M
B
is in a one-way communication with the other components and so
the abstract driving machine is the network except M
B
. The previous steps establish
that it is correct to apply the procedure by Kim and Newborn directly to an arbitrary
FSM network topology. In summary:
N
1
One has to take care of defining over the same alphabets both A
o
M
A
and M
B
, for instance turning
A
o
M
A
into an FSM with don't care outputs for each input combination of the automaton A
o
M
A
.
Search WWH ::
Custom Search