Information Technology Reference
In-Depth Information
Output
Output
Input
Input
L
Memory
Memory
(a)
(b)
Figure 1.5
(a) The finite-state machine (FSM) model; at each unit of time its logic unit,
L
,
operates on its current state (taken from its memory) and its current external input to compute an
external output and a new state that it stores in itsmemory.(b)AnFSMthatholdsinitsmemory
a bit that is the
EXCLUSIVE OR
of the initial value stored in its memory and the external inputs
received to the present time.
in lockstep can be interconnected to form a single FSM. In this case, some outputs of one FSM
serve as inputs to the other.
Finite-state machines are ubiquitous today. They are found in microwave ovens, VCRs and
automobiles. They can be simple or complex. One of the most useful FSMs is the general-
purpose computer modeled by the random-access machine.
1.4.3 Random-Access Machine
The (bounded-memory)
random-access machine
(RAM) is modeled as a pair of intercon-
nected finite-state machines, one a
central processing unit
(CPU) and the other a
random-
access memory
, as suggested in Fig.
1.6
. The random-access memory holds
mb
-bit words,
each identified by an address. It also holds an output word (
out wrd
) and a triple of inputs
Random-Access Memory
b
m
−
1
CPU
m
−
2
cmd
Decode
ALU
out wrd
reg
a
reg
b
in wrd
1
0
prog ctr
addr
Figure 1.6
The bounded-memory random-access machine.
Search WWH ::
Custom Search