Due: Friday, September 30, 2016, 11:00 am (start of the class)

Consider a Moore state machine that can recognize non-overlapping sequences of three 0s in a continuous stream of bits. The state machine has a one bit input and a one bit output, and it should output a 1 only when it detects the third 0 of the sequence.

  1. How many states do you need for this state machine, and what is the meaning of each state.
  2. Given a single input bit, each state should have two edges to a next state (one for 0, one for 1). For each state you defined above, indicate the next state for each possible input.
  3. How many memory bits would you need to hold the state information?
  4. Given the string 00100011, show the sequence of states your state machine would follow.
  5. Assign each of your states an N-bit representation. For example, if you have four states, you would use 00, 01, 10, and 11. Then show the truth table for the output as a function of the state. Finally, write the Boolean expression for the output as a function of the state bits (e.g. S1 and S0).

© 2016 Ying Li. Page last modified: .