Hardware Reference
In-Depth Information
When the theory is extended to sequential circuits, don't care sets become sequences
of inputs instead of single inputs, since sequential circuits transform input sequences
into output sequences.
Definition 5.1.2.
The
input controllability sequential don't care set
, CDC
seq
in
,
includes all input sequences that are never produced by the environment at the
network's inputs. The
output observability sequential don't care sets
, ODC
seq
o
u
t
,
denote all input sequences that represent situations when an output is not observed
by the environment at the current time or in the future, and all subsets of input
sequences whose outputs are not distinguished by the environment.
When the previous definitions are applied to the components of a network, the
limited controllability or observability becomes a consequence of what cannot be
produced by a source component or cannot be observed/distinguished by a sink
component. These restrictions can be exploited to optimize the components; for
instance, since the output don't care sequences of a component are the subsets of
input sequences that cannot be distinguished at the outputs of the component, they
can be used to modify the component that produces them since the modifications
carry no effect on the component that receives them as inputs.
In the rest of the chapter, we will represent sometimes a composition like M
A
M
B
with the notation M
A
!
M
B
or M
A
$
M
B
, to highlight that it is a series
composition (M
A
!
M
B
) vs. a closed-loop (M
A
$
M
B
).
5.1.2
Computation of Input Don't Care Sequences
Consider a cascade interconnection of two FSMs M
A
and M
B
, where the driving
FSM M
A
feeds the input vectors to the driven FSM M
B
. Then input controllability
don't cares are the sequences of outputs not produced by M
A
; they restrict the
controllability of the driven FSM M
B
and are used to modify M
B
obtaining an
FSM
M
B
such that the cascade interconnection does not change, i.e., M
A
!
M
B
D
M
A
!
M
B
.
Kim and Newborn [69] were the first to give a procedure to compute all input
controllability don't care sequences for a series topology, as follows:
1. Construct a NDFA
NA
o
M
A
accepting the output language produced by the FSM
M
A
.
NA
o
M
A
is derived from M
A
by replacing the input/output labels by the output
labels and making each state acceptable; moreover a dead state F is added to
NA
o
M
A
, and if from state s there is no transition with label o then a transition from
s to F under o is added to
NA
o
M
A
.
2. Obtain A
o
M
A
as the determinization of
NA
o
M
A
(and minimize its states, if desired).
Search WWH ::
Custom Search