H13: State Machines
Time Estimate2-3 hours Grade Impact1% DueNov 30 @ 12pm
Problems
-
Sequence detector (Moore vs. Mealy). Design an FSM that outputs 1 whenever the last three inputs are
101(possibly overlapping:10101produces 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
wis asynchronous? - Overlapping detections force you to reuse states; a naive design doubles the state count.
-
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?
-
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).
-
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.
-
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.
-
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.