COSC 201: Computer Organization

Lab 6: Finite State Machines

Purpose
Learn to specify and implement a finite state machine.
Method
Design and build a simulation of a FSM garage door controller. Represent a FSM by a state diagram, a truth table, and as a logic circuit.
Preparation
Review Appendix B in the text.
Files to Use
What to Hand In
Turn in a written report including:

Specifications

You are to design a controller for a garage door opener with the following specifications.

Inputs

top (T)
When the door reaches the top, this input becomes true.
bottom (B)
When the door reaches the bottom, this input becomes true.
eye (E)
There is a light beam across the doorway with an electric eye. When the electric eye detects the light beam, this input is true. If the light beam is blocked, such as by a small child standing in the doorway, then this input becomes false.
go (G)
When the button on the remote control is pressed, this input becomes true. When the button on the remote control is released, this input becomes false.

Outputs

up (U)
When this output is true, the motor moves the door upward to open it.
down (D)
When this output is true, the motor moves the door downward to close it.

If both U and D are false, then the motor will be stopped. The U and D outputs should never both be true at the same time to avoid damaging the motor.

Operation

The input from the button on the remote control (G) will be processed by the one-shot circuit, which happens to be a finite state machine. This circuit prevents the G input from staying true for more than one clock cycle, even if the button is held down for a long period of time.

  1. The clock rate is 10 Hz so that the controller will respond to changes in the inputs within one tenth of a second.
  2. If the door is closed, pressing the button (G = 1) causes the door to begin opening.
  3. If the door reaches the top (T = 1), the motor will stop.
  4. If the door is open, pressing the button (G = 1) causes the door to begin closing.
  5. If the door reaches the bottom (B = 1), the motor will stop.
  6. Pressing the button (G = 1) while the door is opening causes the door to stop. Pressing the button again (G = 1) causes the door to begin closing.
  7. Pressing the button (G = 1) while the door is closing causes the door to reverse direction and immediately begin opening.
  8. If the electric eye detects that the light beam has been interrupted (E = 0) while the door is closing, the door will reverse direction and begin opening.
  9. If the light beam is interrupted (E = 0) while the door is opening then the door continues opening.

Procedure

Draw a state transition diagram for this finite state machine. Use four states numbered as follows: closed (00), opening (01), open (10), and closing (11). Each transistion (edge) should be labeled with the values of the inputs (TBEG) for which it is taken.

Complete the full truth table for the transitions. The columns in this table should be (from left to right): current state, T, B, E, G, next state. There should be one line for each combination of current state and input values (64 lines). You may find the tables in the file garage.doc or garage.pdf useful.

Construct a compressed truth table where "don't care" state or input values have been collapsed into one line. This table should be less than a quarter of the size of the original.

Construct a full truth table for the output. The columns in this table should be (from left to right): current state, U, D. There should be one line for each combination of state values (4 lines).

Construct a circuit for the finite state machine using the LogiSim simulator and the file garage.sim.

  1. Complete the sub-circuits for the state register, the next state function , and the output function. Use two-level sum-of-products circuits to implement the truth tables for the next state and output functions.
  2. Complete the main circuit by connecting instances of the state register, next state, and output sub-circuits.
  3. Connect the T, B, E, and G inputs, the U and D outputs, and the clock. Remember to connect the G input to an instance of the one-shot sub-circuit so that it will never be true for more than one clock cycle.

Turn in your written report and place copies of any files in your ~/courses/201/assignments directory. Be sure that your name appears in any files that you turn in.