CS61C Lab 10

Finite State Machines in Logisim

Background

Goals

There are two parts to this lab. In the first part, you will be learning how to use the remaining essential parts of logisim, in particular, learning how to maintain state and how to split wires to take a subset of bits on a wire. The second part will allow you to familiarize yourself with the general approach of splitting a finite state machine into two parts: the controller, which maintains the current state, and the next-state and output circuit combinational functions.

Reading

P&H section B.10 (copy can be found here). Refer to the Logisim Website or last week's lab for a refresher on Logisim.

Part (A): Advanced Logisim

The following exercises will teach you how to store state into logisim as well as introduce you to how wires work in logism.

Exercise A.1: Storing State

Let's implement the circuit you worked on in Lab 8. 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, Fib8.
  2. Load in the Arithmetic Library (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.


  3. Select the adder subcircuit from the "Arithmetic" library and place the adder into your Fib8 subcircuit.
  4. 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.
  5. Select the register from the "Memory" folder and place two registers into your subcircuit. Below is an image diagraming the parts of a register.


  6. Connect a clock to your register. You can find the clock circuit element in the "Base" folder in the circuit browser.
  7. Connect the two registers and adder together based on the diagram in Lab 8.

    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.

    In general, the box below the circuit browser will list the properties of a given circuit element. Other circuit elements will have other properties.

  8. Add three output pins to your circuit so that you may monitor what comes out of the adder and both registers. Thus, by the end, your circuit should look like as follows:

Now lets see if you built your circuit correctly.

  1. Go back to the "main" subcircuit by double clicking on "main" in the circuit browser.
  2. 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.
  3. Place your Fib8 subcircuit into the main subcircuit.
  4. Select the Fib8 subcircuit you just placed into main.
  5. Connect output pins to the Fib8 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 one of the top register, the middle pin is the output of adder, and the bottom pin is the output of the bottom register.
  6. Right click on your Fib8 subcircuit, and select "View Fib8". This is the ONLY method to preserving state. 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.

    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 Fib8 circuits down, it only takes you to the first Fib8 circuit to put down.

  7. Initialize the register values to 1. You can do this by first, click 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. Alternatively, you can hold Control key and press Up-Arrow.
  9. Now start running your circuit by going to Simulate->Ticks Enabled. Your circuit should now be outputting the fibonachi numbers in binary form.
  10. If you want to run your circuit faster, you can change the tick frequency in Simulate->Tick Frequency.

Checkoff

Show your Fib8 circuit to your TA.  

Exercise A.2: Splitters

This is the last essential tool you will need in this class. To demonstrate it's use you will construct a circuit that will output 1 when the most significant bit and least significant bit are 1.
  1. Create a new subcircuit and name it "Exer2".
  2. Add an 8 bit input pin to your circuit.
  3. Add a 1 bit output pin to your circuit.
  4. Go to the base folder and select the Splitter circuit. This circuit will take a wire and split it into a smaller set of wires.
  5. Before you place your circuit, change the "Bit Width In" property to 8, and "Fan Out" property to 3. If you move your cursor over the schematic, your cursor should look as follows:
  6. Now, select which bits to send out to which part of your fan. The least significant bit is bit 0 and the most significant bit is bit 7. Change bits 1, 2, and 6 to be coming out on fan arm 1. Alternatively, you can have bits 1, 2, and 6 to not come out on any of the fan arms by selecting "None"
  7. Once you configure your splitter, you can place your splitter into your circuit.
  8. Add an AND gate and complete the circuit.

Checkoff

Show your Exer2 circuit.  
Tell your TA a more meaningful name for the Exer2 circuit.  

Part (B): FSM Design

Now that you are familiar with combinational designs in Logisim, we will experiment designs with stateful elements.

Info

Appendix B in P&H presents a description of a circuit used to control a traffic light. Your job in this part of the lab is to implement and test the traffic light controller in Logisim.

The details of the traffic light controller finite state machine are explained in P&H. You should follow that specification with one modification. Add an input signal called RST. Asserting this signal should "reset" the controller to the NSgreen state (on the next positive clock edge) regardless of its current state and the value of the other inputs. Otherwise your circuit should be identical to the one described in the book.

Exercise B.1

Create a sub-circuit that implements the next-state combinational logic for the trafic light.

Checkoff

Show your sub-circuit to your TA  

Exercise B.2

Create a circuit that implements the traffic light controller. This module must include an instance(s) of your next-state combinational logic and a flip-flop to hold the current state. Test it with a couple of input cases.

Checkoff

Show the controller to your TA  

Exercise B.3

Devise a scheme to test your circuit. You want some way to test all possible inputs and easily verify that they produce the correct output. Try to come up with something more clever than manually flipping the inputs and verifying the outputs and something more reliable than connecting clocks with different frequencies to the inputs.

Checkoff

Show how you test your design to TA  
View document source. Generated by Docutils from reStructuredText source.