Logic Circuits

Introduction

Information can be represented and stored on a variety of electrical/mechanical devices. In many cases, the information relates to measurable variables such as elapsed time or total rainfall or accumulated electrical charge (for which the hourglass, raingauge, and capacitor, respectively, are suitable representation devices). But what about abstract information, such as quantities in mathematics? Here we create an analogy between something that can be stored and measured in an electrical/mechanical device and a mathematical value. For example, we can assign an equivalence between mathematical value and electrical charge. The extent to which we can operate on that electrical charge via the capacitor and our measuring instruments is the degreee to which we can perform analogous mathematical calculations.

There are problems, however, with relating mathematics to storable parameters on physical devices. Two of the more important ones are 1) measuring instruments are rarely more accurate than three decimal digits--so mathematics carried out through these devices would have intrinsic limited accuracy; 2) there is typically unrecoverable loss of information--a capacitor could leak away part of its charge, i.e., its analogous mathematical value would arbitrarily change.

But there is a solution to these problems: store mathematical values in discrete rather than analog form. Here one uses devices whose variations are limited to discrete states--typically two, e.g., on or off, positive or negative, closed or open. Then, by representing mathematical quantities in a number system having only two digits--a binary number system--any value can be represented with arbitrary accuracy by linking together a sequence of two-state devices and setting the appropriate state for each device. Information integrity in this discrete representation is better than that of analog representation because here information loss requires an arbitrary change of state of a device, not a drift in value. That is much less likely, and there are ways to correct for it.

Computers

Computers are developed to store and mathematically manipulate quantitative information. Earlier computers were analog--usually electrical or mechanical. Circuits and mechanisms were built to represent fixed mathematical problems with results appearing in the form of a final voltage or a rotation angle of a gear. The electrical and mechanical equivalents of addition, multiplication, integration, and differentiation were incorporated into these computers. Complex problems could be solved, albeit with the accuracy problems mentioned above.

Then the digital computer emerged. Here the electrical and mechanical analogies for mathematical operations are replaced by the digital manipulation of 1's and 0's--the two possible states of binary devices storing information. How does one carry out mathematics with binary devices? That is the topic of this exercise.

Binary Logic

The objective is to devise and to piece together a series of binary logic elements to effect an ultimate mathematical operation such as addition, or subtraction, or multiplication. It is necessary and sufficient to consider logic elements for which there are two binary inputs and one binary output. We consider three logic elements from which all binary logic may be constructed: the AND, OR, and NOT gates.

Problems

Note: in the problems that follow, use the circuit builder to develop your circuits. When you link to the circuit builder you will be asked to specify the number of inputs and outputs--that will be determined, of course, by the problem. You will then be presented with the circuit display having the specified number of inputs and outputs. To build your circuit, drag logic components into the circuit area. Inputs (circles) may be connected to outputs (squares) by clicking first on one, then dragging to the other and releasing the mouse button. (A single output (square) may be connected to several inputs (circles), but only one output may be connected to any input.) Once your circuit is completed you can choose either single input or all inputs. With the single input option, you can specify a particular bit configuration of inputs. Once these inputs are specified, the state (1 or 0) of each logic line will be displayed. This will give you an opportunity to find errors in your circuit. With the "all possible inputs" option, outputs for all possible inputs will be presented. This should be your final confirmation that your circuit operates correctly.

Click here to view the available logic elements, their graphic representation, and their input/output tables.

1. Confirm that each of the elementary circuits behaves as advertised. That is, use the circuit builder to establish the logic behavior of AND, NOT, OR, NAND, NOR. These will all be two-input and one output circuits (except for NOT, which will be one input and one output).

2. Using only the component NAND, create a circuit that is equivalent to the logic of an AND gate. Do the same to emulate a NOT gate. Do the same to emulate an OR gate. (If this is doable, it means that all binary logic circuitry can ultimately be generated from the single logic element NAND).

3. Using only the component NOR, see if you can create circuits equivalent to AND, OR, and NOT is you did in problem 2.

4. Using only AND, NOT, and OR produce a three-input AND circuit, i.e., the output is 0 unless all three inputs are a 1. (You don't have to use all three circuit elements.)

5. Using only AND, NOT, and OR produce a three-input OR circuit, ie., the output is 1 if any of the inputs is 1.

6. Create a two-input "adder" with two outputs: the one-digit result of the add, and the value of a "carry" bit. In binary arithmetic, 1+1=0 with a carry=1.

7. One of the more interesting public works problems is the "Superbowl" problem. At the beginning of halftime during the Superbowl, 35 million toilets are flushed almost simultaneously. The resulting loss of water pressure wreaks havoc on many municipal water systems. Here you will solve the problem for a "three toilet" system. Devise a logic circuit whose "1" inputs represent "flushes" and whose "1" outputs represent opened water-feed valves. If no more than one toilet is flushed, then that toilet's water valve opens, the others remaining closed. If more than one toilet is flushed, then all the water valves remain closed.

8. You are designing a robot to move toward a light source. Three photosensors SL, SC, and SR are mounted at the front of the robot pointing 45o to the left, straight ahead, and 45o to the right, respectively. Two wheels WL and WR are powered depending on the output of the sensors. If SL detects light, the robot is pointing too far to the right, and the right wheel WR must be powered up to turn the robot to the left. The opposite is necessary if SR receives light. If only the forward-pointing sensor SC is lit, then both wheels WL and WR should be powered to propel the robot forward. If one treats the sensors as having binary outputs, i.e., either "on" or \off", and the powered wheels as being "on" or "off", a simple logic circuit can be used to actuate the wheels under each sensor condition. Create such a logic circuit using only NAND gates, and using the least number of these.

9. This picture is a schematic diagram of a 14-pin CMOS chip that contains 4 NAND gates. Your task is to design a printed circuit board that implements the robot circuit you produced in problem 8. Using as many CMOS chips as necessary, and taking into consideration which pins constitute inputs and outputs, create the circuit by connecting the appropriate pins. But now, try to route the connections so that the "wires" don't cross one another. This is a typical problem in printed circuit design. The objective is to "etch" the circuit onto a single layer of a copper-coated circuit board which contains pin holes to accommodate the chips. (Note: this problem does not require the use of the CIRCUIT BUILDER. Just sketch out the connections between the chip(s).