CS61C Lab 10

Software Gates and Finite State Machines in Logisim

Background

Goals

There are two parts to this lab. In the first part, you will be experimenting with using our own "software gate" extension to Logisim. In this part you will be designing a combinational BCD (Binary Coded Decimal) incrementer.

The second part of the lab helps you to gain experience designing and simulating a simple sequential logic circuit. It will give you practice using Logisim for logic simulation and (we hope) an appreciation for the issues involved in designing, testing, and debugging sequential logic circuits. We expect that, having done this lab assignment, you will understand the use of a flip-flop to store state and will be familiar with the pattern of splitting a finite state machine into the controller, which maintains the current state, and the next-state and output combinational functions.

Reading

Project 4 handout. 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): Software Gate

Info

In this part of the lab, you will design a BCD incrementer (counter). BCD is another way to represent numbers. Since we live in a world that uses decimal number system, it is sometimes useful to encode this decimal number system (with number 0 to 9) in a computer. Since we may have 10 different values for each digit, we will need to use 4 bits to represent each decimal digit as shown below:

x3 x2 x1 x0 Value
0 0 0 0 0
0 0 0 1 1
0 0 1 0 2
0 0 1 1 3
0 1 0 0 4
0 1 0 1 5
0 1 1 0 6
0 1 1 1 7
1 0 0 0 8
1 0 0 1 9
1 0 1 0 not used
1 0 1 1 not used
1 1 0 0 not used
1 1 0 1 not used
1 1 1 0 not used
1 1 1 1 not used

Incrementing a BCD encoded number is therefore the same as incrementing normal 4-bit binary except it wraps around at the number 9 back to 0. The following truth table shows the logic of a BCD incrementer with input x3x2x1x0 and output y3y2y1y0:

x3 x2 x1 x0 y3 y2 y1 y0
0 0 0 0 0 0 0 1
0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 1
0 0 1 1 0 1 0 0
0 1 0 0 0 1 0 1
0 1 0 1 0 1 1 0
0 1 1 0 0 1 1 1
0 1 1 1 1 0 0 0
1 0 0 0 1 0 0 1
1 0 0 1 0 0 0 0
1 0 1 0 0 0 0 0
1 0 1 1 0 0 0 0
1 1 0 0 0 0 0 0
1 1 0 1 0 0 0 0
1 1 1 0 0 0 0 0
1 1 1 1 0 0 0 0

Exercise A.0 (Setup)

Create a directory for this part of the lab. You can name it anything you want. We will call it lab10p1 for now:

mkdir lab10p1

Copy the template C file template.c from the project directory to the directory you have just created and name the file myfunc.c:

cp ~cs61c/projs/04/template.c myfunc.c

Now, from within the directory lab10p1, start Logisim by

logisim

Note: do not put logisim into background. i.e. Do not put an & sign at the end of the command. You WILL need to see the output in the windows in which you have started logisim for this part of the lab. You may start your text editor in another windows to edit myfunc.c in later part ofthe lab.

Exercise A.1

Inside logisim, Create a "Software Gate" following instruction from Porject 4 handout. Then perform the following:

  1. Change the number of input to 1.
  2. Create 1 input pin and 1 output pin in your top level Logisim design main
  3. Change the "Bit Width" of both your input and output pin to 4.

Now, edit myfunc.c using a text editor such that this C code performs the BCD incrementing function.

Remember: you should add code between the line marked "put your code below this line" and "put your code above this line".

Once you are done with editing myfunc.c, save it, and go back to Logisim. Use the Poke tool to change values of input. Two things will hapeen:

  1. Your output in Logisim should change accordingly as reflected on the output pin
  2. Messages will be printed to the windows in which you started logisim

Checkoff

Show your code in myfunc.c to your TA  
Show how your software gate works in Logisim.  

Exercise A.2

Now, reimplement the BCD incrementer function using pure hardware. That is, you can use any gates/library in Logisim, except the "Software Gate" that you were using in pervius exercise.

One useful tool you will find is the Combinational Analysis tools which you can start by selecting the menu Window->Combintional Analysis. This tool can generate Gates for you automatically based on truth table. For more information, see the Logisim documentation.

Checkoff

Show your BCD incrementer implemented with hardware to your TA  

Part (B): FSM Design

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

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 verify that they produce the correct output. Try to come up with something more clever than manually flipping the inputs and verifying the outputs.

Checkoff

Show how you test your design to TA