Information Technology Reference
In-Depth Information
x
8
x
5
x
7
x
4
x
6
x
1
x
2
x
3
Figure 1.4
A full-adder circuit. Its output pair (
x
8
,
x
7
)
is the standard binary representation
for the number of 1's among its three inputs
x
1
,
x
2
,and
x
3
.
and
x
8
. Full-adder circuits can be combined to construct an adder for binary numbers. (In
Section
2.2
we give another notation for straight-line programs.)
As shown in the truth table for Fig.
1.3
(c), each logic circuit has associated with it a binary
function that maps the values of its input variables to the values of its output variables. In the
case of the full-adder, since
x
8
and
x
7
are its output variables, we associate with it the function
f
(
3,2
)
FA
2
, whose value is
f
(
3,2
)
3
FA
(
x
1
,
x
2
,
x
3
)=(
x
8
,
x
7
)
.
Algebraic circuits are similar to logic circuits except they may use operations over non-
binary sets, such as addition and multiplication over a ring, a concept explained in Sec-
tion
6.2.1
. Algebraic circuits are the subject of Chapter
6
. They are also described by DAGs
and they execute straight-line programs where the operators are non-binary functions. Alge-
braic circuits also have associated with them functions that map the values of inputs to the
values of outputs.
Logic circuits are the basic building blocks of all digital computers today. When such
circuits are combined with binary memory cells, machines with memory can be constructed.
The models for these machines are called finite-state machines.
:
B
→B
1.4.2 Finite-State Machines
The
finite-state machine
(FSM) is a machine with memory. It executes a series of steps during
each of which it takes its current state from the set
Q
of states and current external input from
the set
Σ
of input letters and combines them in a logic circuit L to produce a successor state
in
Q
and an output letter in
Ψ
, as suggested in Fig.
1.5
. The logic circuit L can be viewed as
having two parts, one that computes the
next-state function
δ
:
Q
Q
, whose value
is the next state of the FSM, and the other that computes the
output function
λ
:
Q
×
Σ
→
Ψ
,
whose value is the output of the FSM in the current state. A generic finite-state machine is
shown in Fig.
1.5
(a) along with a concrete FSM in Fig.
1.5
(b) that provides as successor state
and output the
EXCLUSIVE OR
of the current state and the external input. The
state diagram
of the FSM in Fig.
1.5
(b) is shown in Fig.
1.8
. Two (or more) finite-state machines that operate
→
Search WWH ::
Custom Search