- Learn the basics of using Logisim.
- Implement and use a finite state machine.
Copy the contents of ~cs61c/labs/su14/09 to a suitable location in your home directory.
The following two labs (and project) use Logisim, which is an "educational tool for designing and simulating digital logic circuits." Like MARS, Logisim is a Java-based application that you can download and run on your home computer. You can get the jar file from the Logisim website or by copying it from ~cs61c/bin/logisim-generic-2.7.1.jar on the instructional machines.
You can run Logisim in lab by typing 'logisim &' at the command line. The same rules apply to Logisim as they did with MARS: avoid running Logisim remotely if you can, but if you do, make sure you are running an X-Server (like XMing) with X11 tunneling enabled. Tunneling does NOT work on the Orchard machines.
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.
- 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.
- Click the "Input Pin" button. Now, place two input pins somewhere to the left of your AND gate.
- Click the "Output Pin" button.
Then place an output pin somewhere to the right of your AND gate.
Your schematic should now look something like this:
- At this point, you've probably noticed that our gate has too many inputs. Although this won't affect it's operation, it's always better to have a cleaner schematic (just like with code!). To this effect, Logisim offers a variety of properties that we can modify to make an element appear exactly as we wish. To change these options for our AND gate, click the "Select tool" button,
click the gate, and the pane in the bottom left of the logisim window will update to show the AND gate's properties:
Let's go ahead and change some of these properties to make our circuit cleaner:
- First, let's update the number of inputs to match our circuit. In order to do this, click on the number next to "Number Of Inputs" and change it to 2.
- Next, since we've reduced the number of inputs, there's no point in having a Medium sized gate. Click on "Medium" next to "Gate Size" and make the gate "Narrow".
- Now, let's label our gate. This may seem silly with such a small circuit, but when we start working with large circuits, labels will be very useful (just like comments in a long piece of code). Add a label to your AND gate by clicking the blank field next to "Label" in the properties pane.
- If you entered a long label, you'll notice that it covers the output terminal of the gate. One way of fixing this is to change the "Facing" property. This is akin to rotating the gate. Change the "Facing" property to "South".
- Finally, let's take a look at the "Data Bits" field. Although we won't change it for this gate, it's important to note what it does. We can change this field to allow our gate to perform operations on wider quantities; for example, if we change Data Bits to 32, our AND gate acts exactly like bitwise and on two uint32_t values in C. In order to use this gate, we would also have to change the size of our input/output pins. Based on what we've just seen, how could you do this?
At the conclusion of this step, your circuit should look like this:
The properties pane for your AND Gate should look like this:
- Now, let's add wires to our circuit. Click the "Select tool" button.
Click and drag to connect the input pins to the top 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 top.
Repeat the same procedure to connect the output (now bottom) of the AND gate to the LED.
After completing these steps your schematic should look roughly like this:
- 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?
Exercise 1: Sub-Circuits
Similarly to how a C program can contain helper functions, a schematic can contain subcircuits. In this part of the lab, we will create several subcircuits to demonstrate their use.
- Create a new schematic (File-->New) for your work.
- Create a new subcircuit (Project-->Add Circuit). You will be prompted for a name for the subcircuit; call it NAND.
- 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. Label your inputs 'A' and 'B' and your output 'Out'.
- 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.
- Now single click the word "NAND" in the list and then click in the schematic area to place it.
- If you did it correctly, you should see a gate with 2 input pins on the left and one output pin on the right. If you hover over these pins with the "Select tool", the labels you gave them in step 3 should appear! This is why labeling within subcircuits is so important - to help prevent you from wiring things incorrectly. While you're here, label your subcircuit "NAND".
- Hook input and output pins to your NAND subcircuit and see if it works as you expect (poke, poke!).
- Repeat these steps to create several more subcircuits: XOR, 2 to 1 MUX, and 4 to 1 MUX.i 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: Look at the lecture slides for a refresher on how to build these. You may want to consider using some of your custom subcircuits when designing the others.)
- Place a copy of each subcircuit in your "main" circuit and attach appropriate inputs and outputs. Save your finished file as ex1.circ.
- Show your four circuits in ex1.circ (NAND, XOR, 2-to-1 MUX, and 4-to-1 MUX) to your TA.
Exercise 2: Storing State
Let's implement the circuit we've been talking about in lecture, that increments a value ad infinitum. The difference between this circuit and the circuits you've built for lab so far is that you need some registers to store state. The following will show you how to add registers to your circuit.
- In a new file, create a new subcircuit (Project-->Add Circuit) and name it AddMachine.
- 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 a library, the circuit browser at left will have a new "Arithmetic" folder.
- Select the adder subcircuit from the "Arithmetic" library and place the adder into your AddMachine subcircuit.
- Load in the Memory Library (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.
- Select the Register from the "Memory" folder and place one register into your subcircuit.
Below is an image diagraming the parts of a register.
- Connect a clock to your register. You can find the clock circuit element in the "Wiring" folder in the circuit browser.
- Connect the register and adder together based on the diagram from lecture.
You may notice that when you connect the adder to a register, you will get a "Incompatible widths" error. This means that your wire is trying to connect two pins together with different bit widths. If you click on one the adder with the "Selection" tool, you will notice that in the box below circuit browser will have a field called "Data Bit Width". This field controls the number of bits the the adder will add. Change this field to 8 and the "Incompatible widths" error should now go away.
- Wire a constant 8-bit 1 to the second input of the adder. You can find the "constant" circuit element in the "Wiring" library.
- Add two output pins to your circuit so that you may monitor what comes out of the adder and the register.
Thus, by the end, your circuit should look like as follows:
Now let's see if you built your circuit correctly.
- Go back to the "main" subcircuit by double clicking on "main" in the circuit browser.
- Single click on your "AddMachine" circuit to select it.
- 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 definately be useful when you do your project.
- Place your AddMachine subcircuit into the main subcircuit.
- Select the AddMachine subcircuit you just placed into main.
- 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.
- To access the internal state of a subcircuit, either (1) right-click and select "View AddMachine" or (2) double-click it using the "Poke" tool. 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.
- Initialize the register value to 1. You can do this by clicking on the register value with the "Poke" tool and then typing in the hex value.
- To return to the main circuit while preserving state, go to Simulate-->Go Out To State-->main. Alternatively, you can hold the Command key (control on windows) and press Left-Arrow.
- Now start running your circuit by going to Simulate-->Ticks Enabled. Your circuit should now be outputting a counter in binary form.
- If you want to run your circuit faster, you can change the tick frequency in Simulate-->Tick Frequency.
- Show and operate your AddMachine circuit for your TA.
Exercise 3: FSMs to digital logic
Now we're ready to do something really cool: translate a FSM into a digital logic circuit! If you've been paying attention in lecture you've noticed that the circuit we built in exercise 2 looks eerily similar to the diagram of a general FSM circiut. We're going to modify our circuit 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.
- Note that the FSM is implemented by the following diagram:
- Observe that the following is a truth table for the FSM:
st1 st0 input | nxt st1 nxt 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
- We've provided you with a starter Logisim circuit in FSM.circ.
- Note that the top level of the circuit looks almost exactly the same as our previous adder circuit, but now there's a FSMLogic block instead of an adder block.
FSMLogic is the combinational logic block for this FSM.
The output bit has already been completed for you, as it's the most complicated to simplify and implement.
You should complete the circuit by completing the StateBitOne and StateBitZero subcircuits.
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. This could make your life easier if you think a bit outside the box...
- Once you think you've completed your circuit, TEST IT!
This is accomplished by taking EVERY state transition (arrow) in the FSM diagram and verifying correct behavior.
Note that this may require resetting your FSM (i.e. you can't hit every transition in a single run).
If you are having trouble figuring out how to run your FSM, think about the following: When you take a transition, what gets updated? (Hint: what does FSM stand for?) How do we update this? As you are verifying next state and output, things may seem a little off at first. But you should be able to explain this supposed discrepancy. (Hint: what's the difference between State and Combinational logic?)
- Show your StateBitZero and StateBitOne circuits to your TA and explain how you derived their logic.
- Verify the behavior of your FSM with the following input stream: 1, 0, 1, 1, 0, 1. What states do you go through? What is your corresponding output stream?