Homework 8

Distributed Friday, November 16, 2007
Due before 10:30, Friday, November 30, 2007

Please put your full name and lab section letter on your homework.

Always remember to staple your work, if it is multiple pieces of paper.

If you choose, indicate on the top of your assignment roughly how much time you spent on it. This information will have no impact on your grade; it will only be used by an inexperienced course staff to gauge the volume of work to assign.

  1. (15 points)
    Implement the following FSM in each of the state encoding styles listed below. For each style, draw a state encoding table, and design the next state and output logic, and draw a circuit diagram with the registers and logic gates. The combinational logic you use does not necessarily have to be highly optimized, but it shouldn't be outlandishly huge. (For example, if it's possible do implement some next state function with three gates, and you use twenty, you won't get full credit.)

    1. Binary
    2. One-hot
    3. Output

  2. (15 points)
    Same as 1, but with a Mealy machine, this time.

    1. Binary
    2. One-hot
    3. Output
  3. Do not submit exercise 3 with homework 8! It has been moved to homework 9. (30 points)
  4. (40 points)
    Do the programming assignment described here, or do the state minimization exercises by hand that are described below.

    Exercise 4 alternate:

    For the two FSMs drawn below, do the following. Use the implication chart method to minimize each of the FSMs. In each cell of the implication chart, indicate clearly in some way whether the pair of states that that cell represents will be merged, will not be merged because of an output difference, or will not be merged because of a next state difference. Draw the resulting minimized FSM. Indicate which of these two machines could be minimized with the row-matching method and which could not.
    1. This FSM has three possible input patterns. That means that each cell of the implication chart will have three pairs of next states

    2. The only difference between Moore and Mealy machines as far as state minimization is concerned is that when we are comparing outputs, Mealy machine states have to match outputs for every input pattern.