Information Technology Reference
In-Depth Information
f
(
a
,
b
)
a
1
g
b
Figure 2.5
The subfunction
f
of the function
g
is obtained by fixing some input variables,
assigning names to the rest, and deleting and/or permuting outputs.
This definition is illustrated by the function
f
(
3,2
)
example
(
x
1
,
x
2
,
x
3
)=(
y
1
,
y
2
)
in Fig.
2.2
.
We form the subfunction
y
1
by deleting
y
2
from
f
(
3,2
)
example
and fixing
x
1
=
a
,
x
2
=
1, and
x
3
=
b
,where
a
and
b
are new variables. Then, consulting (
2.3
), we see that
y
1
can be written
as follows:
y
1
=(
ab
)
∨
(
a b
)
∨
(
1
b
)
=
ab
∨
a b
=
a
⊕
b
⊕
1
That is,
y
1
contains the complement of the
EXCLUSIVE OR
function as a subfunction. The
definition is also illustrated by the reductions developed in Sections
2.5.2
,
2.5.6
,
2.9.5
,and
2.10.1
.
The subfunction definition derives its importance from the following lemma. (See Fig.
2.5
.)
LEMMA
2.4.1
If
f
is a subfunction of
g
, a straight-line program for
f
can be created from one
for
g
without increasing the size or depth of its circuit.
As shown in Section
2.9.5
, the logical shifting function (Section
2.5.1
) can be realized
by composing the integer multiplication and decoder functions (Section
2.5
). This type of
reduction is useful in those cases in which one function is reduced to another with the aid of
functions whose complexity (size or depth or both) is known to be small relative to that of
either function. It follows that the two functions have the same asymptotic complexity even if
we cannot determine what that complexity is. The reduction is a powerful idea that is widely
used in computer science. Not only is it the essence of the subroutine, but it is also used to
classify problems by their time or space complexity. (See Sections
3.9.3
and
8.7
.)
2.5
Specialized Circuits
A small number of special functions arise repeatedly in the design of computers. These include
logical and shifting operations, encoders, decoders, multiplexers, and demultiplexers. In the
following sections we construct efficient circuits for these functions.
Search WWH ::
Custom Search