Lesson 25 Flashcards — Finite State Machines II

Click a question to reveal the answer.

1. List the seven steps of FSM design.

Encode the states, inputs, and outputs; create the transition diagram; create the transition table; express the logic equations; implement with flip-flops and gates.

2. How many bits do you need to encode n states?

\(\lceil \log_2 n \rceil\). Three or four states need 2 bits — and each bit needs its own flip-flop.

3. You have 3 states encoded in 2 bits. What about the fourth code?

You must define what it does. If the machine powers up or glitches into an unhandled state code with no transition out, it locks up there permanently.

4. How many rows does the binary transition table have?

\(2^{\text{state bits} + \text{input bits}}\) — every combination, including the rows for unused state codes. Three states with one input give 8 rows, not 6: Lesson 24's 6 counted states, while 2 bits hold four codes. (A machine with many inputs is listed one row per (state, condition) pair in priority order instead — the Project 2 form.)

5. How do you get logic equations from a transition table?

Treat each next-state bit column as the output of a truth table whose inputs are the current state bits and the inputs, then write its SOP expression — exactly as in Objective 2.7.

6. What does a D flip-flop do?

Copies its input \(D\) to its output \(Q\) at each clock edge, and holds it in between. That hold is the memory.

7. How many flip-flops does an FSM need?

One per state bit. A machine encoded in 2 bits needs 2 flip-flops.

8. Describe the three blocks of a complete FSM circuit.

Next-state logic (combinational) reads current state and inputs; flip-flops latch the result on the clock edge; output logic produces the outputs. The feedback path from the flip-flops back to the next-state logic is what makes it a machine.

9. What sets the pace of an FSM?

The clock. The machine advances exactly one transition per clock edge.

10. How do you tell from the equations that a machine is Moore?

The output expression depends only on the state bits, with no input variable in it.

11. How do you implement an FSM in software instead of gates?

Hold the state in a variable, switch on it with one case per state, and inside each case test the inputs in a defined priority order. The switch replaces the next-state gates; the variable replaces the flip-flops.