H13: State Machines

Time Estimate2-3 hours   Grade Impact1%   DueNov 30 @ 12pm  


Problems

  1. Sequence detector (Moore vs. Mealy). Design an FSM that outputs 1 whenever the last three inputs are 101 (possibly overlapping: 10101 produces two detections).

    • (a) Draw the state diagram and state table for a Moore version.
    • (b) Draw them for a Mealy version.
    • (c) Compare: how many states does each need? When does each assert its output? Which is more likely to glitch if w is asynchronous?
    • Overlapping detections force you to reuse states; a naive design doubles the state count.
  2. Vending machine. A machine accepts nickels (5¢) and dimes (10¢) and dispenses a product when at least 15¢ has been inserted (no change given).

    • (a) Design the FSM (Moore or Mealy, your choice) with states representing accumulated value.
    • (b) Minimize it by partitioning.
    • (c) Re-encode the minimized machine in one-hot and compare combinational logic complexity with the binary encoding.
    • (d) Implement the next-state logic with D flip-flops, then redo it with JK flip-flops using the excitation table. Which uses fewer gates?
  3. Traffic-light controller (ASM chart). A 4-way intersection has NS and EW lights. Using an ASM chart, design a controller with states Green-NS, Yellow-NS, Green-EW, Yellow-EW, plus a pedestrian “Walk” request input that extends the current green by one cycle.

    • Include a timer input that forces yellow after a minimum green time.
    • Explain which outputs are Moore (light colors) and which are Mealy (walk acknowledge).
  4. State equivalence / minimization. Given the following state table (inputs 0/1):

    Present Next (0) Next (1) Out (0) Out (1)
    A B C 0 0
    B A D 0 1
    C D A 0 0
    D C B 0 1
    E F A 0 0
    F E D 0 1
    • (a) Find and remove any unreachable states (assume reset = A).
    • (b) Minimize by partitioning; show each partition $P_1, P_2, \dots$ until stable.
    • (c) Is the minimized machine Mealy or Moore? Justify.
  5. Edge detector. Design a 2-state FSM that outputs a single pulse when an input transitions from 0 to 1 (rising edge), and a different design that detects either edge.

    • (a) State diagrams.
    • (b) Show that the edge detector is just a shift register of length 2 (looping in M4 L23) with a comparator on the two stored bits.
  6. Incompletely specified machine. A state table has a don’t-care transition and a don’t-care output. Minimize it twice: once assuming unspecified outputs are 0, once assuming they are 1. Explain why the two results differ and which convention your CAD tool likely uses.

Supplementary Materials