States and memory
A finite state machine is a circuit that is always in one of a few states. This traffic light has three: GREEN, YELLOW and RED. A state diagram draws each state as a circle; the glowing one is the state right now.
The circuit stores its state in flip-flops. A flip-flop holds one bit until it is told to change. Two flip-flops give four patterns, enough for three states: GREEN is 00, YELLOW 01, RED 10. Together they form the state register.
Output logic is a few gates that turn the state bits into lamp signals: 00 lights green, 01 yellow, 10 red. Here the outputs depend only on the state. A machine built like this is called a Moore machine.
Making a move
An input is a signal that comes from outside the machine. The timer gives T = 0 while the light should stay as it is, and T = 1 when its time is up.
Next-state logic reads T and the current state, fed back from the register, and works out where to go. GREEN with T = 0 gives 00 again; with T = 1 it gives 01, YELLOW. Nothing changes yet.
The clock is a signal that ticks between 0 and 1. On each rising edge, the moment it goes from 0 to 1, every flip-flop copies its input at once. The register becomes 01: the machine follows the arrow to YELLOW.
Each time the timer runs out, the next clock edge moves the light one state on: GREEN, YELLOW, RED, then back to GREEN. Between edges nothing changes, so the lamps stay steady.
The big picture
In a Mealy machine, outputs read the inputs as well as the state. Warning lamp W lights the moment T becomes 1 while the light is green, without waiting for the clock. The Moore lamps change only after the edge.
Every state machine circuit has the same three parts. The state register holds which circle is current, next-state logic follows the arrows, and output logic shows what each circle means. Draw the diagram first, then build the parts.
Tables and code
;; step 1/9 · fsm-idea ;; about: State diagram finite state machine (FSM): a fixed, small set of states exactly one is current at a time states of this machine: GREEN YELLOW RED state diagram: circle = a state arrow = a move to another state
A finite state machine is a state register (flip-flops) plus two blocks of combinational logic: next-state logic and output logic (Harris and Harris, Digital Design and Computer Architecture, section 3.4). A D flip-flop copies its input to its output only on the rising edge of the clock and holds it at all other times. Texas Instruments' SN74HC74 holds two of them in one chip.