Finite state machines

A finite state machine (FSM) is a circuit with a small number of states. At each clock edge it moves to a next state that depends on the current state and the input. A vending machine, a traffic light, a lift, the part of a processor that steps through an instruction, and a network protocol are all state machines.

Moore and Mealy

• Moore machine: the output depends only on the state. Outputs are steady for a whole clock.
• Mealy machine: the output depends on the state and the current input. It often needs fewer states and reacts one clock sooner.

Example: detect 101

Output 1 whenever the last three input bits were 1, 0, 1 (overlaps allowed, so 10101 contains two). The states remember how much of the pattern has been seen:

This is a Mealy machine: the output is 1 on the transition from S2 with input 1. After a match it goes to S1, not S0, because the final 1 can start the next match.

# Mealy machine: (state, input) -> (next state, output)
table = {
    ("S0", "0"): ("S0", 0), ("S0", "1"): ("S1", 0),
    ("S1", "0"): ("S2", 0), ("S1", "1"): ("S1", 0),
    ("S2", "0"): ("S0", 0), ("S2", "1"): ("S1", 1),
}
state, outputs = "S0", ""
for bit in "1101011":
    state, out = table[(state, bit)]
    outputs += str(out)
    print("read", bit, "-> state", state, " output", out)
print("input:  1101011")
print("output:", outputs)

In hardware, each state gets a binary code (S0 = 00, S1 = 01, S2 = 10), kept in flip-flops, and the next-state and output columns become truth tables, simplified with K-maps as before. One-hot encoding uses one flip-flop per state instead: more flip-flops, but simpler logic, common on FPGAs.

Example: a traffic light (Moore)

# Moore machine: each state has its lamp and how many ticks it lasts.
states = {"GREEN": ("go", 3, "YELLOW"), "YELLOW": ("slow", 1, "RED"), "RED": ("stop", 2, "GREEN")}
state, ticks = "GREEN", 0
for clock in range(8):
    lamp, length, nxt = states[state]
    print("tick", clock, ":", state, "-", lamp)
    ticks += 1
    if ticks == length:
        state, ticks = nxt, 0

Each state stays for a number of clock ticks and then moves to the next. The output (which lamp is lit) depends only on the state.

Mark lesson complete