H U S E T T S I N S T I T U T E O F T E C H N O L O G Y
6.004 Fall 2000
- 1 -
Problem Set #3 Solutions
M A S S A C H U S E T T S I N S T I T U T E O F T E C H N O L O G Y
DEPARTMENT OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE

6.004 Computation Structures

Fall 2000

Problem Set #3 Solutions

Issued Tuesday, 10/3/00

Problem 1. Quickies (2 Points)


(A) (0.4 Points) No. If G
pd
is less than 0, then in some cases the output will transition to a new
logic level while the input is still at the previous logic level, violating the functional
specification of the device. Given a certain set of inputs, we expect the device G to return
a certain output. But if G
pd
is less than 0, there will be occasions when the output changes
its value before there is any change on the input. G
pd
cannot be less than 0.

No. If G
cd
is less than 0, then the output will become invalid while the input is still valid.
This would violate the static discipline for combinational deviceswe could no longer
guarantee a valid output whenever the inputs are valid. G
cd
cannot be less than 0.

(B) (0.4 Points) No. Suppose we have an input waveform with an almost instantaneous
change in value (such that the rise time and fall time are close to zero). The contamination
delay tells us how long we can expect the output to maintain its previous value after the
input has changed. The propagation delay tells us how soon we can expect to see the new
value on the output after the input has changed. If G
cd
is greater than G
pd
, we will have a
time during which the output is expected to maintain both the previous value and the new
value simultaneously. This is impossible; therefore, G
cd
cannot be greater than G
pd
.

(C) (0.4 Points) No. G
pd
must be greater than G
cd
. Taking all factors into account (possible
input waveforms, mfg variations, power supply, temperature, ...) draw the fastest output
transition a G device is capable of. Compute the slew rate of the output (volts/sec) as it
goes between V
OL
and V
OH
.

Now construct the following input waveform: draw a line with the same slew rate as the
output had that passes through V
IL
just as the output passes through V
OH
. (All this assumes
an inverting device, but the argument can be changed trivially if its a non-inverting
device.) Using this input waveform, G
cd
is 0. Now consider how long it will take for the
input to rise to V
IH
and the output to fall to V
OL
. Remember that both the input and output
are changing at the same rate. Since V
OH
- V
OL
is greater than V
IH
- V
IL
(because of noise
margins), the input will reach V
IL
before the output reaches V
OL
. This means that G
pd
> G
cd
.

(D) (0.1 Points) Assume a non-trivial version of the circuit C, in which all 4 inputs and all 32
G devices are used in calculating the output. The longest possible path that we can create,
using the 4 inputs and 32 G devices, is a path through all 32 G devices. 6.004 Fall 2000
- 2 -
Problem Set #3 Solutions
G
G
G
G
. . . . .
In
In
In
In 0
1
2
3
32 devices in series => tpd = 32Gpd



The configuration in which the longest path is shorter than in all other configurations is as
follows:

G
G
G
G
G
G
G
G
G
G
G
G
G
G
G
G
G
G
G
G
G
G
G
G
G
G
G
G
G
G
G
G


The longest path in this case is through 6 G devices. So our bounds on C
pd
are:

PD
PD
PD
G
C
G
32
6


If you dont assume that all 32 G devices and all 4 inputs are used, then an acceptable
answer is:

PD
PD
PD
G
C
G 32



(E)
(0.1 Points) The shortest possible path in a configuration of 32 G devices is a path through
one G device. The configuration in which the shortest path is longer than it is in any other
configuration would be as follows: 6.004 Fall 2000
- 3 -
Problem Set #3 Solutions
G
G
G
G
G
= 31G
cd
cd
t
In
In
0
1
In
2
In
3
. . . . .


The shortest path in this case is through 31 G devices. So the bounds on C
cd
are:


CD
CD
CD
G
C
G 31


If you dont assume that all 4 inputs are used, then an acceptable answer is:


CD
CD
CD
G
C
G 32


(F)
(0.1 Points) 8 input lines run through the decoder: one for each input, and one for the
inverse of each input.

(G) (0.1 Points) 2
4
= 16 lines run from the AND plane to the OR plane.

(H) (0.1 Points) 16. There is one programmable junction for each signal line coming from the
AND plane.

(I)
(0.1 Points) The sum-of-products expression for the optimized CPLA may not use all the
possible inputs (and their inverses). Only those input variables that show up in the
optimized CPLA expression need to be run as input lines through the decoder. This will be
different from part (F) if some inputs are not used in the optimized sum-of-products
expression.

(J)
(0.1 Points) The number of lines connecting the AND and OR planes will be equal to the
number of product terms in the optimized sum-of-products expression for the CPLA. This
may be less than the answer from part (G), if the optimized sum-of-products expression
has fewer product terms than the original expression.

(K) (0.1 Points) This answer is the same as the answer to part (J). The number of
programmable junctions needed is equal to the number of product terms in the optimized
sum-of-products expression for CPLA. This could be smaller than the answer from part
(H), for the same reasons explained in part (J).


Problem 2. Combinational workout (1.5 Points)

(A) (0.3 Points) Karnaugh map for Z:
6.004 Fall 2000
- 4 -
Problem Set #3 Solutions
00
01
11
10
AB
0
0
0
1
1
1
1
1
1
0
C


(B) (0.3 Points) Z = B + (A C)

(C) (0 Points) This problem will not be graded. We do not know of a way to implement Z with
6 transistors. It is possible with 8, however.

(D) (0.3 Points) There is no way to construct an inverter using a Z gateit is a strictly positive
logic gate. Therefore, a Z gate is not universal.

(E) (0.3 Points) If A=0 and B=0, then Z=0 regardless of the value of C. Thus, if our
implementation of Z is lenient, switching C repeatedly between 1 and 0 will not affect Z,
since A=0, B=0 is enough to determine the value of Z.

(F)
(0.3 Points) There are two acceptable answers for this problem:


If we look only at the case when A=0 and B=0, then the original PLA circuit is lenient:
regardless of the value of C, when A=0 and B=0 the output line is never pulled down,
because there are no pull-downs which affect the output when either
C
B
A
or
C
B
A

is true. Thus, no matter what we do with C, Z will remain a constant 0.

However, if we look at all possible inputs, the original PLA circuit is not lenient.
Consider the case when A and B are fixed at one, and C is switched repeatedly between 0
and 1: the rows in the PLA corresponding to
C
B
A
and
C
B
A
will be alternately
pulled high. When both signals are in transition, it causes a glitch on the output line.

(G) (0 Points) This problem will not graded, since it refers to the answer to part (C).

If you implemented Z using the minimal sum-of-products expression from part (B) using
lenient gates, then the circuit would be lenient. As long as only one input is changed at a
time, the output will never have a glitch.


Problem 3. Mux Trickery (2 Points)

(A) (0.5 Points) t
pd
= 21ns 6.004 Fall 2000
- 5 -
Problem Set #3 Solutions
F
A
B
C
F
A
B
C
0
1
1
0
B
B
C
C
A


(B) (0.8 Points) Yes, you can do better with more F modules and muxes. If you use only 2-
input you would reach the following solutions. Using muxes with more than 2 inputs is
also acceptable for this problem.

With 4 F modules and 3 muxes, t
pd
= 7ns :

0
1
F
A
B
C
F
A
B
C
0
1
B
F
A
B
C
F
A
B
C
0
1
B
0
C
C
1
0
1
1
0
1
0
C
C
A


With 8 F modules and 7 muxes, t
pd
= 3ns :

0
1
0
1
0
1
F
A
B
C
0
0
1
F
A
B
C
0
1
1
C
0
1
F
A
B
C
0
1
1
F
A
B
C
1
1
1
C
B
0
1
0
1
F
A
B
C
0
0
0
F
A
B
C
0
0
1
C
0
1
F
A
B
C
0
0
1
F
A
B
C
0
1
1
C
B
A
6.004 Fall 2000
- 6 -
Problem Set #3 Solutions

(C) (0.5 Points) You dont need the 8 F modules if you use 7 muxes. Since the 8 F modules
would all have constant inputs, the outputs of the F modules would be constant as well.
Therefore, the inputs to the muxes can just be tied to constant ones and zeroes, depending
on the value of F for the given set of inputs. The muxes are essentially implementing the
truth table for F, so the actual F module is no longer necessary.

(D) (0.2 Points) A k-input combinational device can be implemented with a 2
k
-input mux by
simply tying all the multiplexer inputs to the appropriate values, using the k system inputs
as the selector bits for the multiplexer.


Problem 4. Gray Matters (2 Points)

(A) (1 Point) To convert a 3-bit gray code sequence into a sequential binary sequence, you can
use the following algorithm:


1) For each number whose most significant bit is a 1, flip the second bit.

2) For each number whose second bit is a 1, flip the last (least significant) bit

This can easily be implemented using two xor gates:

G
G
G
B
B
B
2
2
1
1
0
0


(B) (1 Point) To convert a 3-bit binary sequence to Gray code, you reverse the algorithm in
part (A):


1) For each number whose second bit is a 1, flip the last (least significant) bit

2) For each number whose most significant bit is a 1, flip the second bit.

This can also