CS270 Homework 2: State Machines

See Progress on class page for due date.

Goals

1. To practice designing state machines.
2. To practice implementing state machines in Logisim.

The Assignment

*** READ THIS SECTION CAREFULLY ***

Start from the following skeleton file: H2.circ

When finished, submit your H2.circ file to the H2 box in the Checkin tab. Preliminary testing will perform some sanity tests, but it will not check that you got the right answers. There is also a Canvas component. Refer to each problem for details.

This assignment will be auto-graded. Don't change the name of the sub-circuits and don't create or remove sub-circuits. Pay attention to the notes inside the input, output, and reserved sections. If you don't pass preliminary testing, the auto-grader will be unable to grade your work and you won't get credit.

Problem 1: Designing a State Machine (30 points)

Design and draw the state diagram of a Mealy machine (i.e., outputs are transition-assigned) to control a mean-spirited vending machine, MVM. It charges 30 cents for a small toy and does not render change (all extra money is gladly accepted), but at least it delivers the toy (output signal T becomes 1). Moreover, MVM only accepts dimes and quarters (as input signals named D and Q). Since the human input is much slower than the clock of the machine, there are many clock cycles when both D and Q are zero, but the condition D = Q = 1 is guaranteed to never occur (only one coin may be inserted). The machine must work for multiple purchases. I.e. if somebody purchases a toy, it must automatically be ready for another purchase.

Here are some important specifications:

1. You must submit a Mealy (i.e., transition assigned) machine. If you submit a Moore (state-assigned) machine, you will lose points.
2. Follow the convention that the machine operates with a fast clock (much faster than the user can insert coins). You will lose points otherwise.
3. You must use the minimum number of states. Otherwise, you will lose points.
4. When following the convention, please only use the following three input labels on the edges of your transition graph:
   • D to denote a dime.
   • Q to denote a quarter.
   • 00 to denote no coin (just a clock tick).

   Do not use symbols like 01, 11, etc. If you do so, you will lose points.

5. You must mark the starting state with the text "Start" (see the machines below for an example)

To draw the diagram, we suggest yEd. Specifically, we suggest you try yEd Live in the browser rather than installing the software to avoid java incompatibility issues. However, you may use any software to generate a graph of your state machine. Your submission must be a PDF file.

If you want to run this program in one of the CS machines, download the Java zip file from that page (you may need to click on Show all versions). In a terminal, go to the folder where you downloaded the file and run the following commands:

unzip yEd-3.17.zip
cd yed-3.17
java -jar yed.jar

To draw an edge from a state to the same state in yEd, use the Polyline with Target Arrow edge. Click and hold on a node, drag the mouse out of the node in any direction, release the mouse and then click on the node again. Here is a short demo on doing this and naming edges: click here.

When you're done, export your graph as a PDF (File > Export...) and submit it to the H2P1 Canvas assignment.

Problem 2: Implementing a State Table (30 points)

In this problem, you will design a circuit that implements the combinational part of the following state machine:

You must use the state encoding shown on the right. Note that S1 is the most significant bit of the state and S0 is the least significant bit. The input to the state machine will be labeled In. The output of the state machine will be labeled Out.

1. The first step is to complete the state table. Go to the Canvas assignment titled H2P2 Canvas. Complete the state table and submit it. You only have one attempt to get credit. If you didn't get it right, you must correct it before moving on.
2. Next, implement the state table as a combinational circuit in Logisim starting from the skeleton in the P2 sub-circuit. Follow these guidelines:
   • Do not introduce additional input or output pins and do not modify the input and output sections. Work on the P2 circuit only. Do not create sub-circuits.
   • You should implement the combinational logic part only. Therefore, your circuit should not contain flip flops or clocks. You may use elements from the Wiring and Gates libraries only.

Problem 3: Implementing a State Machine (40 points)

In this problem, you will design a circuit that implements the following state machine:

You must use the state encoding shown on the right. Note that S2 is the most significant bit of the state and S0 is the least significant bit. Also, notice that the state encoding is unusual: it's not in increasing binary order. Be careful about this when building your state table. The input to the state machine will be labeled In. The output of the state machine will be labeled Out. This is a Moore state machine since the output only depends on the current state.

1. The first step is to complete the state table. Go to the Canvas assignment titled H2P3 Canvas. Complete the state table and submit it. You only have one attempt to get credit. If you didn't get it right, you must correct it before moving on.
2. Next, implement the state machine as a sequential circuit in Logisim starting from the skeleton in the P3 sub-circuit. Follow these guidelines:
   • Do not introduce additional input or output pins and do not modify the input and output sections. Work on the P3 circuit only. Do not create sub-circuits.
   • You may use only D flip flops (triggered on the rising edge, which is the default) and elements from the Wiring and Gates libraries.
   • Since the state encoding requires 3 bits to represent a state, you will need 3 D flip flops. You must label these flip flops appropriately: S2, S1, and S0 (case sensitive). If you don't do this, the auto-grader will be unable to determine the state of your machine and you will get no credit.
   • Don't forget to connect the output of your machine to the Out pin. You don't need a flip flop for Out (why?).
   • Don't forget a clock in your circuit (with the Low Duration and High Duration attributes set to 1 tick, which is the default)!

Advanced question (for fun): can you write the regular expression that this state machine recognizes?