Information Technology Reference
In-Depth Information
xy
x
y
x
y
z
z
+
+
+
−
−
−
xy
xy
xy
(a)
(b)
(c)
Figure 1.3
Three electrical circuits simulating logic circuits.
when the switch that carries its name is closed; otherwise they have value 0.
xyz
(
x
∨
y
)
∧
z
000 0
001 0
010 0
011 1
100 0
101 1
110 0
111 1
Today's computers use transistor circuits instead of the electrical circuits of Fig.
1.3
.
Logic circuits execute
straight-line programs
, programs containing only assignment state-
ments. Thus, they have no loops or branches. (They may have loops if the number of times
a loop is executed is fixed.) This point is illustrated by the “full-adder” circuit of Fig.
1.4
,
a circuit discussed at length in Section
2.7
. Each external input and each gate is assigned a
unique integer. Each is also assigned a variable whose value is the value of the external input
or gate. The
i
th vertex is assigned the variable
x
i
.If
x
i
is associated with a gate that combines
the results produced at the
j
th and
k
th gates with the operator
,wewritean
assignment
operation
of the form
x
i
:=
x
j
x
k
. The sequence of assignment operations for a circuit is
a straight-line program. Below is a straight-line program for the circuit of Fig.
1.4
:
x
4
:=
x
1
⊕
x
2
x
5
:=
x
4
∧
x
3
x
6
:=
x
1
∧
x
2
x
7
:=
x
4
⊕
x
3
x
8
:=
x
5
∨
x
6
The values computed for
(
x
8
,
x
7
)
are the standard binary representation for the number of 1's
among
x
1
,
x
2
,and
x
3
. This can be seen by constructing a table of values for
x
1
,
x
2
,
x
3
,
x
7
,
Search WWH ::
Custom Search