Information Technology Reference
In-Depth Information
2
)
√
m
gates. The depth of this portion of the circuit is the depth of the decoder plus 4 because the
longest path between an input an
d
an output
w
0
,
w
1
,
...
,
w
∗
m−
1
is through the decoder and
then through the gates that form
c
i
w
i
,
j
. This depth is at most
a circuit realizing this portion of the next-state function has at most
m
(
4
b
+
2
)+(
2
μ
−
+
5.
The circuit description is complete after we give a circuit to compute the output word
z
.
The value of
z
changes only when
s
0
=
1, that is, when a
read
command is issued. The
j
th
component of
z
,namely
z
j
, is replaced by the value of
w
i
,
j
,where
i
is the address specified by
the input
a
. Thus, the new value of
z
j
,
z
j
, can be represented by the following formula (see
the circuit of Fig.
3.21
(b)):
log
2
μ
m−
1
z
j
=
s
0
z
j
∨
s
0
y
k
w
k
,
j
≤
j
≤
b
−
for 0
1
k
=
0
Here
denotes the
OR
of the
m
terms
y
k
w
k
,
j
,
m
=
2
μ
. It follows that for each value of
j
this portion of the circuit can be realized with
m
two-input
AND
gates and
m
−
1two-input
OR
gates (to form
) plus four additional operations. Thus, it is realized by an additional
(
2
m
+
3
)
b
gates. The depth of this circuit is the depth of the decoder (
log
μ
+
1) plus
μ
=log
2
m
, the depth of a tree of
m
inputs to form
, plus three more levels. Thus, the
depth of the circuit to produce the output word is
μ
+
+
4.
Th
e size of the complete circuit for the next-state function is at most
m
(
6
b
+
2
)+(
2
μ
log
2
μ
−
2
)
√
m
+
3
b
.Itsdepthisatmost
μ
+
log
2
μ
+
4. We state these results as a lemma.
LEMMA
3.5.1
The next-state and output functions of the FSM
M
RMEM
(
μ
,
b
)
,
δ
RMEM
and
λ
RMEM
, can be realized with the following size and depth bounds over the standard basis
Ω
0
,
where
S
=
mb
is its storage capacity in bits:
2
)
√
m
+
3
b
=
O
(
S
)
C
Ω
0
(
δ
RMEM
,
λ
RMEM
)
≤
m
(
6
b
+
2
)+(
2
μ
−
D
Ω
0
(
δ
RMEM
,
λ
RMEM
)
≤
μ
+
log
2
μ
+
4
=
O
(log(
S/b
))
Random-access memories can be very large, so large that their equivalent number of logic
elements (which we see from the above lemma is proportional to the storage capacity of the
memory) is much larger than the tens to hundreds of thousands of logic elements in the CPUs
to which they are attached.
3.6
Computational Inequalities for the RAM
We now state computational inequalities that apply for all computations on the bounded-
memory RAM. Since this machine consists of two interconnected synchronous FSMs, we
invoke the inequalities of Theorem
3.1.3
, which require bounds on the size and depth of the
next-state and output functions for the CPU and the random-access memory.
From Section
3.10.6
we see that size and depth of these functions for the CPU grow slowly
in the word length
b
and number of memory words
m
.InSection
3.5
we designed an FSM
modeling an
S
-bit random-access memory and showed that the size and depth of its next-state
and output functions are proportional to
S
and
log
S
, respectively. Combining these results,
we obtain the following computational inequalities.
Search WWH ::
Custom Search