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