Finite state machines
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| finite state machine/ˈfaɪnaɪt steɪt məˈʃiːn/ | Máy trạng thái hữu hạn |
| state diagram/steɪt ˈdaɪəɡræm/ | Sơ đồ trạng thái |
FSMs: states, transitions, outputs
- A finite state machine is states + transitions; the state diagram draws them as bubbles and labelled arrows.
- Moore outputs from state (aligned, glitch-free); Mealy outputs from state + inputs (faster, glitch-prone). Design: diagram → table → encoding → excitation → minimise logic.
- Merge equivalent states (same outputs, same next states) — same behaviour, fewer flip-flops.
The parity detector: two states, $Q^{+} = Q \oplus in$ — the whole FSM is one XOR and a flip-flop, and the trace on 1,0,1,1 lands on ODD exactly when three 1s have been seen.
{exercise:uni-ee3x-fsm}
The parity detector is implemented with how much logic?
Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Two states (EVEN/ODD) with the input toggling between them: next state is Q XOR in — minimal by construction, verified by trace.
A 1011 detector sees the stream 1,0,1,1. After the detected match its state should be —
Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
The matched 1011 ends with 1, which is also the first symbol of 1011 - so the detector keeps S10 and the next 1 immediately triggers again. Forgetting the overlap is the classic detector bug.
A Moore machine's outputs change —
Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Moore outputs decode from state only, so they settle one clock after the input; Mealy adds the input for same-cycle response at the cost of glitches.