Information Technology Reference
In-Depth Information
address is
a
. Thus, the memory words
w
0
,
w
1
,
...
,
w
m−
1
change only when
s
1
=
1. The
word that changes is determined by the
μ
-bit address
a
supplied as part of the input. Let
a
μ−
1
,
...
,
a
1
,
a
0
be the
μ
bits of
a
. Let these bits be supplied as inputs to an
μ
-bit decoder
function
f
(
μ
)
decode
(see Section
2.5.4
). Let
y
m−
1
,
...
,
y
1
,
y
0
be the
m
outputs of a decoder
circuit. Then, the Boolean function
c
i
=
s
1
y
i
(shown in Fig.
3.21
(a)) is 1 exactly when
the input address
a
is the binary representation of the integer
i
and the FSM
M
RMEM
is
commanded to
write
the word
d
at address
a
.
Let
w
0
,
w
1
,
...
,
w
∗
m−
1
be the new values for the memory words. Let
w
i
,
j
and
w
i
,
j
be the
j
th components of
w
i
and
w
i
, respectively. Then, for 0
≤
i
≤
m
−
≤
j
≤
b
−
1and0
1we
write
w
i
,
j
in terms of
w
i
,
j
and the
j
th component
d
j
of
d
as follows:
c
i
=
s
1
y
i
w
i
,
j
=
c
i
w
i
,
j
∨
c
i
d
j
Figures
3.21
(a) and (b) show circuits described by these formulas. It follows that changes
to memory words can be realized by a circuit containing
C
Ω
f
(
μ
)
decode
gates for the decoder,
m
gates to compute all the terms
c
i
,0
≤
i
≤
m
−
1, and 4
mb
gates to compute
w
i
,
j
,0
≤
i
≤
m
−
≤
j
≤
b
−
1, 0
1(
NOT
s are counted). Combining this with Lemma
2.5.4
,wehavethat
w
i
,
j
z
j
d
j
y
i
∧
w
i
,
j
c
i
w
i
,
j
s
0
z
j
s
0
u
j
s
1
w
i
,
j
...
...
y
m−
1
y
i
y
0
f
(
μ
)
decode
...
...
y
0
∧
w
0,
j
y
2
∧
w
2,
j
y
i
∧
w
i
,
j
a
μ−
1
a
μ−
2
a
0
y
1
∧
w
1,
j
y
m−
1
∧
w
m−
1,
j
(a)
(b)
Figure 3.21
A circuit that realizes the next-state and output function of the random-access
memory. The circuit in (a) computes the next values
{w
i
,
j
}
for components of memory words,
whereas that in (b) computes components
{z
i
}
of the output word. The output
y
j
∧ w
i
,
j
of (a)
is an input to (b).
Search WWH ::
Custom Search