Assignment for the Next Lab

• Read pp. 242-251, pp. 260-271. Focus on the concept of a Turing Machine.
• For discussion, read the articles listed on the schedule on the class web site: http://www.cs.swarthmore.edu/~mirarchi/schedule.html and write a short reaction paper.

Lab 11 Instructions

1. Build, test, and save a three-way AND circuit which accepts three inputs and produces an output of 1 only when all three inputs are 1; otherwise it produces an output of 0.

2. Build, test, and save a four-way OR circuit, which accepts four inputs and produces an output of 1 if at least one of the inputs is 1, and 0 if all of the inputs are 0. To do this, translate the logical expression (P OR Q) OR (R OR S) into a circuit.

3. Build, test, and save a three-way parity circuit . This circuit has three inputs and one output. If an even number of inputs are 1, then the output is 1, and if an odd number of inputs are 1, then the output is 0. If P, Q, and R represent the inputs, then the logical expression

   [P AND Q AND (NOT R)]
   OR [P AND (NOT Q) AND R]
   OR [(NOT P) AND Q AND R]
   OR [(NOT P) AND (NOT Q) AND (NOT R)]

   represents the output. Use the three-way AND gate and four-way OR gate as subcircuits to design a circuit which represents the above expression.

4. Build, test, and save a majority circuit , which has three inputs and one output. The output is 1 if the majority of the inputs are one (i.e. if two or more inputs are 1), and returns 0 if the majority of the inputs are 0 (i.e. if two or more inputs are 0). To build this circuit, first build a logical expression which has the following truth values:

   P	Q	R	Majority(P,Q,R)
   1	1	1	1
   1	1	0	1
   1	0	1	1
   1	0	0	0
   0	1	1	1
   0	1	0	0
   0	0	1	0
   0	0	0	0

   Construct the logical expression using the algorithm which was presented last class. That is:

   1. For each row of the truth table where the desired result is 1
      • Look at the value of each variable in that row.
      • If the variable has value 1, take the variable; if the variable has value 0, take the negation of the variable. Then connect these three variables (or their negations) using AND's.

   2. Connect each of the above expressions together using OR's.

   Once you have found a logical expression which represents the Majority operator, build the corresponding circuit using the three-way AND and four-way OR operators you built.

   Save your circuit.

5. Open the two-way multiplexor circuit which is in the "saved circuits" folder of module 6. Test the circuit on different inputs so that you understand how it works.

6. A two-way multiplexor is a switch which allows you to select which of two inputs a or b will be the output. It is this type of circuit which gives the computer its programmability. We can think of a program as setting various switches (such as the MUX above) so that different outputs are obtained.

   Add the 2-way MUX as a subcircuit. Then use the MUX along with the majority and parity circuits to design a circuit which has 3 inputs and one output. Depending on the setting of the MUX, the output will be either

   1. The majority the inputs, or
   2. The parity of the inputs

   Call one of us over and show us your circuit.

   ---

   DigSim 2.5: A Digital Logic Simulator for the Macintosh

   DigSim is a program for designing and experimenting with digital circuits. It is useful for both learning digital logic and for testing advanced circuit ideas. When DigSim starts up, a palette of circuit elements and an untitled circuit window will appear. You can drag any of the elements over to the circuit window to add them to the circuit. To remove an element from the circuit window, drag it back to the palette. You can move around elements which are already in your circuit window by dragging them.

   The palette of circuit elements also contains a soldering iron for connecting components and a pair of wire cutters for cutting connections. The Tools menu allows you to choose between them. When the soldering iron is selected, clicking on a lead out of an element and dragging to another lead will connect them with a wire as long as this does not connect two output leads together. When the wire cutters are selected, clicking on a wire where it comes out of the element (clicking in the middle of the wire will not work) will cut it out of the circuit. Clicking on a blank piece of screen and dragging will create a selection box. All the circuits in this box can be dragged together around the screen, and this group of circuits can be copied, cut and pasted.

   Input switches and output lights are used to control the circuit after it is built. Clicking on an input switch will toggle its state from 0 to 1 or 1 to 0, and this value will be fed to the gates connected to it. Output lights will light up if they are connected to a 1 and stay dark if connected to a 0.

   After you have built a circuit and saved it, its name will appear under the Sub-Circuits menu. You can now use that circuit as a sub-circuit inside any other circuit so that you can have much more complicated building blocks than are in the palette. To use a subcircuit which you have saved, simply select the sub-circuit you want from the Sub-Circuits menu, and a box labeled with the sub-circuit name will appear in the middle of the window. This box will have one input lead for every input switch the original circuit had and an output lead for every output light. It can now be used just like any circuit element. Double clicking on the box will open a circuit window showing the innards of the sub-circuit.

   ---