Information Technology Reference
In-Depth Information
of
M
.AsshowninFig.
3.25
,itisconvenienttoview
M
as a pair of synchronous FSMs
(see Section
3.1.4
) and design separate circuits for
M
's control and tape units. The design
of the circuit for the control unit is straightforward since it is an unspecified NFSM. The
tape circuit
, which realizes the next-state and output functions for the tape unit, contains
m
cell circuits
, one for each cell on the tape. We denote by
T
,the
t
th tape
circuit. We begin by constructing a tape circuit and determining its size and depth.
For 0
C
t
(
m
)
,1
≤
t
≤
T
let
C
j
,
t
be the
j
th cell circuit of the
t
th tape circuit,
C
t
(
m
)
.
C
j
,
t
produces the value
a
j
,
t
contained in the
j
th cell after the
j
th step as well as
s
j
,
t
, whose value is 1 if the head is over the
j
th tape cell after the
t
th step and 0 otherwise.
The value of
a
j
,
t
is either
a
j
,
t−
1
if
s
j
,
t
=
0 (the head is not over this cell) or
w
if
s
j
,
t
=
1
(the head is over the cell). Subcircuit
SC
2
of Fig.
3.26
performs this computation.
Subcircuit
SC
1
in Fig.
3.26
computes
s
j
,
t
from
s
j−
1,
t−
1
,
s
j
,
t−
1
,
s
j
+
1,
t−
1
and the triple
h
t
=(
h
−
1
≤
j
≤
m
and 1
≤
t
≤
,
h
t
,
h
+
t
)
,where
h
−
1
t
=
1 if the head moves to the next lower-numbered cell,
h
+
t
=
1 if it moves to the next higher-numbered cell, or
h
t
=
1 if it does not move. Thus,
s
j
,
t
=
1if
s
j
+
1,
t−
1
=
1and
h
−
1
t
=
1, or if
s
j−
1,
t−
1
and
h
+
1
=
1, or if
s
j
,
t−
1
=
1and
t
t
h
t
=
1. Otherwise,
s
j
,
t
=
0.
Subcircuit
SC
3
of cell circuit
C
j
,
t
generates the
b
-bit word
v
j
,
t
that is used to provide
the value under the head on the
t
th step.
v
j
,
t
is
a
j
,
t
if the head is over the
j
th cell on the
SC
2
a
j
,
t
−
1,
b
a
j
,
t
,
b
w
b
a
j
,
t−
1,1
a
j
,
t
,1
w
1
SC
3
v
j
,
t
,
b
s
j
+
1
,
t
−
1
SC
1
h
−
1
t
s
j
,
t−
1
v
j
,
t
,1
s
j
,
t
h
t
s
j−
1
,
t
−
1
h
+
1
t
Figure 3.26
The cell circuit
C
j
,
t
has three components:
SC
1
, a circuit to compute the new
value for the head location bit
s
j
,
t
from the values of this quantity on the preceding step at
neighboring cells and the head movement vector
h
t
,
SC
2
, a circuit to replace the value in the
j
th
cell on the
t
step with the input
1
)
st step (
s
j
,
t−
1
=
1),
and
SC
3
, a circuit to produce the new value in the
j
th cell at the
t
th step if the head is over this
cell (
s
j
,
t
=
1) and the zero vector otherwise. The circuit
C
j
,
t
has 5
(
b
+
1
)
gates and depth 4.
w
if the head is over the cell on the
(
t −
Search WWH ::
Custom Search