Hardware Reference
In-Depth Information
Fig. 10.1
Topology for Kim
and Newborn procedure
i
u
o
M
A
M
B
every state of
M
A
as a final state. For a state
s
, if there are output symbols not
emitted from it, a transition with these symbols is inserted from
s
to the dead
state
d
. The dead state
d
is the only non-accepting state. Thus
A
0
is completely
specified but nondeterministic in general.
2. Convert
A
0
to a minimized completely specified DFA
A
. This can be done by
using the subset construction and state minimization for DFA
A
. Note that the
efficient state minimization method
minimize
in BALM can be used, since the
subset construction produces a deterministic machine.
3. A modified machine
M
B
is constructed as follows: construct
M
B
A
and then
redirect to a DNC state all transitions to a state that contains the dead state
d
in
its subset.
M
B
is an incompletely specified FSM.
We assume that
M
A
and
M
B
are given in BLIF-MV format as
MA.mv
and
MB.mv
, respectively. We can translate these steps into the equivalent BALM
commands by the following script.
K&N script
read_blif_mv MA.mv
extract_aut MA.aut \# convert into an automaton
support u MA.aut MAs.aut \# remove input
complete MAs.aut MAsc.aut \# add the dead state
determinize MAsc.aut MAd.aut
minimize MAd.aut MAd_min.aut
read_blif_mv MB.mv
extract_aut MB.aut \# convert into an automaton
product MB.aut MAd_min.aut MBi.aut \# MB x A
prefix MBi.aut MBifsm.aut \# make prefix-closed
We illustrate this with a small example.
Machine MA.mv
.model MA
.inputs a b c d e
.outputs x y
.latch R1 r1
.reset r1
0
.latch R2 r2
.reset r2
0
.table c d x1
Search WWH ::
Custom Search