Homework Set 1
DUE: April 5,1999, 6:30 pm
Collaboration Policy:
Unless noted otherwise, you may collaborate with other CSE599 students
on the homework. You must spend at least 15 minutes working on a problem
before seeking assistance. Collaboration means that you may discuss the
problems and make notes during the discussion, but you may not look at
other student’s work when writing up your homework. Your homework represents
your own work—the homework must show that you understand the material and
have worked as an individual on every problem. You may not divide up the
task of doing the problem sets in the interpretation of collaboration.
Late Homework Policy:
The weekly assignments are due at the beginning of class. Assignments
handed in after class will incur a 10% penalty; the penalty will increase
by 10% for each additional day late.
Reading:
Feynman pgs. 1–51, Mead papers
Please show all of your work, and remember, your solutions must be legible. The points for each problem are noted on the problem statement.
1. (10 pts) Design a 1-bit full adder using basic logic gates (ANDs,
ORs, XORs, etc.). A 1-bit full adder has 3 inputs and 2 outputs: The inputs
are two numbers A and B (each 1-bit) to be summed, and a
carry-in bit Cin; the outputs are sum, S, and
carryout, Cout. See pg. 33 of the Feynman text for a
picture of a full adder. If you’ve never designed logic circuits before,
one way to do this problem is to (1) write a truth table, showing Sum and
Cout as functions of A, B, and Cin;
(2) write logical (Boolean) expressions for Sum and Cout
from your truth table; and (3) draw logic circuits to implement the Boolean
expressions. You can find a truth table for a half adder on pg. 22 of the
Feynman text—you need to add the carry-in bit to this table to make a full
adder. See if you can come up with a simple implementations (i.e. one that
uses only a small number of logic gates). Is the adder reversible? Explain.
2. (10 pts) Design a 4-bit adder using four 1-bit full adders. A 4-bit
adder takes two 4-bit binary numbers, X, and Y, and produces
the sum, Z, and a carryout bit, Cout. Draw your
solution using boxes to represent the 1-bit adders. Can you use this approach
to make an 8-bit adder? A 16-bit adder? Finally, describe (in words)
how you might implement a multiplier using only adders and a few basic
logic gates.
3. (10 pts) Design a 1-bit full adder using CCN gates. This adder must
have the same number of inputs as it has outputs (how many inputs and outputs
are there?), so that it does not destroy information. Use the same approach
that you used for problem #1. The only difference between this problem
and problem #1 is that here you have to figure out how to implement logic
functions using CCN gates. Is this adder reversible? Explain.
4. (10 pts) Imagine a circuit that represents information using narrow
voltage pulses on a wire, rather than using static voltages. So, for example,
instead of 5Volts representing a logic "1" and 0Volts representing a logic
"0", in this system the presence of a narrow pulse at time t = 1
represents a "1", and the presence of a pulse at time t = 0 represents
a "0". Further imagine that the only circuit elements that you have are
delay lines (delays a pulse by a fixed time) and coincidence detectors
(generates a pulse output if one or more input pulses are coincident).
The coincidence detectors have adjustable thresholds, so that you can create
multiple-input devices that generate output pulses when at least 2 inputs
are coincident, or when at least 3 inputs are coincident, etc. You will
also need a timer, that generates a single pulse t = 0 (basically
a clock). Design a 1-bit full adder using only these components. (Instructors
note: The brain uses pulses to represent information, and we don’t know
how or why. This problem is an attempt to get you thinking about pulse
representations. It derives from a recent theoretical model for pulse computation
in the brain. Unfortunately, I think you’ll find the results very unsatisfying—this
may tell us that the brain doesn’t make adders, or doesn’t compute using
timing and coincidence like this, or both).
5. (10 pts) Can you construct a 1-bit full adder using only CN gates? If not, why not? (Instructors note: This same problem doomed single-layer perceptrons—the first neural networks that had well-defined learning rules).