Information Technology Reference
In-Depth Information
b) Show that the size and depth of a dual-rail logic circuit for a function
f
:
→B
areatmosttwicethecircuitsize(plustheNOTsfortheinputs)andatmostone
more than the circuit depth of
f
over the basis
B
n
{
}
AND
,
OR
,
NOT
, respectively.
n
2.13 A function
f
:
B
→B
≤
j
≤
n
,
f
(
x
1
,
...
,
x
j−
1
,0,
x
j
+
1
,
is
monotone
if for all 1
...
,
x
n
)
f
(
x
1
,
...
,
x
j−
1
,1,
x
j
+
1
,
...
,
x
n
)
for all values of the remaining variables;
that is, increasing any variable from 0 to 1 does not cause the function to decrease its
value from 1 to 0.
a)
≤
Show that every circuit over the basis
Ω
mon
=
{
}
AND
,
OR
computes monotone
functions at every gate.
b) Show that every monotone function
f
(
n
)
:
n
B
→B
can be expanded as follows:
f
(
x
1
,
x
2
,
...
,
x
n
)=
x
1
f
(
1,
x
2
,
...
,
x
n
)
∨
f
(
0,
x
2
,
...
,
x
n
)
Show that this implies that every monotone function can be realized by a logic circuit
over the
monotone basis
Ω
mon
=
{
}
AND
,
OR
.
SPECIALIZED FUNCTIONS
2.14 Complete the proof of Lemma
2.5.3
by solving the recurrences stated in Equation (
2.4
).
2.15 Design a multiplexer circuit of circuit size 2
n
+
1
plus lower-order terms when
n
is even.
Hint:
Construct a smaller circuit by applying the decomposition given in Section
2.5.4
of the minterms of
n
variables into minterms on the two halves of the
n
variables.
2.16 Complete the proof of Lemma
2.11.1
by establishing the correctness of the inductive
hypothesis stated in its proof.
2.17 The
binary sorting
function is defined in Section
2.11
. Show that it can be realized
with a circuit whose size is
O
(
n
)
and depth is
O
(log
n
)
.
Hint:
Consider using a circuit for
f
(
m
)
count
, a decoder circuit and other circuitry. Is there
a role for a prefix computation in this problem?
LOGICAL FUNCTIONS
2.18 Let
f
(
n
)
(
n
+
1
)
b
member
:
B
→B
be defined below.
member
(
x
1
,
x
2
,
...
,
x
n
,
y
)=
1
x
i
=
y
≤
i
≤
n
for some 1
f
(
n
)
0 th rwe
b
and
x
i
=
y
if and only if they agree in each position.
Obtain good upper bounds to
C
Ω
f
(
n
)
where
x
i
,
y
∈B
member
and
D
Ω
f
(
n
)
member
by constructing a
circuit over the basis
Ω=
{∧
∨
¬
⊕}
.
2.19 Design a circuit to compare two
n
-bit binary numbers and return the value 1 if the first
is larger than or equal to the second and 0 otherwise.
Hint:
Compare each pair of digits of the same significance and generate three out-
comes,
yes
,
maybe
,and
no
, corresponding to whether the first digit is greater than,
equal to or less than the second. How can you combine the outputs of such a compar-
ison circuit to design a circuit for the problem? Does a prefix computation appear in
your circuit?
,
,
,
Search WWH ::
Custom Search