Information Technology Reference
In-Depth Information
LEMMA
2.5.5
The multiplexer function
f
(
n
)
2
n
+
n
mux
:
B
→B
can be realized with the following
circuit size and depth over the basis
Ω
0
=
{∧
,
∨
,
¬}
:
C
Ω
0
f
(
n
)
mux
2
n
+
2
(
n
1
)
2
n/
2
≤
3
·
−
−
1
D
Ω
0
f
(
n
)
mux
≤
n
+
log
2
n
+
2
Using the lower bound of Theorem
9.3.3
, one can show that it is impossible to reduce
the upper bound on circuit size to less than 2
n
+
1
−
2. At the cost of increasing the depth by
1, the circuit size bound can be improved to about 2
n
+
1
. (See Problem
2.15
.) Since
f
(
n
)
mux
depends on 2
n
+
n
variables, we see from Theorem
9.3.1
that it must have depth at least
log
2
(
2
n
+
n
)
≥
n
. Thus, the above depth bound is very tight.
2.5.6 Demultiplexer
The
demultiplexer function
f
(
n
)
2
n
is very similar to a decoder. It has
n
+
1
inputs consisting of
n
bits,
x
, that serve as an address and a data bit
e
.Ithas2
n
outputs
y
all
of which are 0 if
e
=
0andoneoutputthatis1if
e
=
1, namely the output specified by the
n
address bits. Demultiplexers are used to route a data bit (
e
)tooneof2
n
output positions.
A circuit for the demultiplexer function can be constructed as follows. First, form the
AND
of
e
with each of the
n
address bits
x
n−
1
,
...
,
x
1
,
x
0
and supply this new
n
-tuple as input to
a decoder circuit. Let
z
=(
z
2
n
−
1
,
...
,
z
1
,
z
0
)
be the decoder outputs. When
e
=
0, each of
the decoder inputs is 0 and each of the decoder outputs except
z
0
is 0 and
z
0
=
1. If we form
the
AND
of
z
0
with
e
, this new output is also 0 when
e
=
0. If
e
=
1, the decoder input is the
address
x
and the output that is 1 is in the position specified by this address. Thus, a circuit
for a demultiplexer can be constructed from a circuit for
f
(
n
)
n
+
1
demux
:
B
→B
decode
to which are added
n
AND
gates on its input and one on its output. This circuit has a depth that is at most 2 more than
the depth of the decoder circuit. Since a circuit for a decoder can be constructed from one
for a demultiplexer by fixing
e
=
1, we have the following bounds on the size and depth of a
circuit for
f
(
n
)
demux
.
LEMMA
2.5.6
The demultiplexer function
f
(
n
)
demux
2
n
n
+
1
:
B
→B
can be realized with the
following circuit size and depth over the basis
Ω
0
=
{∧
∨
¬}
,
,
:
C
Ω
0
f
(
n
)
demux
C
Ω
0
f
(
n
)
decoder
≤
−
≤
n
+
1
0
D
Ω
0
f
(
n
)
demux
D
Ω
0
f
(
n
)
decoder
0
≤
−
≤
2
2.6 Prefix Computations
The prefix computation first appeared in the design of logic circuits, the goal being to paral-
lelize as much as possible circuits for integer addition and multiplication. The carry-lookahead
adder is a fast circuit for integer addition that is based on a prefix computation. (See Sec-
tion
2.7
.) Prefix computations are now widely used in parallel computation because they
provide a standard, optimizable framework in which to perform computations in parallel.
The
prefix function
(
n
)
n
on input
x
=(
x
1
,
x
2
,
...
,
x
n
)
produces as
output
y
=(
y
1
,
y
2
,
...
,
y
n
)
, which is a running sum of its
n
inputs
x
using the operator
n
P
:
A
→A
Search WWH ::
Custom Search