Combinational logic answers a question about the present inputs. A processor, however, must remember a program counter, register contents, outstanding requests, protocol phase, and architectural mode. That memory is state. Sequential logic is the disciplined combination of storage elements and combinational next-state logic. Its correctness depends on both a functional relation—what state should follow what inputs—and a temporal relation—when a new state is allowed to become visible.
This chapter develops the synchronous design model used by most digital systems. It distinguishes latches from edge-triggered registers, derives setup and hold constraints, models finite-state machines formally, and treats asynchronous inputs and reset as sources of metastability and illegal behavior. The purpose is not to draw a traffic light but to make timing and state invariants explicit enough that a pipeline controller, bus arbiter, or cache controller can be reasoned about and tested.
State as a mathematical transition system
A synchronous machine can be modeled as a tuple a set of states input alphabet output alphabet transition function and output function At discrete clock boundaries, if the current state is and the sampled input is then
depending on whether the machine is Mealy or Moore. A Mealy output may respond combinationally to an input during a state; a Moore output depends only on registered state. Moore outputs often simplify timing and avoid input glitches at an interface, while Mealy machines may use fewer states and respond within a cycle. Neither is universally superior; the interface contract decides whether an output may change between clock edges.
The state set is an abstraction. A two-bit register physically has four encodings, but a protocol may use only 00, 01, and 10; 11 is illegal. The transition function must define what happens from an illegal encoding, usually by moving to a safe recovery state. Leaving an encoding unconstrained is not the same as proving it unreachable. Faults, reset races, soft errors, X-propagation in simulation, and design bugs can all make an “impossible” state observable.
Worked example: a request controller. Let states be IDLE, BUSY, and ERROR. In IDLE, a request starts work and transitions to BUSY; no request keeps the machine in IDLE. In BUSY, completion transitions to IDLE, while a detected fault transitions to ERROR. In ERROR, reset returns to IDLE and all normal inputs are ignored. The safety invariant is that a request is accepted only in IDLE; the liveness assumption is that a BUSY operation eventually either completes or reports a fault. The hardware design is incomplete until the priority between simultaneous completion and fault is specified.
The diagram completes that contract: reset has highest priority in every state, fault wins over completion in BUSY, and a request during BUSY is not queued. All ordinary transitions sample inputs on the active edge; the global reset rule is omitted from the arrows for legibility.
Trace challenge. Starting in IDLE, sample (request, completion, fault) as (1,0,0), (1,1,1), then (1,1,0), with reset absent. Predict the post-edge states and count accepted requests.
Check the state traceExpandCollapse
The states are BUSY, ERROR, ERROR. Exactly one request is accepted, at the first edge. Fault outranks completion at the second edge; the third request cannot escape ERROR without reset. Accepting another request while busy would violate the specified no-queue contract.
State the transition
What is required to specify a synchronous state machine?
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
Latches, flip-flops, and registers
A level-sensitive latch is transparent during an enable phase and holds its previous value otherwise. If enable is high, follows after propagation delay; if enable is low, is stable. A pair of latches driven by complementary phases can form an edge-triggered element. A flip-flop is commonly abstracted as sampling at a clock edge and retaining that sample until the next active edge:
where denotes the state just after the edge. A register is a bank of such storage elements, often with a shared clock-enable and reset. The abstract edge-triggered model prevents a combinational path from “seeing through” a storage element during the active edge, which makes cycle-by-cycle reasoning compositional.
The abstraction has limits. A physical flip-flop needs its input stable for a setup interval before the edge and a hold interval after it. If the input changes too close to the edge, the internal feedback may take an unusually long time to resolve to 0 or 1: metastability. The output is not a third logical value in the final system, but it can violate downstream timing while resolving. No finite synchronizer can make metastability impossible; it reduces the probability that unresolved behavior reaches logic by giving the first stage time to settle.
Two flip-flops in series are a common clock-domain crossing synchronizer for a single slowly changing control bit. The first may become metastable; the second samples it one cycle later. This is not safe for a multi-bit bus whose bits can settle on different cycles, nor does it preserve every pulse if the source toggles faster than the destination can observe. Multi-bit data requires a protocol such as a handshake, asynchronous FIFO, gray-coded pointer scheme, or a formally justified sampling method.
A correct truth table can still miss timing
A register's input changes 50 ps before the clock edge, but its setup requirement is 90 ps. Simulation using only Boolean values reports the expected next state.
Which conclusion is justified?
Timing constraints
In a single-clock path, a launching register changes after the clock-to-Q delay combinational logic requires and the receiving register requires data to arrive at least before the next edge. With clock period and skew a simplified setup constraint is
The corresponding hold constraint is a lower-bound condition: the launching register’s earliest change plus the shortest combinational delay must not reach the receiving register too soon after the same edge. A simplified form is
Increasing the clock period can repair setup failure but cannot generally repair hold failure. This distinction matters in pipeline design: a path may be slow enough to miss the next edge, or so short that new data corrupts the old sample immediately after the edge. Adding a register changes latency and may repair setup while creating a new architectural timing contract.
Worked timing calculation. Suppose ps, the worst combinational path is 620 ps, setup time is 90 ps, and the worst skew provides 20 ps of relief. Then ps, so the frequency bound from this path is approximately 1.30 GHz. If the shortest path has ps and ps, with hold requirement 45 ps and no helpful hold skew, the hold inequality is satisfied at 55 ps. Notice that the setup and hold calculations use different extrema; averaging delays would be unsound.
Clock gating and enables add another layer of correctness. A register with enable has next-state equation meaning it retains state when disabled. A gated clock physically suppresses clock transitions and can save power, but the gate itself must be designed so enable changes cannot create a spurious pulse. A synchronous enable is usually easier to verify than ad hoc combinational clock gating.
Finite-state-machine design flow
A robust design flow begins with an interface contract rather than an encoding. First define events, inputs, outputs, safety properties, liveness assumptions, reset behavior, and simultaneous-event priority. Next identify the smallest state that distinguishes futures: two histories may share a state only if every possible future input produces equivalent outputs and transitions. Then write a state-transition table or graph, choose an encoding, derive next-state logic, and verify the implementation against the transition relation.
State minimization is a behavioral question. If two states produce different outputs for the same input, they cannot be merged. If their outputs match, they can be merged only when their successor states are themselves equivalent under every input. This is the same idea as distinguishing prefixes in automata theory, now applied to a clocked controller. One-hot encoding uses a separate bit for each state, binary encoding uses roughly bits, and gray-like encodings can reduce simultaneous bit changes. Encoding affects physical timing and fault detection but not the abstract machine.
Worked example: a ready/valid interface. Suppose a producer presents valid and data, and a consumer presents ready. A transfer occurs on a clock edge exactly when valid && ready. If the producer is allowed to keep data stable while waiting, the controller needs EMPTY and FULL states: EMPTY may accept a new item, FULL holds an item until transfer. If simultaneous dequeue and enqueue are permitted, FULL with both signals high may remain FULL while replacing the data; if not, the enqueue must be rejected. The choice changes throughput and must be stated. A common bug is to clear valid as soon as it is asserted rather than when the handshake condition is true, losing data when the consumer is not ready.
Counters, timers, and derived state
A counter is a register plus an increment, decrement, hold, or load function. For a -bit modulo counter, A timer that must represent a duration of cycles needs a clear convention: does zero mean “expired now,” does it count the current edge, and can reload occur on the expiration edge? Off-by-one errors are semantic errors in not merely coding mistakes.
Worked example: a three-cycle timeout. If a request is accepted at edge and the specification says failure should be raised if completion has not arrived by the third subsequent edge, then the relevant checks occur at Load 3 at and, at each later edge without completion, decrement then test the new value: it becomes 2, 1, 0 and expires at An equivalent convention loads 2 and tests the old value for zero before decrementing: old values at are 2, 1, 0. Loading 2 and testing after decrement instead expires at one edge too early. State whether completion wins over timeout at and test durations 0, 1, 2, 3, and 4 explicitly; duration zero needs its own acceptance-edge rule.
Derived state should be minimized when it can be recomputed without ambiguity. Storing both a count and an empty flag creates a consistency invariant; if one updates and the other does not, the controller can accept or discard data incorrectly. Redundant state is justified when it improves timing or power, but then the equality and update invariants must be asserted.
Reset and initialization
Reset establishes an initial state but does not automatically initialize every physical bit in every technology. A synchronous reset is sampled by the clock; an asynchronous reset can affect state between edges but introduces deassertion timing concerns. A common safe pattern asserts reset asynchronously for rapid containment and deasserts it synchronously per clock domain.
Reset strategies and timing boundaries:
| Reset architecture | Assertion timing | Deassertion timing | Hardware failure mode / race condition |
|---|---|---|---|
| Pure synchronous | On active clock edge | On active clock edge | Cannot reset if clock is stopped or gated; requires larger gates in logic path |
| Raw asynchronous | Immediate (level-triggered) | Asynchronous to clock | Deassertion near clock edge violates recovery/removal timing, causing metastability |
| Synchronized deassertion | Immediate (asynchronous) | Synchronized via 2-FF chain | Clean deassertion aligned to clock; eliminates cross-register reset skew |
// Reset synchronizer: asynchronous assertion, synchronous deassertion
always @(posedge clk or posedge async_rst) begin
if (async_rst) begin
rst_meta <= 1'b1;
rst_sync <= 1'b1;
end else begin
rst_meta <= 1'b0;
rst_sync <= rst_meta;
end
end
Reset values should be chosen for safety, not convenience. A bus arbiter should not grant multiple owners after reset; a valid/data queue should begin empty; a privilege controller should begin in the least-authority state. If the state encoding has illegal patterns, reset should enter a legal recovery state and the transition logic should route illegal encodings there as well.
Reset is also a protocol event. Downstream logic must know when outputs are meaningful, and cross-domain consumers must not observe one domain leaving reset while another remains held. A design that “works after reset” in simulation may fail in hardware if deassertion violates recovery/removal timing or if memories and registers initialize differently.
Verification and invariants
The strongest FSM tests are derived from properties. Safety properties say something bad never occurs: never grant two mutually exclusive resources, never dequeue an empty queue, never assert done without a prior accepted request. Liveness properties say something good eventually occurs under assumptions: every accepted request eventually completes or faults, a waiting arbiter eventually grants a continuously requesting client, and a nonempty queue eventually dequeues when the consumer remains ready.
An invariant proof has the form: establish the property in every initial state, assume it before an edge, and show every allowed transition preserves it. For a one-entry queue, the invariant is valid=0 iff no item is stored, and valid=1 implies stored data is stable until a handshake. The proof must consider no operation, enqueue only, dequeue only, and simultaneous enqueue/dequeue. Omitting the simultaneous case is a classic completeness failure.
Simulation explores traces; formal verification can quantify over all input combinations within a bounded or inductive model. Neither replaces a correct environment assumption. An assertion that assumes ready is always high proves little if the actual integration allows backpressure.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 1.3.1: Finite State Machine Controller Design
Design a four-state elevator controller for floors 0 and 1. Specify state, request input, motor output, door output, reset behavior, illegal-state recovery, and simultaneous arrival/request priority.
HintExpandCollapse
Construct state transition diagrams and truth tables with explicit current and next state assignments.
Worked solutionExpandCollapse
A correct solution has explicit states such as IDLE_0, MOVING_TO_1, IDLE_1, and MOVING_TO_0, with outputs derived from state. A request received while moving must be queued, ignored, or merged by specification; silently choosing one is not a design. Illegal state encodings should disable the motor and return to a known idle state after reset or fault recovery.
Exercise 1.3.2: Setup and Hold Timing Constraint Equations
A path has ps, ns, setup 80 ps, and clock skew of -30 ps. Compute the minimum clock period and explain the sign of skew in your equation.
HintExpandCollapse
Calculate maximum clock frequency from flip-flop clock-to-Q delay, combinational logic, and setup margins.
Worked solutionExpandCollapse
The bound is ps, because negative skew makes the receiving edge effectively earlier relative to the launching edge. The maximum frequency is about 613.5 MHz. The exact sign convention can vary, but the physical question is whether skew gives or removes available setup time.
Exercise 1.3.3: Metastability and Multi-Clock Synchronizers
Explain why synchronizing each bit of a binary counter independently can produce a value that never existed in the source domain. Give a safer transfer protocol.
HintExpandCollapse
Explain the mean time between failures (MTBF) when crossing asynchronous clock domains with dual flip-flops.
Worked solutionExpandCollapse
Bits do not cross at the same instant. A source changing from 0111 to 1000 can be sampled as 1111, a mixed value never held by the source. Use a gray-coded counter for pointer transfer when its one-bit transition property is proven, or transfer data with a request/acknowledge handshake or asynchronous FIFO.
Exercise 1.3.4: Ready/Valid Handshake Protocol State Table
Write a complete transition table for a one-entry ready/valid buffer, including simultaneous enqueue and dequeue. State whether it supports fall-through behavior.
HintExpandCollapse
Specify valid and ready assertion rules to prevent data loss or duplicate reads across boundaries.
Worked solutionExpandCollapse
The buffer is empty when valid=0. Enqueue without dequeue stores data and sets valid; dequeue without enqueue clears valid; neither preserves state; both can replace data and preserve valid if the protocol permits throughput one per cycle. Fall-through requires an additional combinational path from input to output when empty and a different timing contract; a registered buffer does not fall through.
Exercise 1.3.5: Queue Storage Invariant Verification
Prove the queue-valid invariant for the four cases of input handshake and output handshake. Identify the case that changes the stored data without changing occupancy.
HintExpandCollapse
Prove that enqueue and dequeue operations maintain FIFO order and correct full/empty status flags.
Worked solutionExpandCollapse
In an empty state, only an accepted enqueue makes valid true. In a full state, only an accepted dequeue without enqueue makes it false. Neither handshake preserves it. Simultaneous handshake replaces the stored item and preserves occupancy. The proof must include the fact that the producer holds input data stable while valid && !ready.
Exercise 1.3.6: One-Hot vs Binary State Encoding Trade-offs
Compare one-hot and binary state encoding for 12 states. Discuss flip-flop count, decode complexity, illegal encodings, and timing rather than declaring one universally better.
HintExpandCollapse
Compare flip-flop count, combinational decode logic speed, and power dissipation between encoding strategies.
Worked solutionExpandCollapse
One-hot uses 12 state bits and often simple local decode. Of its bit patterns, exactly 12 have one asserted bit, leaving 4084 illegal encodings, including all-zero and multi-hot values. Binary uses four bits: 12 encodings represent states and four of the 16 encodings remain unused. Binary decode may create deeper logic. Physical fanout, power, synthesis technology, and fault model determine the choice; both schemes need defined illegal-state behavior.
Exercise 1.3.7: Asynchronous Reset Assertion with Synchronous Release
Give a reset design for a multi-clock system with a producer, consumer, and asynchronous external interrupt. Identify which signals require synchronization and which require a handshake.
HintExpandCollapse
Explain how reset synchronizers prevent metastable transitions when releasing circuit resets.
Worked solutionExpandCollapse
Reset release should be synchronized independently in each clock domain. A single-bit interrupt request needs synchronization or an asynchronous capture circuit; a multi-bit event needs a handshake or FIFO. The producer and consumer need a defined reset interaction so neither treats stale valid/data as a new transfer.