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: Creating a State Diagram (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 machine (ouput based on transitions, which are based on current state and inputs). If you submit a Moore machine (outputs based on current state), 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. This basically means that in any state there are three possible inputs: dime, quarter, or no coin, and for the purposes of this state diagram you do not need to worry about a clock
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).

   For this state diagram do not use symbols like 01, 11, etc to name the states, instead give the states names that are meaningfull to what is happening with the vending machine, i.e., "Start", or "10 cents".

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

To draw the diagram, we suggest draw.io however, you may use any software to generate a graph of your state machine. Your submission must be a PDF file.

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

Problem 2: Implementing a State Table in Combinational Logic (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. 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 not be able 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?