CPSC 120: Principles of Computer Science
Fall 2002

Lab 2: Logic Circuits


IT IS POSSIBLE IN THEORY to construct a working computer entirely out of transistors (although in practice, other types of basic components are also used). Of course, in the process of assembling a computer, individual transistors are first assembled into relatively simple circuits, which are then assembled into more complex circuits, and so on. The first step in this process is to build logic gates, which are circuits that compute basic logical operations such as AND, OR, and NOT. In fact, once AND, OR, and NOT gates are available, a computer could be assembled entirely from such gates. In this lab you will work with simulated circuits made up of AND, OR and NOT gates. You will be able to build such circuits and see how they operate. And you will see how simpler circuits can be combined to produce more complex circuits.

This lab covers some of the same material as Chapter 2 in The Most Complex Machine. The lab is self-contained, but many of the ideas covered here are covered in more depth in the text, and it would be useful for you to read Chapter 2 before doing the lab.

There are exercises at the end of this lab. Some of these exercises ask you to save your work in a file. These files must be put into the "homework" directory in your account on the "math" computer. In Lab 1, you created a shortcut to this account on your Windows "M" drive. Double-click the shortcut to make your "math" account available. Once this is done, you will be able to save files directly into the "homework", or you can copy files into that directory by dragging them onto the "homework" folder.

This lab uses an applet named xLogicCircuits. To run this program, go to the "cpsc120" folder (you should have a shortcut for it), open the "Lab 2" folder, and double-click the icon named "Run xLogicCircuits".

You can also run the applet off the Web by clicking this button. But if you run xLogicCircuits this way, you will not be able to save any work you do! This is only for reading the lab on the Web:

(Sorry, your browser doesn't do Java!)

Logic and Circuits

A logic gate is a simple circuit with one or two inputs and one output. The inputs and outputs can be either ON or OFF, and the value of a gate's output is completely determined by the values of its inputs (with the proviso that when one of the inputs is changed, it takes some small amount of time for the output to change in response). Each gate does a simple computation. Circuits that do complex computations can be built by connecting outputs of some gates to inputs of others. In fact, an entire computer can be built in this way.

In the xLogicCircuits applet, circuits are constructed from AND gates, OR gates, and NOT gates. Each type of gate has a different rule for computing its output value. Circuits are laid out on a circuit board. Besides gates, the circuit board can contain Inputs, Outputs, and Tacks. Later, we'll see that circuits can also contain other circuits. All these components can be interconnected by wires. To the left of the circuit board in the applet is a pallette. The pallette contains components available to be used on the circuit board. You can't usually see all the components at once, but there is a scroll bar that allows you to scroll through all the components on the pallette. The following illustration shows the part of the pallette that contains the six standard components, along with some comments and a small sample circuit:

The standard component pallette

One thing you should note: Wires cannot connect to each other except at Tacks. Just because two wires cross each other on the circuit board does not mean that they are connected. Effectively, the real circuit is three-dimensional. One wire goes over the other, so they don't actually touch. Wires can only carry signals between components such as gates, Tacks, Inputs, and Outputs.

The xLogicCircuit applet should start up showing a sample circuit called "Basic Gates." At the top of the circuit board are an AND gate, an OR gate, and a NOT gate. The gates are connected to some Inputs and Outputs. A more complicated circuit built from several gates occupies the bottom of the circuit board.

To see how the circuit works, you have to turn on the power. Power to the circuit board is turned on and off using the "Power" checkbox below the circuit board. The power is ON when the box is checked. Click on the Power checkbox now to turn on the power. (Why does the wire leading from the NOT gate come on when you do this?) When the power is on, you have control over the Inputs on the circuit board: you can turn an input ON and OFF by clicking on it. The circuit does the rest: signals from the Inputs propagate along wires, through gates and other components, and to the Outputs of the circuit. Try it with the sample circuit. If you have a problem, make sure the power is on and that you are clicking on an Input, not an Output.

You should check that the AND, OR, and NOT gates at the top of the circuit board have the expected behavior when you turn the inputs ON and OFF. You can also investigate the circuit in the bottom half of the logic board. Below the circuit board, to the left of the Power switch, you'll find a pop-up menu that can be used to control the speed at which signals propagate through the circuit. The speed is ordinarily set to "Fast." You can use the pop-up menu to change the speed to "Moderate" or "Slow" if you want to watch the circuit in slow motion. (For the most part, though, you probably want to leave the speed set to Fast.)

Logic gates and logic circuits are associated with mathematical logic, which is the study of the computations that can be done with the logical values true and false and with the logical operators and, or, and not. This association comes about when we think of ON as representing true and OFF as representing false. In that case, AND, OR, and NOT gates do the same computations as the operators and, or, and not.

Mathematical logic uses Boolean algebra, in which the letters A, B, C, and so on, are used to represent logical values. Letters are combined using the logical operators and, or, and not. For example,

(A and C) or (B and (not C))

is an expression of Boolean algebra. As soon as the letters in an expression are assigned values true or false, the value of the entire expression can be computed.

Every expression of boolean algebra corresponds to a logic circuit. The letters used in the expression are represented by the Inputs to the circuit. Each wire in the circuit represents some part of the expression. A gate takes the values from its input wires and combines them with the appropriate word -- and, or, or not -- to produce the label on its output wire. The final output of the whole circuit represents the expression as a whole. For example, consider the sample circuit from the applet. If the inputs are labeled A and B, then the wires in the circuit can be labeled as follows:

Circuit labeled with logical expressions

The circuit as a whole corresponds to the final output expression, (A and (not B)) or (B and (not A)). This expression in turn serves as a blueprint for the circuit. You can use it as a guide for building the circuit. The expression given earlier, (A and C) or (B and (not C)), corresponds to another sample circuit shown in the illustration above -- provided you label the inputs appropriately.

To sum up, given any expression of Boolean algebra, a circuit can be built to compute that expression. Conversely, any output of a logic circuit that does not contain a "feedback loop" can be described by a Boolean algebra expression. The relation between circuits and logic is a powerful association that is useful in understanding and designing logic circuits. (Note: Feedback occurs when the output of a gate is connected through one or more other components back to an input of the same gate. Circuits with feedback are used in memory circuits, which you'll be seeing later in the lab.)

Building Circuits

You can build your own circuits in the xLogicCircuits applet. Click on the "Iconify" button at the bottom of the applet. This will put away the "Basic Gates" circuit, by turning it into an icon on the pallette. You'll have a clear circuit board to work on. As an exercise, try to make a copy of the sample circuit shown aabove, which corresponds to the Boolean expression

(A and C) or (B and (not C)).

To add a component to your circuit, click on the component in the pallette, hold down the mouse button, and use the mouse to drag the component onto the circuit board. Make sure you drag it completely onto the board. If you want a gate that is facing in a different direction, you have to rotate the gate in the pallette before you drag it onto the circuit board.

Once some components are on the board, you can draw wires between them using the mouse. Every wire goes from a source to a destination. To draw a wire, move the mouse over the source, click and hold the mouse button, move the mouse to the destination, and release the button. You must draw the wire from source to destination, not the reverse. If you release the mouse button when the wire is not over a legal destination, no wire will be drawn. When there are two possible destinations in one component -- such as the two inputs of an AND or OR gate -- make sure that you get the wire connected to the right one.

Circuit Inputs are valid sources for wires. So are Tacks. So are the outputs of gates. Valid destinations include circuit Outputs, inputs of gates, and Tacks. You can draw as many wires as you want from a source, but you can only draw one wire to a destination. (This makes sense because when the circuit is running, a destination takes its value from the single wire that leads to it. On the other hand, the value of a source can be sent to any number of wires that lead from it.)

Once a component is on the board, you can still move it to a new position, but you have to drag it using the right mouse button. Alternatively -- if you have a one-button mouse, for example -- you can drag a component by holding down the control key as you first press the mouse button on it.

You can delete components and wires that you've added by mistake. Just click on the component or wire to hilite it. Then click on the "Delete" button at the bottom of the applet. The hilited item will be deleted from the circuit board. If you delete a component that has wires attached, the attached wires will also be deleted along with the component.

If you delete an item or modify the circuit in some other way, you get one chance to change your mind. You can click on the "Undo" button to undo one operation. Only the most recent operation can be undone in this way.

There is one shortcut that you might find useful, if you like using Tacks. You can insert a Tack into an existing wire by double-clicking on the wire. If you double-click and hold the mouse down on the second click, you can drag the tack to a different position. (However, some versions of Java might not support double-clicks.)

After you build the practice circuit, you can clear the screen, since you won't need that circuit again in the rest of the lab. However, you'll get more practice building circuits in the Exercises at the end of the lab.

Complex Circuits and Sub-circuits

In order to have circuits that display structured complexity, it is important to be able to build on previous work when designing new circuits. Once a circuit has been designed and saved, it should be possible to use that circuit as a component in a more complex circuit. A lot of the power of xLogicCircuits comes from the ability to use circuits as components in other circuits. Circuits used in this way are called sub-circuits. A circuit that has been saved as an icon in the pallette can simply be dragged into another circuit. (More exactly, a copy of the circuit is created and is added to the circuit board. The copy is a separate circuit; editing the original will not change the copy.) This ability to build on previous work is essential for creating complex circuits.

You can open a circuit from the pallette to see what's inside or to edit it. Just double-click the circuit. The icon will be removed from the pallette and the circuit will appear on the circuit board. At the same time, any circuit that was previously on the circuit board will be iconified and placed on the pallette. (By the way, you can change the name of the circuit on the circuit board by editing the text-input box at the top of the applet. This box contains the name that appears on the iconified circuit.)

When you run xLogicCircuits for this lab, it reads a file of example circuits ("examples.txt") and adds them to the palette. One of these circuits is called "Two or More". Open this circuit now by double-clicking on it. The circuit has three inputs. It turns its output ON whenever at least two of its inputs are ON. Try it. (Click on the inputs to turn them ON and OFF -- and don't forget to turn the Power on first!)

As a simple exercise in building circuits from sub-circuits, use the "Two or More" circuit as part of a "At Most One" circuit. You want to build a circuit with three inputs that will turn on its output whenever zero or one of its inputs is on. Notice that this is just the opposite behavior from the "Two or More" circuit. That is, "At Most One" is ON whenever "Two or More" is not ON. This "logical" description shows that the "At Most One" circuit can be built from a NOT gate and a copy of the "Two or More" circuit. Begin by re-Iconifying the "Two or More" circuit, then drag a NOT gate and a copy of "Two or More" onto the empty circuit board. Add Inputs, Outputs, and wires as appropriate, then test your circuit to make sure that it works. If you like, you can give it a name and turn it into an icon.

As another example of circuits that use sub-circuits, open the "4-Bit Adder" circuit from the pallette. You'll see that it contains several copies of a sub-circuit called "Adder." It's possible to look inside one of these circuits: Just click on the double-click the adder circuit. This does not remove the main circuit from the board -- it just lets you see an enlarged part of it. When you shrink the sub-circuit back down to its original size, the main circuit is still there. (Do this by clicking the "Shrink" button at the bottom of the applet.) In this case, you'll see that an "Adder" circuit contains two "Half Adder" sub-circuits, which you can enlarge in their turn, if you want.

Circuits and Arithmetic

The "4-Bit Adder" circuit is an example of a logic circuit that can work with binary numbers. Circuits can work with binary numbers, as long as you think of ON as representing the binary value 1 (one) and OFF as representing the value 0 (zero). The "4-Bit Adder" can add two 4-bit binary numbers to give a five digit result. Here are some examples of adding 4-bit binary numbers:

      1011       1111       1111       1010       0111       0001
      0110       0001       1111       0101       1010       0011
     -----      -----      -----      -----      -----      -----
     10001      10000      11110      01111      10001      00100

The answer has 5 bits because there can be a carry from the left-most column. Each of the four "Adder" circuits in the "4-Bit Adder" handles one of the columns in the sum. You should test the "4-Bit Adder" to see that it gets the right answers for the above sums. The two four-bit numbers that are to be added are put on the eight Inputs at the top of "4-Bit Adder". The sum appears on the outputs at the bottom, with the fifth bit -- the final carry -- appearing on the output on the right. You should observe that it takes some time after you set the inputs for the circuits to perform its computations.

Circuits and Memory

Computers store and process information. Circuits can be used to process information because they can do things like addition. To store information, you need a circuit that can "remember" in the sense that you can put some data in the circuit, and the data will stay there until you deliberately change it by storing a new value. Memory circuits can be used to hold input data or data that is generated by some computation. The memory circuit can hold the data until it is needed for later processing.

The sample circuit named "One Bit Memory" is a memory circuit that can store one bit of data. It has two inputs and one output:

one-bit memory

The Data-out output shows the number (zero or one) that is stored in the memory circuit. You can tell which value is stored by checking the output. The inputs are used together to store data in the circuit. The Data-in input specifies which number (zero or one) is to be stored. The Load-data wire must be turned ON and OFF to actually put the number into the circuit. As long as Load-data is OFF, the number in the circuit won't change, no matter what happens to the Data-in wire. That is:

If you look inside the One Bit Memory, you will see a "feedback loop" at the right-hand side of the circuit. The number that is stored in the circuit is effectively recorded in this feedback loop. However, you don't really need to know how this circuit works on the inside. You only need to know how it is used.

Exercises

The following exercises are due next Wednesday, September 18. Exercises 1, 3, 4, and 5 ask you to create circuits. You should create these circuits using the xLogicCircuits applet and save them in the "homework" directory in your "math" account. You can use the "Save" button in xLogicCircuits to save your work. Give your files reasonable names, such as "Lab1Ex3". All of the exercises require you to do some writing. You should write up your answers, either by hand or on computer, and them in in class next Wednesday. Include the names of your files in your write-up. Remember that you have the option of working on the lab with another student.

Exercise 1: Consider the following three Boolean algebra expressions:

(A and (not B)) or (B and C)

A and (not (B and (not C)))

(not (A or B or C)) or (A and B and C)

For each expression, build a logic circuit that computes the value of that expression. (They can be on the same circuit board or on three separate circuit boards.) Write a paragraph that explains the method that you apply when you build circuits from expressions. (One note: To build a circuit for an expression of the form (X and Y and Z), you should insert some extra parentheses, which don't change the answer. Think of the expression as ((X and Y) and Z), and build the circuit using two AND gates.) Remember that the parentheses are important!

Exercise 2: Given a logic circuit that does not contain any feedback loops, it is possible to find a Boolean algebra expression that describes each output of that circuit. Open the circuit called "For Ex. 2", which is one of the sample circuits in the applet's pallette. This circuit has four inputs and three outputs. Assuming that the inputs are called A, B, C, and D, find the expression that corresponds to each of the three outputs. (You will have three different expressions -- one for each output.) Also write a paragraph that discusses the procedure that you apply to find the Boolean expression for the output of a circuit.

Exercise 3: One of the examples in this lab was a circuit called "Two or More", which checks whether at least two of its inputs are on. Consider the problem of finding a similar circuit with four inputs. The output should be on if any two (or more) of the inputs are on. A circuit that does this can be described by the Boolean expression:

(A and (B or C or D)) or (B and (C or D)) or (C and D)

Based on this expression, construct a "Two or More" circuit with four inputs. Try to understand where this expression comes from. Why does it make sense? (Hint: Think of two cases, one case where the input A is ON, and the other case where the input A is OFF.) Write a paragraph explaining this. The form of this expression can be extended to handle circuits with any number of inputs. Write down a logical expression that describes a circuit with five inputs that turns on its output whenever two or more of the inputs are on. (You do not have to build the 5-input circuit!)

Exercise 4: The One Bit Memory circuit can hold a single bit of information. Suppose you want to store a four-bit binary number. You can build a Four Bit Memory from four One Bit Memories, provided you wire them together correctly. Build a Four Bit Memory. Your circuit should have four Data-in wires, four Data-out wires, and a single Load-data wire. (The Load-data wire loads data into all four One Bit Memories at the same time.) In your write-up, give instructions for using your circuit to store a four-bit number. Also, briefly explain how you could build a memory circuit for storing 16 bits, 32 bits, or any other number of bits.

Exercise 5: Memory circuits are used to store the results of computations so that they are available for use in later computations. This can be done by attaching the inputs of a memory circuit to the outputs of a computational circuit. This lets you store the results of a computation for later use. Build a circuit that can add two 4-bit binary numbers and store the result (without the carry bit) in a 4-bit memory circuit. You can build the circuit from a copy of the 4-bit Adder circuit and a copy of the Four Bit Memory circuit from Exercise 4. Write a paragraph that explains the design of your circuit and how it is used.

Exercise 6: Write a short essay (of several paragraphs) that explains how sub-circuits are used in the construction of complex circuits and why the ability to make and use sub-circuits in this way is so important.

--David Eck (eck@hws.edu), Fall 2002