CS61C $ummer 2017 Lab 6 - Introduction to Logisim (not Logism). It's short for "logic simulator." It doesn't mean "discrimination against logs."

ONLINE QUEUE

Hi everyone, we are going to be trying out the online queue that CS61A uses for their lab checkoffs and office hours and stuff. Please verify that you are able to log in to this website: http://61c-queue.app.cs61a.org. If not, please fill out the form linked at the very bottom of this Piazza post, and raise your hand to request checkoffs today! Thanks!

Goals

• Get up close and personal with Logisim

Grabbing the lab files

Copy the lab files from the instructional servers to your lab account with

$ cp -r ~cs61c/labs/06/ ~/labs/06/

Alternatively, secure-copy (scp) them from the instructional servers to your own laptop with

$ scp -r cs61c-xxx@hive10.cs.berkeley.edu:~cs61c/labs/06/ ~/YOUR_FILEPATH

And if you want to secure-copy them back to your class account:

$ scp -r ~/YOUR_FILEPATH/06 cs61c-xxx@hive10.cs.berkeley.edu:~/YOUR_LABACCT_FILEPATH

Preparation

Launch the Logisim application to begin. To do this, type 'logisim' from the terminal while logged on to one of the hive machines.

You can learn about Logisim beyond the scope of this lab (or download it to use at home) from the Logisim website. Like with MARS, Logisim can be a bit buggy; if the program starts to act strangely, it is possible that something internally crashed, so the best solution would be to turn it off and turn it on again.

Exercises

Exercise 0: The Basics (Warm-Up)

We'll begin by creating a very simple circuit just to get the feel for placing gates and wires.

1. Start by clicking the "AND gate" button. This will cause the shadow of an AND gate to follow your cursor around. Click once within the main schematic window to place an AND gate.
2. Click the square-shaped "Input Pin" button. Now, place two input pins somewhere to the left of your AND gate.
3. Click the roundly-shaped "Output Pin" button. Then place an output pin somewhere to the right of your AND gate. Your schematic should look something like this at this point:
   

4. Click the "Select tool" button. Click and drag to connect the input pins to the left side of the AND gate. This will take several steps, as you can only draw vertical and horizontal wires. Just draw a wire horizontally, release the mouse button, then click and drag down starting from the end of the wire to continue vertically. You can attach the wire to any pin on the AND gate on the left side. Repeat the same procedure to connect the output (right side) of the And Gate to the LED. After completing these steps your schematic should look roughly like this:
   

   You can also change the number of inputs of the "AND gate" by clicking it using the select tool and changing the properties in the bottom left segment of the window. This can also be done before you put down the component.

5. Finally, click the "Poke" tool and try clicking on the input pins in your schematic. Observe what happens. Does this match with what you think an AND Gate should do? (Your answer should be a resounding "yes.")

Exercise 1: Sub-Circuits

Just as C programs can contain helper functions, a schematic can contain subcircuits. In this part of the lab, we will create several subcircuits to demonstrate their use.

1. Create a new schematic (File->New) for your work.
2. Create a new subcircuit (Project->Add Circuit ). You will be prompted for a name for the subcircuit; call it NAND.
3. In the new schematic window that you see create a simple NAND circuit with 2 input pins on the left side and an output pin on the right side. Task: do this without using the built-in NAND gate from the Gates folder (i.e. only use the AND, OR, and NOT gates provided next to the selection tool icon). Taking your rights away already...
4. Naming stuff: you can change the labels for the inputs and output by selecting the input/output using the select tool and changing the property "Label" in the bottom left of the window. Task: in this subcircuit, name the two inputs "Alice" and "Bob," and name the output "Nancy."
5. Using your subcircuit: Go back to your "main" schematic by double-clicking "main" in the circuit selector at the left of the screen. Your original (blank) schematic will now be displayed, but your NAND circuit has been stored.
6. Now, single click the word "NAND" in the dropdown list. This will tell Logisim that you wish to add your "NAND" circuit into your "main" circuit.
7. Try placing your NAND circuit into the "main" schematic. If you did it correctly, you should see a gate with 2 input pins on the left and one output pin on the right. Try hooking input pins and output pins up to these and see if it works as you expect. Again, your response to the preceding sentence should be a tremendous "yes."
8. Repeat these steps to create several more subcircuits: NOR, XOR, 2-to-1 MUX, and 4-to-1 MUX. Do not use any built in gates other than AND, OR, and NOT. However, once you've built a subcircuit, you may use it to build others.

Hint: NOR and XOR should be a little easier than the two MUXes. First of all, make sure you know what a MUX (multiplexor) does. Here's a slide from last week to refresh you on that if you need it. BEFORE YOU PROCEED: know the answer to the following question. How many input bits are required for a 2-to-1 MUX?. If your answer is "2", then you would be wrong. Try drawing the truth table to see why.

Once you've done the 2-to-1 MUX, think about how it could be useful in creating the 4-to-1 MUX. Consult the same slideshow as above for some hints as to how this might work...

Exercise 2: Storing State in a Register

Let's implement the circuit we've been talking about in lecture that increments a value ad infinitum. That's fancy talk for "until you tell it to stop." The difference between this circuit and the circuits you've built for lab so far is that you need some registers. The following will show you how to add registers to your circuit.

1. Create a new subcircuit (Project->Add Circuit). Name this new subcircuit, AddMachine.
2. Load in the Arithmetic Library if it is not already loaded (go to Project->Load Library->Built in Library and select "Arithmetic"). This library contains elements that will perform basic mathematical operations. When you load the library, the circuit browser at left will have a new "Arithmetic" folder. Now you may use the dropdown menus on the left (libraries).
   

3. Select the adder subcircuit from the "Arithmetic" library and place the adder into your AddMachine subcircuit.
4. Load in the Memory Library if it is not already loaded (go to Project->Load Library->Built in Library and select "Memory"). This library contains memory elements used to keep state in a circuit. A new "Memory" folder will appear in the circuit browser.
5. Select the register from the "Memory" folder and place one register into your subcircuit. Below is an image diagramming the parts of a register.
   

6. Connect a clock to your register. You can find the clock circuit element in the "Wiring" folder in the circuit browser.

7. Connect the output of the adder to the input of the register and the output of the register to an input of the adder. You should've made a rectangle (or some other enclosed box shape) with your wires.

   Note: You may get a "Incompatible widths" error when you try to connect components. This means that your wire is trying to connect two pins together with different bit widths. If you click on the adder with the "Selection" tool, you will notice that there is a "Data Bit Width" property in the bottom left field of the window. This value determines the number of bits each input and output the adder has. Change this field to 8 and the "Incompatible widths" error should be resolved.

8. Wire an 8-bit constant 1 to the second input of the adder. You can find the "constant" circuit element in the "Wiring" library.

9. SPOILERS BELOW. BEWARE. You really should try to be comfortable with performing the preceding sequence of steps. It'll be really good practice for familiarizing yourself with Logisim. Nonetheless, below will appear a diagram of exactly what you should have for the addMachine. Task: add two (2) output pins to your circuit so that you may monitor

   1. What comes out of the adder
   2. What comes out of the register
   Make sure the outputs have bit-widths of 8 bits. Also make sure to label them so you know which one represents which. Thus, by the end, your circuit should look like as follows, or equivalent:
   

Now let's test your addMachine by using it as a subcircuit. Notice that using something as a subcircuit is like abstracting the bitwise logic away into a black box.

1. Go back to the "main" subcircuit by double clicking on "main" in the circuit browser.
2. Single click on your "AddMachine" circuit to select it.
3. Random task: change the "Facing" property to another direction. Any circuit with the "Facing" property can be rotated to accomodate wires as you need them. This will definitely be useful when you do project 3.
4. Place your AddMachine subcircuit into the main subcircuit.
5. Connect output pins to the AddMachine subcircuit. Output pins are ordered top to bottom, left to right. Thus, if you followed the schematic above, then the top pin on the right side outputs the value of the adder, and the bottom pin is the output of the register.
6. Here's an important note about viewing subcircuits that you should take care to understand!

   Right click on your AddMachine subcircuit, and select "View AddMachine". This is the ONLY method to preserve state (i.e. keep register values at its current value) while viewing a subcircuit. Please note that double-clicking on the circuit at the circuit browser at left makes logisim think you want to edit the circuit instead of just checking what state the circuit has in the main circuit.

   Note: You can use Simulate->Go In To State->*Circuit Name*, but that allows you go into the first circuit of that type. If you placed two addMachine circuits down, it only takes you to the first addMachine circuit you put down.

7. Initialize the register value to 1. You can do this by first, clicking on the register value with the poke tool. Then, type the hex value in.
8. To return to the main circuit while preserving state, go to Simulate->Go Out To State->main. Shortcut! Shortcut! Alternatively, you can hold the Command key (control on windows) and press the up arrow.
9. Now start running your circuit by going to Simulate->Ticks Enabled (or Command/Control + K). Your circuit should now be outputting a counter in binary form.
10. If you want to run your circuit faster, you can change the tick frequency in Simulate->Tick Frequency.

Exercise 3: FSMs to digital logic

Now we're ready to do something really cool (lol); translate a FSM into a digital logic circuit.

We're going to implement the following FSM:

If two ones in a row or two zeroes in a row have ever been seen, output zeros forever. Otherwise, output a one.

1. Here's a nontrivial fact: the FSM is implemented by the following diagram:

   The leftmost bubble is the start state, the two intermediate states represent where you are if you've seen a 0 or a 1 most recently, and the rightmost state represents where you are if you've seen consecutive matching values. Notice that it only goes back to itself.

2. Observe that the following is a truth table for the FSM:

   st1	st0	input	|	next st1	next st0	output
   0	0	0	|	0	1	1
   0	0	1	|	1	0	1
   0	1	0	|	1	1	0
   0	1	1	|	1	0	1
   1	0	0	|	0	1	1
   1	0	1	|	1	1	0
   1	1	0	|	1	1	0
   1	1	1	|	1	1	0

3. We've provided you with a starter Logisim circuit to start out called FSM.circ.

4. First of all, what the heck is going on in this thing? Oh! I'm glad you asked! Let me explain. In our main circuit "FSM", we've got a register to hold the state of our state machine. We've got it wired in that box-like manner in which we wired our AddMachine in exercise 2. That means on every tick of the clock, the state will update itself based on what happens with whatever logic happens in the box titled, "FSM Logic".

   So, what goes on there? Oh! I'm so glad you asked! Let me try to explain. Check the "FSM Logic" subcircuit. See that "current state" input box? That's the current state of the register in the outer "FSM" circuit which we wired into this subcircuit. See that "input" input box? That's the input to the FSM which we also wired from the main "FSM" circuit. Using these two inputs we should be able to logic our way to calculating both the next state and the output of the FSM.

   So, what about those other two badly named subcircuits? Oh! I'm SO VERY HAPPY you asked! Let me explain. In the "FSM Logic" subcircuit, we've already done the logic for calculating the output from the input and the current state. What your task is: implement the logic for calculating the state bits for the next state. The "StateBitZero" subcircuit should calculate the LSB of the next state (AKA the rightmost bit) given the input and current state. Likewise, the "StateBitOne" subcircuit should calculate the MSB of the next state (AKA the leftmost bit). Was that clear? Ask a lab assistant or your TA if it wasn't.

   How in the world would I even start doing this? All sarcasm aside, this is a very good question. This slide from last week tells you two strategies for converting a truth table to a boolean expression. And a boolean expression is something you can wire up in Logisim pretty easily from your experience with exercise 1.

   Think about and compare and contrast the two methods presented in that lecture slide. Does SoP make sense? Here's a sentence that a fellow student might say to you when trying to convince you of how it works: You just add up all the times when the output is 1. Does PoS make sense? If not, here's a nontrivial fact: to go from PoS to SoP, you can just use DeMorgan's Laws! Try to convince yourself of this when you get home or in office hours.

   SO, you could go from the truth table to SOP to a circuit, or you could notice that for each state bit, there are only two situations in which it is zero. That is to say, there are very few situations in which it is zero. In SoP, we add up all the times that the output is 1. In PoS we "multiply" up all the complements of the inputs when the output is 0. The COMPLEMENTS. Relook at the slide if you glossed over this detail (I know I did). Now, here's the big hint. If there are fewer 0s than 1s in the output column, which method is easier to use?

   Another hint for simplifying stuff: (A + B) * (A + C) = A + BC

Exercise 3.5: Logisim pointers

Now, it's time to implement .circ files that point to other .circ files in memory. Just kidding. By pointers I meant tips. Here we go.

• You can see what values are on wires by simply using the "select" tool to click on a wire.
• To keep a visual reminder of what value is on a wire without using an input or output pin, use a probe, which is located under the "wiring" folder on the left. If you hook this up to a wire, it will always update itself with the value of the wire.
• You may have noticed that wires turn different colors in different situations. In general, if stuff turns blue, you might fix it if you restart Logisim... or you might have some undefined values somehwere. If stuff is red, you've probably put an extra bit of wire somewhere. And if stuff is mainly black and green, then you're good to go!
• Look up from your screen. When I was working on my CPU project in Logisim, I found it maddening to stare at my huge expanse of wires and make sure that they went into the right pins. We'll be showing you some extra tools next lab to help the process, but I would ask anyone who's pulling their hair out over Logisim to just back away from the computer, take a deep breath, and drink some water before resuming.

I really admire you for toughing through this lab and lab 5. If you feel a little behind on the labs, that's perfectly fine. Lab 7 is supposed to take a little less time than the previous two.

As always, I wanted to share some of my favorite cute pictures. I think these are not only adorable but extremely creative. I hope they make you smile.

Chalk and charcoal art on the streets of Ann Arbor, Michigan