Information Technology Reference
In-Depth Information
xyg
5
g
7
0000
0101
1011
1100
We now ask the following question: “Given a circuit with values for its inputs, how can the
values of its outputs be computed?” One response it to build a circuit of physical gates, supply
values for the inputs, and then wait for the signals to propagate through the gates and arrive at
the outputs. A second response is to write a program in a high-level programming language to
compute the values of the outputs. A simple program for this purpose assigns each step to an
entry of an array and then evaluates the steps in order. This program solves the
circuit value
problem
; that is, it determines the value of a circuit.
2.2.2 Circuits That Compute Functions
Now that we know how to compute the function defined by a circuit and its corresponding
straight-line program, we ask: given a function, how can we construct a circuit (and straight-
line program) that will compute it? Since we presume that computational tasks are defined by
functions, it is important to know how to build simple machines, circuits, that will solve these
tasks. In Chapter
3
we show that circuits play a central role in the design of machines with
memory. Thus, whether a function or task is to be solved with a machine without memory (a
circuit) or a machine with memory (such as the random-access machine), the circuit and its
associated straight-line program play a key role.
To construct a circuit for a function, we begin by describing the function in a table. As
seen earlier, the table for a function
f
(
n
,
m
)
m
has
n
columns containing all 2
n
possible values for the
n
input variables of the function. Thus, it has 2
n
rows. It also has
m
columns containing the
m
outputs associated with each pattern of
n
inputs. If we let
x
1
,
x
2
,
...
,
x
n
be the
input variables
of
f
and let
y
1
,
y
2
,
...
,
y
m
be its
output variables
,
n
:
B
→B
f
(
3,2
)
example
x
1
x
2
x
3
y
1
y
2
00011
00101
01010
01101
10011
10110
11001
11111
Figure 2.2
The truth table for the function
f
(
3,2
)
example
.
Search WWH ::
Custom Search