Finite state machines
導入済み| English | 意味 |
|---|---|
| finite state machine/ˈfaɪnaɪt steɪt məˈʃiːn/ | 有限状態機械 |
| state diagram/steɪt ˈdaɪəɡræm/ | 状態図 |
| Moore machine/mʊə məˈʃiːn/ | A state machine whose outputs depend only on its present state. |
| Mealy machine/ˈmiːli məˈʃiːn/ | A state machine whose outputs depend on both its present state and its inputs. |
| state minimisation | state minimisation |
Same keys, different order
- A door keypad opens for 1-0-1-1 but not for 1-1-0-1. The keys are the same; only the order differs.
- Reacting to a sequence needs a circuit that knows how far through the sequence it is. That is a state machine, the controller inside most digital systems.
States, transitions, outputs
- A finite state machine 有限状态机 (FSM) has a fixed set of states, a rule for moving between them on each clock, and outputs.
- The state diagram 状态图 draws states as bubbles and transitions as arrows labelled with the input. In hardware it becomes a state register plus next-state logic and output logic.
Put one clock cycle of an FSM in order.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
State, combinational next-state logic, clock edge, then outputs from the new state (Moore). The register is the only memory.
Moore and Mealy
- A Moore machine 穆尔机 computes its outputs from the state alone, so they change only just after a clock edge and are free of glitches.
- A Mealy machine 米利机 uses the state and the present inputs, so it can respond in the same cycle, but an input glitch can reach the output.
A Moore machine's outputs change —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Moore outputs are decoded from the state only, so they settle one clock after the input. Mealy adds the input for a same-cycle response, at the cost of possible glitches.
The design procedure
- State diagram → state table → binary state encoding → flip-flop inputs from the excitation table → minimised next-state logic.
- State minimisation 状态化简 first: two states with the same outputs and the same next states are one state. Merging them saves flip-flops and logic.
After minimisation an FSM has 5 states. How many flip-flops does a binary state encoding need?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
$2^{2} = 4 < 5 \le 8 = 2^{3}$, so 3 flip-flops. The 3 unused codes still need a safe next state.
Worked example: the parity detector
- Output 1 when the number of 1s seen so far is odd. Two states, EVEN and ODD: a 1 moves across, a 0 stays. The output is 1 in ODD.
- Input 1, 0, 1, 1: EVEN → ODD → ODD → EVEN → ODD. Three 1s, output 1. With ODD = 1, the next-state logic is one XOR: $Q^{+} = Q \oplus x$.
The parity detector is implemented with how much logic?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Two states (EVEN, ODD), with a 1 moving between them: the next state is $Q \oplus x$, one gate and one flip-flop.
Worked example: detecting 1011
- Track the longest matched prefix: S0, S1 (seen 1), S10, S101. On each input go to the longest tail of the input so far that is still a prefix of 1011.
- From S101, a 1 completes the match: output "detected" and go to S1, because that final 1 starts the next match. A 0 leaves "1010", whose tail "10" is a prefix, so go to S10.
| State | in 0 | in 1 |
|---|---|---|
| S0 | S0 | S1 |
| S1 | S10 | S1 |
| S10 | S0 | S101 |
| S101 | S10 | S1, detect |
Stream 1, 0, 1, 1, 0, 1, 1: S0 → S1 → S10 → S101 → detect (S1) → S10 → S101 → detect. The two copies of 1011 share bit 4, and the machine finds both. Restarting at S0 after a match would miss the second.
An overlapping 1011 detector sees the stream 1, 0, 1, 1 and reports a match. What state should it go to?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Of the tails of 1011 ("1", "11", "011"), only "1" is also a start of 1011, so the machine goes to S1. Then 0, 1, 1 completes a second match: 1011011 holds two.
An overlapping 1011 detector receives 1, 0, 1, 1, 0, 1, 1, 0, 1, 1. How many matches does it report?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Matches end at bits 4, 7 and 10, each sharing its first 1 with the match before. A detector that restarts at S0 after each match misses the one ending at bit 7 and reports only 2.
Three common slips
- Restarting after a match. Overlapping detection keeps the part of the match that starts the next one.
- Encoding before minimising. Merge equivalent states first, or you build extra flip-flops.
- Picking the wrong machine type. Mealy for same-cycle response; Moore when outputs must not glitch.
Two states with the same outputs and the same next state for every input can be merged into one.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
No input sequence can tell them apart, so one state does the job, and the machine may need fewer flip-flops.
Recap
- An FSM is states, transitions and outputs: a state register plus next-state and output logic.
- Moore outputs come from the state; Mealy outputs from the state and inputs.
- A sequence detector tracks the longest matched prefix, including after a match.