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:

Assignment 1

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

A Simple State Machine

Start from the following skeleton file: StateMachine.circ

  1. Translate the state diagram into a state table.
    S0InS0nOut
    00
    01
    10
    11
  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.