Binary State Machine

A finite state machine (FSM) is a digital circuit that can be in exactly one of a finite number of states at any time. The circuit transitions between states on each clock cycle, based on its current state and its inputs.

A state machine has three essential components:

• State registers: A set of D flip-flops that store the current state as a binary number. If the machine has N flip-flops, it can represent up to 2^N states.
• Next-state logic: A combinational circuit (AND/OR gates) that computes the next state based on the current state and inputs.
• Output logic: A combinational circuit that produces the outputs based on the current state (and possibly the inputs, depending on the machine type).

The entire machine is synchronous — all state transitions happen on the same rising clock edge, which keeps the system deterministic and predictable.

Each state in a FSM must be represented as a unique binary pattern. The simplest approach is binary encoding, where states are numbered sequentially and stored in the state registers as ordinary binary numbers.

For example, a 4-state machine might use:

State S0: 00  (2'b00)
State S1: 01  (2'b01)
State S2: 10  (2'b10)
State S3: 11  (2'b11)

This encoding uses the minimum number of flip-flops (log₂(N), rounded up), but the decode logic can be slower because the next-state function requires more gate levels to compute.

One-hot encoding is an alternative where each state gets its own flip-flop, and exactly one flip-flop is high (hot) at any time:

State S0: 0001
State S1: 0010
State S2: 0100
State S3: 1000

One-hot encoding uses more flip-flops (N flip-flops for N states instead of log₂(N)), but the next-state logic is much simpler and faster — each state transition only needs to shift the 1 bit to a neighboring position. This speed advantage makes one-hot encoding the preferred choice in high-speed CPU controllers.

These two state machine types differ in when and how outputs are generated:

Moore Machine:

• Outputs depend only on the current state, not on the inputs.
• Outputs are synchronous — they change only on clock edges when the state changes.
• Simpler to design and debug because outputs are purely state-driven.
• May require extra states if an output needs to respond quickly to an input change.

Mealy Machine:

• Outputs depend on both the current state and the current inputs.
• Outputs can change asynchronously within a clock cycle when inputs change.
• Often requires fewer states than an equivalent Moore machine.
• More complex to design and more susceptible to glitches on output lines.

The behavior of any state machine is fully described by its state transition table. This table maps each combination of current state and input to a next state and output value. Here's an example for a simple 2-bit up-counter (a state machine that counts 00, 01, 10, 11, and wraps back to 00):

Current State | Next State | Output
     00       |    01      |   00
     01       |    10      |   01
     10       |    11      |   10
     11       |    00      |   11

To implement this as a circuit, we derive the next-state logic from the transition table. For the counter above:

• Next_Q0 = NOT(Current_Q0) — bit 0 toggles every cycle (a single NOT gate, or more commonly a T flip-flop).
• Next_Q1 = Current_Q0 XOR Current_Q1 — bit 1 toggles when bit 0 is 1 (an XOR gate).

This is a Moore machine (output = state). Adding an input (like an "enable" signal or a "direction" signal for up/down counting) adds more columns to the transition table and more terms to the next-state logic equations.

State machines are everywhere in digital hardware. Here are a few concrete examples:

Traffic Light Controller: A classic Moore machine with states like GREEN_NS, YELLOW_NS, GREEN_EW, YELLOW_EW. Each state has a fixed duration (determined by a counter), and the state machine cycles through the pattern indefinitely. The binary state encoding might be: 00 = GREEN_NS, 01 = YELLOW_NS, 10 = GREEN_EW, 11 = YELLOW_EW.

Elevator Controller: A more complex state machine with states representing the current floor, direction of travel, and door status. Inputs include floor sensors, button presses, and door obstruction sensors. The state transition logic must handle competing requests, safety interlocks (doors must be closed before moving), and priority scheduling.

UART Receiver: A serial communication controller uses states like IDLE, START_BIT, DATA_BITS (8 states, one for each data bit), PARITY_BIT, and STOP_BIT. The state machine samples the serial line at exactly the right moments to reconstruct the transmitted byte from the incoming bit stream.

CPU Control Unit: The heart of every processor is a state machine (or several) that sequences the fetch-decode-execute cycle. Each micro-operation within an instruction — reading the instruction word, incrementing the PC, decoding the opcode, reading registers, performing the ALU operation, writing results — is a different state in the control FSM.

Here's the process I follow when designing a digital state machine:

1. Draw the state diagram: Circles for states, arrows for transitions. Label each arrow with the input condition that triggers it. For Moore machines, write the output inside each state circle. For Mealy machines, write the output on each arrow.
2. Assign binary state codes: Choose binary or one-hot encoding based on speed vs. flip-flop count tradeoffs.
3. Build the state transition table: List every combination of current state and input, and write the next state and output for each.
4. Derive the logic equations: Each next-state bit and output bit becomes a Boolean equation. Use Karnaugh maps or logic minimization to simplify.
5. Implement with gates and flip-flops: The next-state equations become AND-OR logic feeding D flip-flops, and the output equations feed the output pins.