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 C_in; the outputs are sum, S, and carryout, C_out. 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 C_out as functions of A, B, and C_in; (2) write logical (Boolean) expressions for Sum and C_out 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, C_out. 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).