CS270 Recitation 13: A Simple State Machine

Recitation Credit

Goals

1. To learn how to translate a state diagram into a state table.
2. to learn how to implement a state machine in Logisim.

Introduction

Check out this document for an example of how to build and simplify a FSM's state table, as well as an implementation of the machine. As you inspect it, consier the following questions:

• Why couldn't we use the combinational circuit shown at first? What design issues would this approach have?
• Did we use a Mealy or a Moore machine? Which switching help simplify it or make it more complicated?
• Can you determine from only the circuit diagram whether the machine is a Mealy or Moore machine? Hint: Is the output dependent solely on state or does it depend on transitions?
• How would the logic circuit implementation change if we switched?

Assignment 1

We would like to implement the following state machine as a circuit:

Start from the following skeleton file: StateMachine.circ

1. Translate the state diagram into a state table.

   S0	In	S0n	Out
   0	0
   0	1
   1	0
   1	1

2. In Logisim, insert enough D flip flops to store the current state (how many flip flops do we need?). Label the flip flops appropriately.
3. Implement the state table as combinational logic. Make sure to connect the flip flops and the combinational logic appropriately.
4. Notice that the output is on a transition. This means that the output shouldn't change until the clock tick comes in. How can we ensure this?
5. Question for fun: can you write a regular expression that represents the pattern that is recognized by this state machine?

Assignment 2

You are to design a Mealy state machine to control an old fashioned vending machine that would drop a token for a price of 20 cents. There are two possible inputs at any state: N (for nickel) and D (for dime). Based on the input, the machine is to transition to a new state. When any sequence of coins worth 20 cents or more is input, the machine transitions to the start state and outputs a 1 to indicate that the vending machine is to drop the token. All other transitions are accompanied with an output of 0. If the value of the coins is higher than 20 cents, the extra money is lost.

Draw the state diagram for this machine.