Information Technology Reference
In-Depth Information
g
7
g
5
g
6
g
4
g
3
g
1
g
2
y
x
Figure 2.1
A circuit is the graph of a Boolean straight-line program.
scription of the circuit, where
g
j
is the value computed by the
j
th input or gate of the circuit:
g
1
:=
x
;
g
5
:=
g
1
∧
g
4
;
g
2
:=
y
;
g
6
:=
g
3
∧
g
2
;
(2.1)
g
3
:=
g
1
;
g
7
:=
g
5
∨
g
6
;
g
4
:=
g
2
;
The statement
g
1
:=
x
;
means that the exte
rn
al input
x
is the value associated with the first
vertex of the circuit. The statement
g
3
:=
g
1
;
means that the value computed at the third
vertex is the
NOT
of the value computed at the first vertex. The statement
g
5
:=
g
1
∧
g
4
;
means that the value computed at the fifth vertex is the
AND
of the values computed at the
first and fourth vertices. The statement
g
7
:=
g
5
∨
g
6
;
means that the value computed at the
seventh vertex is the
OR
of the values computed at the fifth and sixth vertices. The above is
a description of the functions computed by the circuit. It does not explicitly specify which
function(s) are the outputs of the circuit.
Shown below is an alternative description of the above circuit that contains the same infor-
mation. It is a
straight-line program
whose syntax is closer to that of standard programming
languages. Each step is numbered and its associated purpose is given.
Input
and
output
steps
are identified by the keywords
READ
and
OUTPUT
, respectively.
Computation steps
are identified by the keywords
AND
,
OR
,and
NOT
.
(
1
READ
x
)
(
2
READ
y
)
(
3
NOT
1
)
(
4
NOT
2
)
(
5
AND
1
)
(
6
AND
3
)
(
7
OR
5
)
(
8
OUTPUT
5
)
(
9
OUTPUT
7
)
(2.2)
The correspondence between the steps of a straight-line program and the functions computed
at them is evident.
Straight-line programs are not limited to describing logic circuits. They can also be used to
describe algebraic computations. (See Chapter
6
.) In this case, a computation step is identified
with a keyword describing the particular algebraic operation to be performed. In the case of
Search WWH ::
Custom Search